Show that language is context free
$E=\{a^ib^j|i\neq j\wedge 2i\neq j\}$

Look at my solution please: I use the fact that languages context free are closer under sum
$E=E_1\cup E_2\cup E_3 = \{a^ib^j|i>j\}\cup \{a^ib^j|j>2i\}\cup \{a^ib^j|i<j<2i\} $
Grammar for $E_1:$
$T\rightarrow a|aTb|aT$
Grammar for $E_2:$
$T\rightarrow aTbb|Tb|b$
Grammar for $E_3:$
$T\rightarrow aaU$
$U\rightarrow aUbV|bbb$
$V\rightarrow v|\epsilon$

For $E_1,E_2,E_3$ I showed CFG. For $E_1,E_2$ is obvious. What about grammar for $E_3$. Should I prove that it is correct and full ? Maybe, it is clear enough.


Assuming that you meant $V\to b\mid\epsilon$, it looks fine. As a teacher I think that I’d have wanted some justification for the grammar $E_3$, though. It would be enough to observe that if $U\to aUbV$ is applied $n$ times, the final result must be $a^{n+2}b^{n+3+k}$, where $k$ is the number of times that $V\to b$ is applied; clearly $0\le k\le n$, so

$$n+2<n+3+k\le 2n+3<2(n+2)\;.$$

  • $\begingroup$ very clever justification! Thanks, I am very welcome :) $\endgroup$ – user220688 Apr 20 '15 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.