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 ...
Hendrik Jan's user avatar
  • 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.
oleshkowitz's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible