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 ...
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.
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
context-free × 1669formal-languages × 770
formal-grammars × 607
pushdown-automata × 236
regular-languages × 224
automata × 219
pumping-lemma × 189
parsers × 120
closure-properties × 89
computability × 62
ambiguity × 61
finite-automata × 59
compilers × 48
turing-machines × 46
regular-expressions × 43
undecidability × 39
proof-techniques × 37
normal-forms × 36
complexity-theory × 33
context-sensitive × 32
algorithms × 24
nondeterminism × 23
chomsky-hierarchy × 20
lr-k × 18
computation-models × 17