Discussion
The minimum number of states required for a DFA to accept even parity (strings with even number of 1's over the alphabet {0,1}) is
Answer: B
The minimum is 2 states.
The DFA only needs to track whether it has read an even or an odd number of 1s. State E (even, the start and accepting state) and state O (odd): a 1 switches between them and a 0 leaves the state unchanged.
One state cannot work, because it would either accept or reject everything. Three or four states are more than needed; any extra state would be equivalent to E or O and merge in minimisation.
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