--- title: "DFA with no three consecutive 0's" subject: "Discrete Structure" chapter: 2 key: "semester_4/discrete_structure:dfa-no-three-consecutive-zeros" source: https://www.bctengineer.com/q/semester_4/discrete_structure/dfa-no-three-consecutive-zeros site: BCT Engineering --- # DFA with no three consecutive 0's Discrete Structure · Chapter 2: Finite State Automata - Asked in: 2070 Bhadra, 3 marks - Video: [dfa language accepting strings with 3 consecutive zeros over ∑ ={0,1}](https://www.youtube.com/watch?v=OdGOXfItGrY) — Learning_Bay Channel - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/discrete_structure/dfa-no-three-consecutive-zeros - Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2 ## Question Construct a DFA that recognize the language "The set of bit strings that do not contain three consecutive 0's". Show only necessary figures and state diagrams. ## Short answer DFA states: s0 (0 zeros, start), s1 (1 zero), s2 (2 zeros) are final; s3 (3 zeros) is dead. On 0, move s0→s1→s2→s3; on 1, all go to s0. Accepts strings with no 000. ## Answer Let L = set of bit strings with no substring 000. The DFA must remember how many 0's have just occurred in a row (0, 1 or 2). A third consecutive 0 sends it to a dead state. **States** - s₀: last symbol is 1 (or nothing read yet): 0 zeros in a row (start). - s₁: exactly one 0 at the end. - s₂: exactly two 0's at the end. - s₃: three consecutive 0's seen (dead state, non-final). Final states: {s₀, s₁, s₂}. **Transition table** | State | 0 | 1 | |---|---|---| | → *s₀ | s₁ | s₀ | | *s₁ | s₂ | s₀ | | *s₂ | s₃ | s₀ | | s₃ | s₃ | s₃ | **State diagram** ```text 1 (loop) +--+ v | 0 0 0 ->((s0))-------->((s1))-------->((s2))-------->(s3) 0,1 (loop) ^ | | +------1--------+ | +----------------1-------------+ ``` (Double brackets mean final. Every 1 from s₁ or s₂ returns to s₀; s₀ loops on 1; s₃ loops on 0 and 1.) **Check:** *1001*: s₀ -1→ s₀ -0→ s₁ -0→ s₂ -1→ s₀, accepted. *10001*: s₀ s₀ s₁ s₂ s₃ s₃, rejected. Brute-force test up to length 12 confirmed that the DFA accepts exactly the strings with no 000. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What do s0, s1, s2 remember? A. Total number of 0's in the string B. Total number of 1's C. Number of 0's at the end of the string so far: 0, 1, 2 D. Position of the first 0 Answer: C. The DFA tracks the current run of 0's. (Key point: State meaning) 2. What happens in s3? A. It is final and loops on 1 B. It returns to s0 on 1 C. It is the start state D. Three consecutive 0's were seen; it is non-final and loops on 0 and 1 Answer: D. Once 000 appears the string must be rejected forever. (Key point: Dead state) 3. Where do s1 and s2 go on input 1? A. Back to s0, because the run of 0's is broken B. Stay in the same state C. Go to s3 D. Go to s1 Answer: A. A 1 resets the count of consecutive 0's. (Key point: Reading 1) 4. Which states are final? A. Only s3 B. s0, s1, s2 C. Only s0 D. s2 and s3 Answer: B. All states before reaching 000 correspond to strings with no 000. (Key point: Final states) ## Related in Discrete Structure - [Language of grammar; grammar for strings not ending in ab](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Alanguage-of-grammar-and-grammar-not-ending-ab) — Discrete Structure, chapter 2 - [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2 - [Define FSM; design FSA with two consecutive a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-two-consecutive-a) — Discrete Structure, chapter 2, asked 4× - [Design NFA for strings ending with aba](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Anfa-strings-ending-aba) — Discrete Structure, chapter 2 - [Design FSA for strings beginning with baa](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-strings-beginning-baa) — Discrete Structure, chapter 2 - [NFA and DFA from grammar σ→bσ|aC](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-bsigma-ac) — Discrete Structure, chapter 2, asked 4× ## Related in other subjects - [DFA for {00}*{11}* language](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-00-star-11-star) — Theory of Computation, chapter 2 - [Detector for three consecutive zeros](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-three-zeros) — Digital Logic, chapter 9, asked 2× - [Three consecutive zeros detector using SR](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-three-zeros-sr) — Digital Logic, chapter 9, asked 2× - [8085 ALP: transfer with bit set/reset](https://www.bctengineer.com/question.md?key=semester_4%2Fmicroprocessor%3Aalp-8085-set-reset-bit-80h) — Microprocessor, chapter 2