Problem Detail: Is the language $$L = {a,b}^* setminus {(a^nb^n)^nmid n geq1 }$$ context-free? I believe that the answer is that it is not a CFL, but I can’t prove it by Ogden’s lemma or Pumping lemma.
Asked By : Andrés Felipe Téllez Crespo
Answered By : sdcvvc
Hint:
Yes
Solution:
$${(a^n b^n)^n mid n geq 1 } = {a^{n_1} b^{n_2} dots a^{n_{2k-1}} b^{n_{2k}}}: k geq 1 land n_1 = k land forall i. n_i = n_{i+1} }$$
and therefore the complement is
$${a,b}^{ast} setminus {(a^n b^n)^n mid n geq 1 } = {a^{n_1} b^{n_2} dots a^{n_{2k-1}} b^{n_{2k}}: n_1 neq k lor exists i. n_i neq n_{i+1}}$$
which is context-free as you can easily write a nondeterministic PDA.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2623
