1
$\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$
2
$\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$

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.