---
title: "DFA for (a(ab)*b)*"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:dfa-re-a-ab-star-b"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-re-a-ab-star-b
site: BCT Engineering
---

# DFA for (a(ab)*b)*

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2071 Chaitra
- Video: [Regular expression to DFA Conversion || Theory of computation](https://www.youtube.com/watch?v=05JR9n4O5UQ) — Institute Academy
- 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-re-a-ab-star-b
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

Design a DFA for the regular expression (a(ab)*b)*. Verify your design by taking one accepted and one rejected string.

## Short answer

DFA: states s0 (start/final), s1, s2, dead d. Transitions: s0-a→s1, s1-b→s0, s1-a→s2, s2-b→s1; others go to d. Accepts ε and zero or more blocks of a(ab)*b. Example: aabb (accepted by s0→s1→s2→s1→s0), aab (rejected, ends in s1).

## Answer

**Language.** (a(ab)*b)* is a repetition of blocks of the form a(ab)ᵏb, k ≥ 0: ab, aabb, aababb, ... Zero blocks (ε) is allowed.

**Idea.** s0 = at a block boundary (start and final). After the first a of a block we are in s1. In s1 we may close the block with b, or open an "ab" pair with a (going to s2), which must be finished by b (back to s1).

M = ({s0, s1, s2, d}, {a, b}, δ, s0, {s0})

| State | a | b |
|---|---|---|
| → *s0 | s1 | d |
| s1 | s2 | s0 |
| s2 | d | s1 |
| d (dead) | d | d |

```text
          a          a
 ──►((s0)) ───► (s1) ───► (s2)
        ◄─── b ──┘ ◄─── b ──┘
 (s0 -b-> d, s2 -a-> d, d loops on a,b)
```

Edges: s0 –a→ s1, s1 –b→ s0, s1 –a→ s2, s2 –b→ s1.

#### Verification
- **Accepted: aabb.** s0 →a s1 →a s2 →b s1 →b s0, which is final. (It is a(ab)b.)
- **Accepted: abab.** s0 → s1 → s0 → s1 → s0 (two blocks ab, ab).
- **Rejected: aab.** s0 → s1 → s2 → s1, and s1 is not final.
- **Rejected: ba.** s0 →b d, and d is not final.

## Check yourself

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

1. What strings does (a(ab)*b)* generate?
   A. Strings with equal a's and b's
   B. Only (ab)*
   C. Strings starting with a and ending with b
   D. Repetitions of blocks a(ab)^k b, including ε
   Answer: D. Blocks are ab, aabb, aababb, ... repeated zero or more times. (Key point: Language)

2. Why is s0 both start and final?
   A. Because the DFA has one state
   B. Because all strings are accepted
   C. Because the dead state is final
   D. ε is in the language (zero blocks)
   Answer: D. The star allows zero blocks. (Key point: Start state)

3. What happens on b from s0?
   A. Go to the dead state d
   B. Go to s2
   C. Go to s1
   D. Stay in s0
   Answer: A. A block must start with a, so b at a boundary is rejected. (Key point: Dead state)

4. What happens for aab?
   A. s0 → s1 → s2 → s1, not final, rejected
   B. It reaches the dead state
   C. It is accepted in s0
   D. It is accepted in s1
   Answer: A. s1 is not final, so aab is rejected. (Key point: Verification)

## 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
- [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
- [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 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 grammar to RE and FA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aregular-grammar-to-re-fa) — Theory of Computation, chapter 2
- [Every RE has NFA; ε-NFA for bb(a∪b)*ab](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-to-nfa-bb-aub-ab) — Theory of Computation, chapter 2

## Related in other subjects

- [Regular expression and FSA: at least three b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-at-least-three-b) — Discrete Structure, chapter 2
- [Design pipes AB and BC, A RL 210 m, 44 and 18 lps](https://www.bctengineer.com/question.md?key=semester_5%2Fwater_supply_engineering%3Apd-c73) — Water Supply Engineering, chapter 7
- [Design pipes AB, BC, AD (min pressure 1.1 kg/cm2)](https://www.bctengineer.com/question.md?key=semester_5%2Fwater_supply_engineering%3Apipe-design-ab-bc-ad-110) — Water Supply Engineering, chapter 7, asked 2×
- [Design pipes AB and BC, 75 lpcd, tank 6 m high](https://www.bctengineer.com/question.md?key=semester_5%2Fwater_supply_engineering%3Apd-b81) — Water Supply Engineering, chapter 7