Which of the following sets are regular and which are not? Give justification.

Question

Which of the following sets are regular and which are not? Give justification.

a) $\{a^nb^{2m}\mid n\ge 0\text{ and }m\ge 0\}$
b) $\{a^nb^m\mid n\ne m\}$
c) $L((a^*b)^*a^*)$
d) $\{a^nb^nc^n\mid n\ge 0\}$

Any help would be greatly appreciated! Any help to guide me please :)

Note: I am not looking for the answers, but help to get to them.

• From Kozen textbook

Answer 1

If the notation in (c) means the language of the regular expression inside the parentheses, the answer for that part should be immediate. For the other three, a useful general principle is that if $x$ and $y$ are two letter in the alphabet of the language, and the language requires a very specific relationship between the number of $x$s and the number of $y$s in a word, then there’s a reasonable possibility that the language is not regular.

For instance, the language $\{a^nb^n:n\ge 0\}$, whose words all contain the same number of $a$s as $b$s, is the classic example of a context-free language that is not regular. There are exceptions when the requirement is enforced locally (i.e., in short segments): the language $\{(ab)^n:n\ge 0\}$ also contains only words with the number of $a$s as $b$s, and it is regular, since it’s just $L((ab)^*)$, the language of the regular expression $(ab)^*$.

If you suspect that one of the languages is regular, you can try to prove it in at least three ways: $(1)$ show that it’s the language of a regular expression; $(2)$ find a regular grammar that generates it; $(3)$ find a DFA or NFA that accepts/recognizes it. That’s fairly easy for all of the regular languages here.

If you suspect that one is not regular, try to prove this by using the pumping lemma for regular languages or the Myhill-Nerode theorem; there are examples of the use of both on this site, especially the pumping lemma, that you can find pretty easily by searching. (A Google search on pumping lemma regular site:math.stackexchange.com is probably more effective than the site’s own search engine.) The Myhill-Nerode theorem is probably the easier way to deal with one of the languages.

I’ve given the numbers of regular and non-regular languages amongst the four in the spoiler-protected block below.

Two are regular and two are not.