--- title: "NDFA importance; two consecutive a or b" subject: "Theory of Computation" chapter: 2 key: "semester_3/theory_of_computation:ndfa-importance-consecutive" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/ndfa-importance-consecutive site: BCT Engineering --- # NDFA importance; two consecutive a or b Theory of Computation · Chapter 2: Finite Automata - Asked in: 2073 Chaitra - Video: [Lecture -26 NFA containing two consecutive zeros or two consecutive ones | By Neelis Galaxy](https://www.youtube.com/watch?v=1L-V1tgih_s) — Neeli's Galaxy - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/ndfa-importance-consecutive - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2 ## Question Why is NDFA important although it is equivalent to a DFA? Design an NDFA which accepts L = {w : w ∈ {a,b}* such that w contains either two consecutive a's or two consecutive b's}. ## Short answer NFA simplifies design and often uses fewer states than DFA. NFA for aa or bb: start q0, on a go to q0 and q1, on b to q0 and q2. q1 on a to q3, q2 on b to q3; q3 accepts with loops. Example: abba reaches q3; abab rejected. ## Answer #### Why NDFA is important Although every NFA can be converted to an equivalent DFA, NFAs are useful because: 1. **Easier design.** An NFA can "guess" (for example, where a pattern begins), so it is often much simpler to design than a DFA. 2. **Fewer states.** An NFA with n states may need up to 2ⁿ states as a DFA. For example, "the n-th symbol from the end is 1" needs n + 1 NFA states but 2ⁿ DFA states. 3. **Constructions are easy.** Union, concatenation, star and the conversion from regular expressions (Thompson's construction) are natural with NFAs and ε-moves. 4. **Theoretical tool.** Proofs of closure properties and Kleene's theorem are simpler with NFAs. Nondeterminism is also a key idea for more powerful models: nondeterministic PDAs are strictly more powerful than deterministic PDAs, and nondeterministic Turing machines (which are no more powerful than ordinary TMs) are used to define the class NP. #### NFA for strings containing aa or bb The NFA guesses where the two equal symbols begin. M = ({q0, q1, q2, q3}, {a, b}, δ, q0, {q3}) | State | a | b | |---|---|---| | → q0 | {q0, q1} | {q0, q2} | | q1 | {q3} | ∅ | | q2 | ∅ | {q3} | | *q3 | {q3} | {q3} | ```text a ┌──► q1 ──a──┐ ──► q0 │ ├──► ((q3)) ↻a,b ↻a,b └──► q2 ──b──┘ (q0 -a-> q1, q0 -b-> q2) ``` (q0 –a→ q1 –a→ q3 detects "aa"; q0 –b→ q2 –b→ q3 detects "bb"; q3 loops on a and b.) #### Test - "abba": q0 →a q0 →b q2 →b q3 →a q3 (final). Accepted, since it contains bb. - "abab": every path that leaves q0 for q1 or q2 dies on the next symbol (there is no aa or bb), so no path reaches q3 and the string is rejected. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Why are NFAs useful even though DFAs are equivalent? A. They accept more languages B. They are easier to design and may need far fewer states C. They never need ε-moves D. They are faster to run Answer: B. Equivalence in power, but simpler design and exponentially smaller in the worst case. (Key point: Why NFA) 2. Which language needs n+1 NFA states but 2^n DFA states? A. Strings with n zeros B. Strings of length n C. Strings ending in 1 D. The n-th symbol from the end is 1 Answer: D. A classic example. (Key point: State blowup) 3. How does the NFA for aa or bb work? A. It counts the a's and b's B. It reverses the input C. It reads the string twice D. It guesses where the two equal symbols begin Answer: D. q0 on a goes to {q0,q1}, then q1 on a goes to q3. (Key point: NFA design) 4. Why is abab rejected? A. q0 is not final B. It contains aa C. It has odd length D. No path reaches q3, as it has no aa or bb Answer: D. q1 and q2 die before q3. (Key point: Test) ## Related in Theory of Computation - [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 avoiding substring 10110](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-not-substring-10110) — Theory of Computation, chapter 2 - [Difference between DFA and NFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-nfa-difference) — Theory of Computation, chapter 2, asked 2× - [Convert NFA (q0,q1,q2) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-01-q0q2) — Theory of Computation, chapter 2 - [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: 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 ## Related in other subjects - [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× - [DFA with no three consecutive 0's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adfa-no-three-consecutive-zeros) — Discrete Structure, chapter 2 - [Equivalent Y-parameter of parallel two-ports](https://www.bctengineer.com/question.md?key=semester_3%2Felectrical_circuit_theory%3Aequivalent-y-parameter-parallel-two-ports) — Electrical Circuit Theory, chapter 7, asked 3× - [Equivalent Z-parameter of three series two-ports](https://www.bctengineer.com/question.md?key=semester_3%2Felectrical_circuit_theory%3Aequivalent-z-parameter-three-series-two) — Electrical Circuit Theory, chapter 7, asked 3×