Possible Duplicate:
Is this language Context-Free?

The language is defined by $$(a+b)^*-\{(a^nb^n)^n\mid n \geq1 \}$$

is Context-Free Language? I believe that the answer is that it is not a CFL's, but I can't prove it by Ogden lemma or pumping lemma.

chazisop, (a+b)* means {a,b}*. That's all strings that you can form with the symbols a or b or both.


If I understand the notation correctly, only $ab$ can fit both $(a+b)^{*}$ and $(a^{n}b^{n})^{n}$. I see no other way of stacking more $b$'s after the a's, since $a+$ suggest you should have at least one $a$ in every repetition of the expression in parentheses.

$(a+b)^{*}-ab$ seems like a regular language to me, since $ab$ rejects, $a+b$ just consumes one or more $a$'s before a $b$. If we can construct a DFA for $a+b$, we can construct one for $(a+b)^{*}$ as well.

| cite | improve this answer | |
  • 2
    $\begingroup$ The language under consideration is all strings over $\{ a , b \}$ except for those of the form $(a^nb^n)^n$ for some $n \geq 1$. $\endgroup$ – Arthur Fischer Jul 4 '12 at 19:14
  • $\begingroup$ You seem to be thinking $(a+b)$ means $(a^+ b)$. See Frank's edit to the question. $\endgroup$ – Tara B Jul 9 '12 at 10:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.