Skip to main content

DFA for (a(ab)*b)*

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).

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

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})

Stateab
→ *s0s1d
s1s2s0
s2ds1
d (dead)dd
          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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →