Skip to main content

DFA with no three consecutive 0's

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.

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.

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

State01
→ *s₀s₁s₀
*s₁s₂s₀
*s₂s₃s₀
s₃s₃s₃

State diagram

 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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 2 questions →