2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "The approach is basically the same" is quite a stretch. I apologize. In order to make this work we need the stronger Ogden's pumping Lemma, as explained here: cs.stackexchange.com/q/162133/4287 $\endgroup$ Sep 19 at 21:25
  • $\begingroup$ Please correct your answer. The language does satisfy the pumping lemma, and hence it cannot be showed that it's not context free this way. $\endgroup$ Sep 23 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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