# Is this language Context-Free? [duplicate]

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.

## marked as duplicate by Kaveh, Ran G., A.Schulz, Raphael♦Aug 15 '12 at 6:10

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.
• 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$. – Arthur Fischer Jul 4 '12 at 19:14
• You seem to be thinking $(a+b)$ means $(a^+ b)$. See Frank's edit to the question. – Tara B Jul 9 '12 at 10:53