Discussion
Consider the Deterministic Finite-state Automaton (DFA) \(\mathcal{A}\) shown below. The DFA runs on the alphabet \(\{0, 1\}\), and has the set of states \(\{s, p, q, r\}\), with \(s\) being the start state and \(p\) being the only final state.
Which one of the following regular expressions correctly describes the language accepted by \(\mathcal{A}\)?
Answer: C
The language is \(1(0+11)^{*}\).
From the start state s, a 0 goes to the dead state r, which loops on everything, so every accepted string begins with 1, which reaches the final state p. From p, a 0 loops back to p, and a 1 goes to q, from which a second 1 returns to p while a 0 falls into r. So once in p, the machine stays in an accepting state exactly when the rest of the input is a sequence of blocks '0' and '11', which is \((0+11)^{*}\).
\(0(0+1)^{*}\) describes strings starting with 0, all of which are rejected. \(1(0^{*}11)^{*}\) and \(1(110^{*})^{*}\) both fail to generate 10, which the DFA accepts (s to p on 1, p to p on 0): in the first, anything after the leading 1 must end in 11, and in the second, it must begin with 11.
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