Idetifying equivalent regular expressions

regex

Solution

`i` and `iii` are equivalent.

The regular expressions are both "a string of `a`s and `b`s where there are at least two `b`s" (this should be clear from each definition). The fact that `iii` just has `a*`s in place of the first two `(a+b)*` is a distraction. I'll break down how `iii` describes the string:

- a possibly empty string of `a`s (`A` in the labelling below)

- the first `b` (`X`)

- another possibly empty string of `a`s (`B`)

- a second `b` (`Y`)

- and the rest of the string which is just a mix of `a`s and `b`s (`C`)

For your example, `iii` does match it. Imagine we labelled the regular expression like so (the `v` and `^` are just arrows):

A  X B  Y   C
vv v vv v vvvvvv 
a* b a* b (a+b)*

Then we can label which part of the regex corresponds to the parts of the string:

  X  Y
  v  v
aabaabaabaabbaabaabaabaabbaabaabaabaab
^^ ^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
A   B            C

(@Li-aungYip's suggestion is a good one too.)

Problem

I am revising for am exam and one of the topics is regular expressions. A past exam paper has the question Which of the following regular expressions are equivalent? Explain your reasoning. [8 Marks] (i) (a+b)* b (a+b)* b (a+b)* (ii) a* b a* b a* (iii) a* b a* b (a+b)* I think its a trick question and the answer is none because i will accept aabaabaabaabbaabaabaabaabbaabaabaabaab but ii and iii wont then because ii can only accept 2 b's maximum and iii can accept 2 b's as a minimum. Am I correct or have I got this completely wrong? I have e-mailed my lecturer for help but had no reply so I'm hoping someone here can help. Thanks.

Original source