Question

Consider the following regular expressions over the alphabet {0, 1}

I. $1^{\ast }0(0+1{)}^{\ast }$

II. $(0+1{)}^{\ast }{01}^{\ast }$

III. $1^{\ast }0(1+0{)}^{\ast }+(0+1{)}^{\ast }{01}^{\ast }$

Which of the above regular expressions are equivalent?

• A. II and III only
• B. I and III only
• C. I, II and III
• D. I and II only

Answer 1

The correct option is C I, II and III

I and II are quite easy to understand both denote strings containing at least one 0. III is actually the union of I and II, but III is again denoting strings containing at least one 0 as both regular expressions (i.e. I and II) are equivalent, so union won't make any difference.

Hence all 3 regular expressions are equivalent.