HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
themidfreelanguagecontextnmid

Problem

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 \ , \ \ j\neq 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 j\neq i \ and \ j\neq2i \ \} $ 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

Solution

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.

Context

StackExchange Computer Science Q#11405, answer score: 5

Revisions (0)

No revisions yet.