---
title: "DFA starts or ends with 01"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:dfa-starts-or-ends-01"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-starts-or-ends-01
site: BCT Engineering
---

# DFA starts or ends with 01

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2074 Asoj
- Video: [Design DFA for Strings Starting with 01 or Ending with 01 | GATE CSE | TOC | Automata Theory](https://www.youtube.com/watch?v=og0jibdBKsY) — THE GATEHUB
- 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-starts-or-ends-01
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

What is the significance of finite automata? Design a DFA that accepts the strings over the alphabet Σ = {0,1} that either start with 01 or end with 01. Hence test your design for any two strings.

## Short answer

DFA for start with 01 or end with 01: states q0 (start), a (saw 0), F (trap for start-01), N (ends in 1), Z (ends in 0), E (ends in 01). Transition: q0-0→a, q0-1→N; a-0→Z, a-1→F; N-0→Z, N-1→N; Z-0→Z, Z-1→E; E-0→Z, E-1→N; F loops. Accept F, E. Example: '01110' → F; '1101' → E; '1100' → Z rejected.

## Answer

#### Significance of finite automata
- They are the simplest model of computation (a machine with finite memory) and define the **regular languages**.
- They are used in lexical analysers (tokenisers), text search and pattern matching, network protocols, hardware controllers and vending/traffic controllers.
- They are the base for studying more powerful machines (pushdown automata, Turing machines) and show what can be done with a fixed amount of memory.

#### DFA: strings that start with 01 or end with 01
**Idea.** After reading a prefix 01, accept everything (a final trap state F). Otherwise keep track of the "ends with 01" condition using three states:
- N: the last symbol is 1 (or nothing relevant yet),
- Z: the last symbol is 0,
- E: the last two symbols are 01 (final).

States: q0 (start), a (read "0" first), F (prefix 01 seen), N, Z, E.

M = ({q0, a, F, N, Z, E}, {0,1}, δ, q0, {F, E})

| State | 0 | 1 |
|---|---|---|
| → q0 | a | N |
| a | Z | F |
| *F | F | F |
| N | Z | N |
| Z | Z | E |
| *E | Z | N |

```text
 q0 ─0─► a ─1─► ((F)) ↻0,1
 │       └0─► Z
 └1─► N ─0─► Z ─1─► ((E))
      ↻1      ↻0        │0 -> Z
                        │1 -> N
 (N -1-> N, N -0-> Z, Z -0-> Z, Z -1-> E)
```

Edges: q0 –0→ a, q0 –1→ N, a –0→ Z, a –1→ F, N –0→ Z, N –1→ N, Z –0→ Z, Z –1→ E, E –0→ Z, E –1→ N, F loops.

#### Testing
- **"01110"** (starts with 01): q0 →0 a →1 F →1 F →1 F →0 F. Accepted.
- **"1101"** (ends with 01): q0 →1 N →1 N →0 Z →1 E. Accepted.
- **"1100"** (neither): q0 → N → N → Z → Z. Z is not final. Rejected.

## Check yourself

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

1. Which is an application of finite automata?
   A. Storing unbounded counts
   B. Parsing every context-free language
   C. Lexical analysers and pattern matching
   D. Solving all computable problems
   Answer: C. FAs are used in tokenisers, text search and controllers. (Key point: Significance)

2. What happens after reading the prefix 01?
   A. Go to the dead non-final state
   B. Go to trap final state F and accept everything
   C. Go to E
   D. Return to q0
   Answer: B. Any string starting with 01 is accepted. (Key point: Prefix 01)

3. What do states N, Z, E track?
   A. Parity of 1s
   B. Last symbol is 1, last symbol is 0, last two are 01
   C. Length mod 3
   D. Parity of 0s
   Answer: B. E is final when the string ends with 01. (Key point: Ends in 01)

4. What happens for 1100?
   A. Rejected in N
   B. Accepted in E
   C. Rejected in Z
   D. Accepted in F
   Answer: C. Neither starts nor ends with 01. (Key point: Test)

## Related in Theory of Computation

- [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 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: even a and odd b](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-even-a-odd-b) — Theory of Computation, chapter 2
- [Convert ε-NFA (q0..q4) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-epsilon-q4) — Theory of Computation, chapter 2, asked 2×
- [Convert NFA (q0..q4, 0/1) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-five-states) — 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

## Related in other subjects

- [Design NFA for strings ending with aba](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Anfa-strings-ending-aba) — Discrete Structure, chapter 2
- [Design FSA for strings beginning with baa](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-strings-beginning-baa) — Discrete Structure, chapter 2
- [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×
- [Differentiate Finite State Machine and Automata](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsm-vs-fsa-difference) — Discrete Structure, chapter 2, asked 2×