Question

The languge {0^1 1^j|gcd(i,j)=1} is
A. regular and not infinite
B. context-free but regular
C. context-sensitive but not context-free
D.recursive but not context-sensitive

Answer 1

Answer on Question#38651 – Math - Other

Let $p$ be the pumping length guaranteed by the pumping lemma (for context free languages). Then we choose $i \neq j$ such that $i, j \geq p$ and are both prime. Then clearly $s = 0^i 1^j \in L$.

By the pumping lemma we can divide $s$ such that $s = uvxyz$ and

1. $|vxy| \leq p$

2. $|vy| \geq 0$

3. $s' = uv^k xy^k z \in L$ for all $k \in \mathbb{N}$

For this language we get three similar cases, and one trivial case. The trivial case is where either $v$ or $y$ contains both $0's$ and $1's$, in which case $s'$ doesn't have the correct ordering, and thus $s' \notin L$.

The nontrivial cases:

1. $v$ and $y$ are both strings of $0's$, then when we pump $s$ we get $s' = 0^{i + kn}1^i$ where $n \geq 1$. Then $s' \in L$ if $\gcd(i + kn, j) = 1$, however the modular equation $i + kn \equiv 0(j)$ has the solution $k \equiv in - 1(j)$, and as $j$ is prime we are guaranteed that $n - 1$ exists. Therefore any element of the residue class $k \equiv in - 1(j)$ would give us $\gcd(i + kn, j) > 1$. Ergo $s' \notin L$.

2. $v$ and $y$ are both strings of $1's$, but this case is just the symmetric case to case 1, so we derive a contradiction in this case too.

3. $v = 0^n$ and $y = 1^h$ for some $n$ and $h$ with $1 \leq n + h \leq p$. Then when we pump we get $s' = 0^{i + kn}1^{j + kh}$. Now $s' \in L$ if $i + kn \equiv j + kh(j)$ has no solution, but we can see from here, rearranging just gives $i + k(n + h) \equiv 0(j)$, and as before this has solution $k \equiv i(n + h) - 1(j)$. So again we derive a contradiction.

Thus there is at least one string in $L$ that cannot be divided as per the pumping lemma and still have all pumping results remain in $L$. Therefore $L$ is not context free.

Answer: C.