Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Which of the following regular expressions generate a language that is different from the rest?

  1. (a+b)$^*$a(a+b)$^*$(a+b)$^*$

  2. b$^*$ab$^*$a(a+b)$^*$

  3. (a+b)$^*$ab$^*$ab$^*$

  4. b$^*$ a(a+b)$^*$ab$^*$

RE 1 generates a language that contains the string 'a' which no other language among 2,3,4 contains, so can I say this language is different from all others? Does it suffice to show that a single string is not present in the language and hence its different from the rest?

share|cite|improve this question
yes its called a proof by counter-example QED – Nikos M. Jan 13 at 23:12

Does it suffice to show that a single string is not present in the language and hence its different from the rest?

Yes. It's actually a very neat proof.

Formally speaking, you have found $w \in \{a,b\}^*$ with $w \in L_1$ but $w \not\in L_2,L_3,L_4$. That is sufficient to show that $L_1 \neq L_2$, $L_1 \neq L_3$ and $L_1 \neq L_4$.

You have not shown that $L_2 = L_3 = L_4$. The phrasing of the question seems to suggest as much (MC questions are boring!) but you may want to prove that as an additional exercise.

Hint: Translate into NFA, determinize, minimize, check for isomorphy.

share|cite|improve this answer
The procedure given in the hint seems overkill. abaa is accepted by L2 not L4 so they're not equivalent either. – MSalters Jan 13 at 10:23
@ymbirtt Quite right, thanks! – Raphael Jan 13 at 11:35
@MSalters All four regular expressions match abaa. Maybe it's not overkill after all? (I honestly do not not a more efficient way to establish equivalence of regular expressions formally.) – Raphael Jan 13 at 11:38
I might overlook something, but L4 is b* a (a+b)* ab*, so 4 parts. Matching abaa we see that the leading b* occurs zero times, the 2nd term produces the first a in abaa leaving baa, the third term produces the one b leaving aa and the final ab* does NOT produces aa. It can produce at most a single a. – MSalters Jan 13 at 11:55
@MSalters $ba \in L((a+b)^*)$, so you go $a \in L(a)$, then $ba \in L((a+b)^*)$, and then $a \in L(ab^*)$ to get $abaa$. – G. Bach Jan 13 at 12:21

A language is just a set of strings. To show that sets $X$ and $Y$ are different, it's always enough to show that $X$ contains something that's not in $Y$ or vice-versa. This is because two sets are defined to be equal exactly if they have the same elements.

share|cite|improve this answer
I was tempted to write "the symmetric difference is not empty" but I figured that was more likely to add salt to the wound. :D – Raphael Jan 13 at 7:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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