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?



-
(a+b)$^$a(a+b)$^$(a+b)$^*$

-
b$^$ab$^$a(a+b)$^*$

-
(a+b)$^$ab$^$ab$^*$

-
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?

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.

StackExchange Computer Science Q#51788, answer score: 8