Discussion
The minimum number of states required for DFA to accept binary strings that are divisible by 3 is
Answer: C
The minimum is 3 states.
Read the binary number left to right and track the value modulo 3. Appending a bit b to a number x gives 2x + b, so the remainder changes as r to (2r + b) mod 3. Only three remainders are possible, 0, 1 and 2, so three states suffice, with remainder 0 as the start and accepting state.
The three states are distinguishable (from remainder 1, reading 1 gives 0; from remainder 2, reading 0 then 1 is needed), so fewer cannot work, and a fourth state would be redundant.
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