Question

Which of the regular expressions given below represents the following DFA?

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

II. $0^{\ast }{1}^{\ast }1+{11}^{\ast }{0}^{\ast }1$

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

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

Answer 1

The correct option is D I and III Only


I. $0^{\ast }1(1+{00}^{\ast }1{)}^{\ast }$ is correct r.e for the given machine.

II. $0^{\ast }{1}^{\ast }1+{11}^{\ast }{0}^{\ast }1$ is not correct.

0101 is accepted by DFA, but can not be generated by this regular expression

III. $(0+1{)}^{\ast }1$ is correct since the language accepted by the given DFA is all strings ending with 1.

$\therefore$ I and III are equivalent to given DFA.