1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Tempted to close as duplicate of our reference question. $\endgroup$
    – Raphael
    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$ 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$
    – Raphael
    Jun 9, 2015 at 9:17

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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