1
vote
Accepted
How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?
Your analysis is correct. In order to keep the $a^n b^n c^m$ structure of the string, the only ways to pump are case (2) pump both $a$'s and $b$'s, or case (5) pump only $c$'s. All other case will ...
- 29.6k
1
vote
Accepted
Is $L=\{1^n2^n3^m : n\neq m\}$ context free?
The language is not context free, and indeed Ogden's Lemma can be used to show so. See the answer in the following duplicate.
- 76
Only top scored, non community-wiki answers of a minimum length are eligible