I have a question to find out that $L = \{a^i b^{j+3}\mid i\ne j \}$ is regular or not. I know that it is not regular. I tried with pumping lemma but I am finding just a specific number of $v$'s in $u v^i w$ that not satisfies the language condition, but not ALL $v$'s. What are the best choices for $i$ and $j$ to prove with pumping lemma that this is not a regular language?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Tempted to close as duplicate of our reference question. $\endgroup$– RaphaelCommented Jun 9, 2015 at 7:22
-
$\begingroup$ @Raphael I think this is just about specific enough to stand on its own. It passes the "What did you try? Where did you get stuck?" test. $\endgroup$– David RicherbyCommented Jun 9, 2015 at 8:27
-
$\begingroup$ @DavidRicherby But then, Rick's answer can be summarized as "if one method from the reference question does not work, try the next". $\endgroup$– RaphaelCommented Jun 9, 2015 at 9:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
When you get stuck trying to prove a language is not regular by the Pumping Lemma, as in this example, because there doesn't seem to be a good choice of $u,v,w$, it's sometimes helpful to use closure properties first, to transform the problem. This is a good example of when this paradigm is useful.
We'll do this by contradiction. Suppose that $L$ were regular. Then since regular languages are closed under complement, $\overline{L}$ would be regular. Now $\overline{L}$ isn't particularly easy to describe, since it contains strings like $bababbba$, but what is $\overline{L}\cap a^*b^*$? This is just $a^nb^{n+3}=a^nb^nb^3$. Since regular languages are closed under intersection and $a^*b^*$ is regular, that would mean that $a^nb^nb^3$ would be regular. I'll bet you can now do a pumping lemma proof to show that this language wasn't regular.
answered Jun 9, 2015 at 1:40