Discussion
Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?
Answer: A
The equivalent expression is \(0^{*}1(0 + 10^{*}1)^{*}\).
Only 1s change the state, and each 1 moves between the two states, so the DFA accepts exactly the strings with an odd number of 1s. \(0^{*}1\) reads any 0s and the first 1, reaching the accepting state. From there, \((0 + 10^{*}1)^{*}\) repeatedly either reads a 0 (staying put) or reads a 1, any 0s, and a 1 (leaving and coming back), so it always returns to the accepting state and can generate every such continuation.
\(0^{*}(10^{*}11)^{*}0^{*}\) accepts the empty string, which has no 1s. \(0^{*}1(010^{*}1)^{*}0^{*}\) cannot generate 11 followed by 1 (that is, 111), and \(0(1 + 0^{*}10^{*}1)^{*}0^{*}\) insists on a leading 0 and accepts 0 alone.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development