4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ yes its called a proof by counter-example QED $\endgroup$ – Nikos M. Jan 13 '16 at 23:12
8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The procedure given in the hint seems overkill. abaa is accepted by L2 not L4 so they're not equivalent either. $\endgroup$ – MSalters Jan 13 '16 at 10:23
  • 1
    $\begingroup$ @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.) $\endgroup$ – Raphael Jan 13 '16 at 11:38
  • $\begingroup$ 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. $\endgroup$ – MSalters Jan 13 '16 at 11:55
  • 3
    $\begingroup$ @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$. $\endgroup$ – G. Bach Jan 13 '16 at 12:21
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Jan 13 '16 at 13:15
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Raphael Jan 13 '16 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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