Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I need to say Is language $a^mb^nc^n, m \not= n$ context free
I managed to find a grammar for $L1 = $ { $a^lb^mc^n | l=m$ or $m = n$ }, but I couldn't find the one I needed. Maybe it is impossible, but than why? If it may be helpful, that is the grammar for L1 wich i found: $A \rightarrow \epsilon |aAb, B \rightarrow \epsilon|bBc, S1 \rightarrow A|S1c, S2 \rightarrow B|aS2, S\rightarrow S1|S2$
I think that is not context free at all but I don't know how to proof.
The reason that $L_1$ is context-free is that one needs to keep track of only two numbers at the same time: either $l=m$ or $m=n$. The 'or' is handled using union, we patch two languages together. The difference of the two numbers $l-m$ or $m-n$ can be stored on the stack while reading the string.
Your language $L=\{a^mb^nc^n \mid m\neq n\}$ is not context-free. Intuitively because we need to handle three numbers, and there is no way to store two differences.
The formal proof of non-context-freeness can be done using the pumping lemma for context-free languages. As the specification involves the unequality of $m$ and $n$ a specific trick is needed, which involves a factorial. An example of this trick is shown here for nonregularity: Prove if $L=\{0^m1^n∣m≠n\}$ is regular or not. The approach is basically the same.
