World's most popular travel blog for travel bloggers.

[Solved]: Is this language Context-Free?

, , No Comments
Problem Detail: 

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