# prove language is Context-free and not regular [duplicate]

I have to prove that $\left \{ a, b \right \}^{\ast} - \left \{ a^ib^i | i\geq 0 \right \}$ is a context-free language and it's not regular.

So far I've got that this language is not regular because regular languages are closed under complementation and $\left \{ a^ib^i | i\geq 0 \right \}$ is a well know context free language (by the way do you have a link with a formal proof that $\left \{ a^ib^i | i\geq 0 \right \}$ is context free?)

For the context-free I'm a little confused I've thought about building a PDA that recognize $\left \{ a^ib^i | i\geq 0 \right \}$ (pushing a's on the stack and popping a's when a b is read works?) I think is deterministic CF so i can use the same reasoning (complement of a DCF is a DCF language?)

• You are on the right track with closure under complementation. And your PDA works. So you have your answer. We do not usually take questions with a complete answer, unless you have a specific clarification that you need about you own solution to the problem. So, is there a specific point you do not understand. – babou Jul 5 '15 at 8:27
• I was just looking for confirmation that my line of reasoning was correct. However I assumed that the $a^ib^i$ is context-free (because I remember it being so) but how do I formally show it? – Crysis85 Jul 5 '15 at 8:40
• Giving a context-free grammar which generates is would suffice. – Klaus Draeger Jul 5 '15 at 12:32
• If by "context-free", you really mean "not regular", try the pumping lemma. – Klaus Draeger Jul 5 '15 at 12:33

The idea is similar to the pumping lemma. Suppose that you have an FDA that recognizes the language, you are going to break it. That FDA is, as it name says, finite, let it's size (node count) be $N$. To recognize the words in $\left \{ a^ib^i | i\geq N \right \}$ it certainly has to do some loops.
By exploiting a loop of length $l$ (looping in it one time more than the expected), you can see that $a^{(i+l)}b^i$ should also be accepted by that FDA, so it fails to recognize the language, as it would accept words that are not in it.
• Actually the FDA that you took may have the loop at $ab$, or at $b$, but the idea is the same. You can repeat part of the pattern an still get the FDA to accept the word. – Dietr1ch Jul 5 '15 at 14:41