patternMinor
Is this language Context-Free?
Viewed 0 times
thiscontextfreelanguage
Problem
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.
$$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.
Solution
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.
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.
Context
StackExchange Computer Science Q#2623, answer score: 8
Revisions (0)
No revisions yet.