---
title: "DFA avoiding substring 10110"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:dfa-not-substring-10110"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-not-substring-10110
site: BCT Engineering
---

# DFA avoiding substring 10110

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2073 Chaitra
- 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-not-substring-10110
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

Design a DFA that accepts the language L = {x : x ∈ {0,1}* and 10110 does not occur as a substring}. Verify your design with a supporting example.

## Short answer

DFA tracks the longest suffix that is a prefix of '10110'. States q0–q4 represent progress: q0 start, q1 after '1', q2 '10', q3 '101', q4 '1011'. On reading the full pattern, go to dead state d (non-final). Example: 1011 ends in q4 (accepted); 0101100 hits d (rejected).

## Answer

**Idea.** Use states q0..q4 to record the length of the longest suffix of the input read so far that is a prefix of 10110. If the whole pattern 10110 is seen, go to a dead (trap) state. All states except the dead state are final.

M = ({q0, q1, q2, q3, q4, d}, {0,1}, δ, q0, {q0, q1, q2, q3, q4})

Meaning: q0 = no progress; q1 = suffix "1"; q2 = "10"; q3 = "101"; q4 = "1011"; d = pattern found.

#### Transition table
| State | 0 | 1 |
|---|---|---|
| → *q0 | q0 | q1 |
| *q1 | q2 | q1 |
| *q2 | q0 | q3 |
| *q3 | q2 | q4 |
| *q4 | d | q1 |
| d | d | d |

Reasons for the less obvious moves:
- q1 on 1: input ends in "11"; the longest suffix that is a prefix is "1", so q1.
- q2 on 0: "100" has no suffix matching a prefix, so q0.
- q3 on 0: "1010" ends in "10", so q2.
- q4 on 1: "10111" ends in "1", so q1.
- q4 on 0 completes 10110, so d.

```text
    1        0        1        1        0
 q0 ──► q1 ──► q2 ──► q3 ──► q4 ──► d
 (all of q0..q4 are final; d is the trap)

 Back edges:  q0 ↻0     q1 ↻1     q2 -0-> q0
              q3 -0-> q2           q4 -1-> q1
              d ↻0,1
```

#### Verification
- **Accepted: 1011.** q0 →1 q1 →0 q2 →1 q3 →1 q4 (final). Also 101011: q0,q1,q2,q3,q2,q3,q4 (final); 10110 is not a substring.
- **Rejected: 0101100.** q0 →0 q0 →1 q1 →0 q2 →1 q3 →1 q4 →0 d →0 d, and d is not final (the string contains 10110).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does state qi track?
   A. The number of 1s read
   B. The last symbol read
   C. The longest suffix of the input that is a prefix of 10110
   D. The length mod 5
   Answer: C. States 0..4 are matched-prefix lengths. (Key point: State meaning)

2. Which states are final?
   A. All except the trap state d
   B. Only q4
   C. Only d
   D. Only q0
   Answer: A. We accept strings that never contain 10110. (Key point: Final states)

3. Why does q3 on 0 go to q2?
   A. Because 1010 contains the pattern
   B. Because it restarts at q0
   C. Because 1010 ends with 1
   D. 1010 ends with 10, a prefix of the pattern
   Answer: D. The longest matching suffix is 10. (Key point: Back edge)

4. What does q4 on 0 do?
   A. Go to q2
   B. Go to q1
   C. Go to q0
   D. Completes 10110 and goes to the dead state
   Answer: D. Pattern complete, so d which loops forever. (Key point: Trap)

## Related in Theory of Computation

- [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
- [Regular expression with substring 0101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-substring-0101) — Theory of Computation, chapter 2
- [Configuration of DFA; DFA with 01 and 10](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-config-01-and-10) — 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 (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

- [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
- [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
- [Interpret: book for second-language readers](https://www.bctengineer.com/question.md?key=semester_5%2Fcommunication_english%3Ainterpret-book-for-second-language-readers) — Communication English, chapter 1
- [Principles of mix design; factors not in DOE](https://www.bctengineer.com/question.md?key=semester_5%2Fconcrete_technology_and_masonry_structure%3Amix-design-principles-doe-omitted) — Concrete Technology and Masonry Structure, chapter 3