Is the language
$$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid 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
0 comments:
Post a Comment
Let us know your responses and feedback