0
$\begingroup$

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?)

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – babou Jul 5 '15 at 8:27
  • $\begingroup$ 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? $\endgroup$ – Crysis85 Jul 5 '15 at 8:40
  • $\begingroup$ Giving a context-free grammar which generates is would suffice. $\endgroup$ – Klaus Draeger Jul 5 '15 at 12:32
  • 1
    $\begingroup$ If by "context-free", you really mean "not regular", try the pumping lemma. $\endgroup$ – Klaus Draeger Jul 5 '15 at 12:33
  • 1
    $\begingroup$ "Please check whether my solution is correct" questions are considered off-topic here by our site policy. Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. $\endgroup$ – D.W.♦ Jul 6 '15 at 3:13
1
$\begingroup$

To prove that the language is Context Free, it suffices to give the Push Down Automaton, and that language is recognized by one of the simplest PDA.

To prove that the language is NOT regular, you don't only have to show that you can't find an appropriate Automaton (be it a FDA or FNA, they have equivalent expressive power), but that no one can.

That proof can't be shown with an example, because you want to prove that not a single FDA can recognize the language correctly. The proof shows a contradiction between having such FDA and that the FDA correctly rejects some words outside the language.

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dietr1ch Jul 5 '15 at 14:41

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