Discussion
How many states does the minimal DFA for the language of strings over {a, b} ending in abb have?
Answer: D
Correct answer: 4
The automaton must remember how much of abb has been seen so far, which gives four conditions: nothing yet, an a seen, ab seen, and abb seen. Those are the four states, the last being accepting. No two of them can be merged, because from each a different continuation is needed to reach acceptance, so four is also the minimum.
No comment is present. Be the first to comment.
Loading…
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