# Is a single string enough to prove regular expressions inequivalent?

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?

• yes its called a proof by counter-example QED – Nikos M. Jan 13 '16 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.

• The procedure given in the hint seems overkill. abaa is accepted by L2 not L4 so they're not equivalent either. – MSalters Jan 13 '16 at 10:23
• @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 '16 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 '16 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 '16 at 12:21
• The three remaining all sprecify strings that have at least two $a$'s? The expressions "focus" on the first two, the last two and the outer two $a$'s respectively. – Hendrik Jan Jan 13 '16 at 13:15

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.

• 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 '16 at 7:47