Problem Detail: Is the language $L = { a^ib^j mid i nmid j } $ context free ? If we fix $n in N$ then we know that the language $L = { a^ib^j mid forall 1 le k le n , jneq ki } $ is context free (as it can be presented as a finite union of context free languages in a similar way to the example here: Is $L= { a^ib^j mid jneq i and jneq2i } $ context free?) I think that it’s not context free but have failed to prove it. By reading other questions on this site I noticed this interesting observation: CFL’s in $a^*b^*$ are closed under complement as can be seen here: Are context-free languages in $a^*b^*$ closed under complement? So our language $L$ is context free if and only if $ bar L = { a^ib^j mid i mid j } $ is context free. I tried using the pumping lemma but to no avail. Thanks in advance
Asked By : Robert777
Answered By : Alejandro Sazo
If I’m not mistaken, you can pump $bar L$ using $sigma = a^{n}b^{n^{2}}$, because $n mod n^{2} = 0$. The result is that $bar L$ is not context free. The property that you mentioned has an “iff”, then $L$ is not context free.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11405
