Is the language $L=\{1^n2^n3^m : n\neq m\}$ context free?
I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Indeed, it seems that Ogden's Lemma is the right approach to show the language is not context-free. See here: cs.stackexchange.com/q/162133/4287 (apart from the simple change in symbols) $\endgroup$– Hendrik JanSep 19 at 21:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The language is not context free, and indeed Ogden's Lemma can be used to show so. See the answer in the following duplicate.