Which two of the following four regular expressions are equivalent? (ε denotes…
1996
Which two of the following four regular expressions are equivalent? (ε denotes the empty string.)
(i) (00)*(ε + 0)
(ii) (00)*
(iii) 0*
(iv) 0(00)*
- A.
(i) and (ii)
- B.
(ii) and (iii)
- C.
(i) and (iii)
- D.
(iii) and (iv)
Attempted by 14 students.
Show answer & explanation
Correct answer: C
Compare the languages generated by each expression.
(i) (00)*(ε + 0) = (00)*ε ∪ (00)*0. This combines all even-length zero strings with all odd-length zero strings, so it generates {0ⁿ | n ≥ 0} = 0*.
(ii) (00)* generates only {0²ᵏ | k ≥ 0}, i.e. strings with an even number of zeros.
(iii) 0* generates {0ⁿ | n ≥ 0}, i.e. all strings containing zero or more zeros.
(iv) 0(00)* generates only {0²ᵏ⁺¹ | k ≥ 0}, i.e. positive odd-length strings of zeros.
Therefore, expressions (i) and (iii) are equivalent.