--- title: "Configuration of DFA; DFA with 01 and 10" subject: "Theory of Computation" chapter: 2 key: "semester_3/theory_of_computation:dfa-config-01-and-10" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-config-01-and-10 site: BCT Engineering --- # Configuration of DFA; DFA with 01 and 10 Theory of Computation · Chapter 2: Finite Automata - Asked in: 2073 Shrawan - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-config-01-and-10 - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2 ## Question 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. ## 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. ## Answer #### 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}) | State | 0 | 1 | |---|---|---| | → q0 | A0 | A1 | | A0 | A0 | B1 | | A1 | B0 | A1 | | B1 | F | B1 | | B0 | B0 | F | | *F | F | F | ```text ┌─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). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does a configuration (instantaneous description) of a DFA consist of? A. The current state and the unread part of the input B. The set of all final states and the input alphabet C. The current state and the stack contents D. The start state and the complete input string only Answer: A. A configuration is a pair (q, w) where q is the current state and w is the unread input. (Key point: DFA configuration) 2. A string contains both 01 and 10 as substrings exactly when it has: A. At least two runs of equal symbols B. At least three runs of equal symbols C. An even number of runs D. Equal numbers of 0s and 1s Answer: B. Seeing both 01 and 10 needs two symbol changes, which means at least three runs (e.g. 010, 101). (Key point: Strings with both 01 and 10) 3. In the designed DFA, why does state F loop to itself on both 0 and 1? A. Because F is the dead state and no string can be accepted from it B. Because F is the start state C. Because once both 01 and 10 have been seen, any further input keeps the string accepted D. Because F counts the number of 0s modulo 2 Answer: C. F means both substrings are already found, so any suffix keeps the string in L. (Key point: Final trap state) 4. Why is 0011 rejected by the DFA? A. It ends in state A0 B. It contains no 0 C. It contains 10 but not 01 D. It contains 01 but no 10, so it ends in the non-final state B1 Answer: D. 0011 has only one change (0 to 1), so the run ends in B1, which is not final. (Key point: Verification by trace) ## Related in Theory of Computation - [DFA for (a(ab)*b)*](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-re-a-ab-star-b) — Theory of Computation, chapter 2 - [DFA starts or ends with 01](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-starts-or-ends-01) — Theory of Computation, chapter 2 - [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 - [DFA avoiding substring 10110](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-not-substring-10110) — Theory of Computation, chapter 2 - [DFA: even 0s and even 1s](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-even-zeros-even-ones) — Theory of Computation, chapter 2 - [PDA configuration; PDA for a^(3n)b^n](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-config-a3n-bn) — Theory of Computation, chapter 3 ## Related in other subjects - [String insulator configuration and advantages](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Astring-insulator-configuration) — Transmission and Distribution System Design, chapter 3 - [400 kV lines: configuration, V-string, earth wires](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Ajustify-400kv-config-vstring-earthwire) — Transmission and Distribution System Design, chapter 4 - [Sallen-Key LPF at 10 kHz, largest C 0.01 μF](https://www.bctengineer.com/question.md?key=semester_5%2Ffilter_design%3Asallen-key-10khz-largest-capacitance) — Filter Design, chapter 6 - [Settling tank 30 m x 3 m, 0.02 mm at 25°C; 0.01 mm at 10°C](https://www.bctengineer.com/question.md?key=semester_5%2Fwater_supply_engineering%3Ased-as70) — Water Supply Engineering, chapter 6, asked 3×