Skip to main content

Configuration of DFA; DFA with 01 and 10

Short answer

A configuration is (state, remaining input). The DFA counts runs: q0 start; A0 (0-run), A1 (1-run); B1 after 01, B0 after 10; F final trap when both seen. Transitions: q0-0->A0, q0-1->A1; A0-0->A0, A0-1->B1; A1-0->B0, A1-1->A1; B1-0->F, B1-1->B1; B0-0->B0, B0-1->F; F loops on 0,1.

Define a configuration of a DFA. Design a DFA for the language L = {w ∈ {0,1}* : w has both 01 and 10 as substrings}. Verify your design by taking one accepted and one rejected string.

Configuration (instantaneous description) of a DFA

A configuration of a DFA M = (Q, Σ, δ, q₀, F) is a pair (q, w) ∈ Q × Σ*, where q is the current state and w is the unread part of the input. One move is

(q, aw) ⊢ (δ(q, a), w), for a ∈ Σ, w ∈ Σ*.

M accepts x iff (q₀, x) ⊢* (f, ε) for some f ∈ F. The initial configuration is (q₀, x).

DFA for strings having both 01 and 10 as substrings

A string contains both 01 and 10 exactly when it has at least three runs (blocks) of equal symbols, e.g. 010, 101, 0110, 1001. The DFA counts runs up to three.

States: q0 start; A0 = still in first run of 0's; A1 = first run of 1's; B1 = seen 01, now in 1's; B0 = seen 10, now in 0's; F = both found (final trap).

M = ({q0, A0, A1, B1, B0, F}, {0,1}, δ, q0, {F})

State01
→ q0A0A1
A0A0B1
A1B0A1
B1FB1
B0B0F
*FFF
        ┌─0─► A0 ─1─► B1 ─0─┐
 ──► q0 │                     ├─► ((F)) ↺0,1
        └─1─► A1 ─0─► B0 ─1─┘
 (A0↺0  A1↺1  B1↺1  B0↺0)

Verification

  • Accepted: 0110. (q0, 0110) ⊢ (A0, 110) ⊢ (B1, 10) ⊢ (B1, 0) ⊢ (F, ε). F is final. It contains 01 and 10.
  • Rejected: 0011. (q0, 0011) ⊢ (A0, 011) ⊢ (A0, 11) ⊢ (B1, 1) ⊢ (B1, ε). B1 is not final (no 10).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →