---
title: "DFA for {00}*{11}* language"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:dfa-00-star-11-star"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-00-star-11-star
site: BCT Engineering
---

# DFA for {00}*{11}* language

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2072 Kartik
- Video: [✅ DFA that Accepts {00}*{11}*|Automata Exam Problem Solved | No. of “00” followed by any No. of “11”](https://www.youtube.com/watch?v=iDDCOeC_UYA) — Dr. Insightful
- 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-00-star-11-star
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

Design a DFA accepting strings over the alphabet {0,1} defined by {00}*{11}*. [Printed expression unclear in scan.]

## Short answer

The DFA has states q0 (even 0s, no 1s, final), q1 (odd 0s), q3 (odd 1s), q2 (even 1s, final), and dead state d. Transitions: q0-0->q1, q1-0->q0, q0-1->q3, q3-1->q2, q2-1->q3; any 0 after a 1 or 1 after odd 0s goes to d.

## Answer

**Reading of the question.** The scan is unclear; we take the language L = {00}*{11}* = (00)*(11)*, i.e. an even number of 0's followed by an even number of 1's (the blocks are 00 and 11). The method is the same for similar expressions.

**Idea.** Phase 1 reads pairs of 0's; phase 2 reads pairs of 1's; after any 1 is read, a 0 is not allowed.

States:
- q0: even number of 0's read, no 1 yet (start, final)
- q1: odd number of 0's read
- q3: in the 1-phase with an odd number of 1's read
- q2: in the 1-phase with an even number (≥ 2) of 1's read (final)
- d: dead state

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

| State | 0 | 1 |
|---|---|---|
| → *q0 | q1 | q3 |
| q1 | q0 | d |
| q3 | d | q2 |
| *q2 | d | q3 |
| d | d | d |

```text
 Phase 1 (pairs of 0):   ((q0)) <--0--> (q1)    q1 --1--> d
 Phase 2 (pairs of 1):   q0 --1--> (q3) <--1--> ((q2))
                         q3, q2 --0--> d
 d loops on 0,1.   Start: q0.   Finals: q0, q2.
```

Edges: q0 –0→ q1, q1 –0→ q0, q0 –1→ q3, q3 –1→ q2, q2 –1→ q3. All other moves go to d (e.g. q1 –1→ d, q2 –0→ d, q3 –0→ d).

#### Test
- "0011": q0 → q1 → q0 → q3 → q2, final. Accepted.
- "00": q0 → q1 → q0 final, accepted. ε is accepted too.
- "011": q0 → q1 → d. Rejected (odd 0's).
- "1100": q0 → q3 → q2 → d → d. Rejected (0 after 1).

## Check yourself

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

1. What strings does {00}*{11}* describe?
   A. Any number of 0s followed by any number of 1s
   B. An even number of 0s followed by an even number of 1s
   C. Strings with equal numbers of 0s and 1s
   D. Strings with 00 or 11 as a substring
   Answer: B. Each block is a pair, so the string is (00)* followed by (11)*: even 0s then even 1s. (Key point: Language meaning)

2. Which states are final in the DFA?
   A. q0 and q2
   B. q2 only
   C. q1 and q3
   D. q0 only
   Answer: A. q0 accepts the empty string and even 0s only; q2 accepts even (at least 2) 1s after the 0s. (Key point: Final states)

3. Why does q3 on input 0 go to the dead state d?
   A. Because an odd number of 1s is allowed to be followed by 0
   B. Because q3 is final
   C. Because a 0 is not allowed once a 1 has been read
   D. Because 0 resets the count
   Answer: C. After the first 1 the string is in the 1-phase, so any 0 makes it impossible to match (00)*(11)*. (Key point: Dead state use)

4. Why is 011 rejected?
   A. It has too many 1s
   B. The 1 read in q1 (odd number of 0s) sends the machine to d
   C. It starts with 0
   D. q3 is not final
   Answer: B. After one 0 the machine is in q1, and a 1 there goes to the dead state. (Key point: Rejecting odd 0s)

## 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: 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
- [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
- [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 (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
- [TM accepting wwᴿ; process 101101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-accept-wwr-101101) — Theory of Computation, chapter 4

## Related in other subjects

- [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2
- [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
- [Design FSA accepting even number of a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-even-number-of-a) — Discrete Structure, chapter 2, asked 4×
- [Design FSA accepting odd number of b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-odd-number-of-b) — Discrete Structure, chapter 2, asked 4×