Discussion
What does this NFA accept ?
The NFA has states A, B, C and D. A is the start state and D the only accepting state. Its transitions are:
| State | on 0 | on 1 |
|---|---|---|
| A (start) | A, B | A, C |
| B | D | - |
| C | - | D |
| D (accepting) | D | D |
Answer: B
The NFA accepts 0110.
From the start state A, the machine can stay in A on any symbol, or guess that a pair is starting: on 0 it can go to B, which needs another 0 to reach D, and on 1 it can go to C, which needs another 1 to reach D. D is accepting and keeps every later symbol. So the NFA accepts exactly the strings that contain 00 or 11 somewhere.
0110 contains 11: stay in A on 0, go A to C on the first 1, C to D on the second 1, then stay in D on 0. It is accepted.
101010 alternates and never has two equal symbols in a row, so no path reaches D and it is rejected. That rules out 'only A' and 'both A and B'.
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