Construct a DFA for the Regular Expression $r = 0^*1^*2^*$

Construct a DFA for the Regular Expression $r = 0^1^2^*$

Verified Sources

Nov 3, 2026

We want a DFA for the language denoted by the regular expression $r = 0^*1^*2^*$ , i.e., all strings over $\Sigma=\{0,1,2\}$ that consist of some number of 0s, followed by some number of 1s, followed by some number of 2s, in that order (and with any of the three blocks possibly empty). This is a standard DFA-design pattern: keep track of which “phase” of the input you’re currently in, and once you move to a later phase you can never go back.

Key DFA notions used below: DFA , Transition function , Accepting state , Sink (dead) state.

RE to DFA (Thompson + Subset Construction) — background video

Language characterization

Let $L = \mathcal{L}(0^*1^*2^*)$ . Then

L=\{\,0^i1^j2^k \mid i,j,k\ge 0\,\}.

Equivalently:

If you ever see a $1$ after a $2$ , the string must be rejected (order violation).
If you ever see a $0$ after a $1$ or $2$ , the string must be rejected (order violation).
If you’re still in the “allowed region” (only $0$ s, then only $1$ s, then only $2$ s), you accept at the end of the input.

This matches the general idea behind building automata from regular languages: regular expressions correspond to finite automata, and conversion techniques often go via NFA + subset construction, but here a direct DFA is simpler and minimal for the structure $0^*1^*2^*$ .

Regular Expressions (CS103 lecture PDF) - Explains conversions between regex, NFA, DFA; highlights equivalence. ↩

Direct DFA construction intuition (3 phases + dead state)

Use one state per phase:

Phase 0: “still consuming $0^*$ ”
Phase 1: “now consuming $1^*$ ”
Phase 2: “now consuming $2^*$ ”
Dead state: “order already violated”

A DFA must be deterministic, so for each phase state and each input symbol, define exactly one next state.

Build the DFA for $0^1^2^*$

1
Step 1
Take $\Sigma = \{0,1,2\}$ (if your course assumes a different alphabet, add any missing symbols to the dead-state transitions).
2
Step 2
Let $Q = \{q_0,q_1,q_2,q_d\}$ where: $q_0$ = phase for $0^*$ , $q_1$ = phase for $1^*$ , $q_2$ = phase for $2^*$ , and $q_d$ = dead/sink state.
3
Step 3
Set the start state $s=q_0$ (before reading anything, we are in the $0^*$ block).
4
Step 4
The regex allows any $i,j,k\ge 0$ , so strings can end after finishing any prefix phase: accept in $q_0,q_1,q_2$ . Thus $A=\{q_0,q_1,q_2\}$ .
5
Step 5
From $q_0$ : on input $0$ stay in $q_0$ ; on input $1$ move to $q_1$ ; on input $2$ move to $q_2$ (because $1^*$ can be empty).
6
Step 6
From $q_1$ : on $1$ stay in $q_1$ ; on $2$ move to $q_2$ (since the $0^*$ block is over); on $0$ go to dead $q_d$ (order violation).
7
Step 7
From $q_2$ : on $2$ stay in $q_2$ ; on input $0$ or $1$ go to dead $q_d$ (since no symbols other than $2$ are allowed after the $2^*$ block starts).
8
Step 8
From dead $q_d$ : on any input in $\Sigma$ stay in $q_d$ .
9
Step 9
Report $D=(Q,\Sigma,\delta,s,A)$ with the transition table in the next block.

DFA definition (transition table)

Let $D=(Q,\Sigma,\delta,s,A)$ where:

$Q=\{q_0,q_1,q_2,q_d\}$
$\Sigma=\{0,1,2\}$
$s=q_0$
$A=\{q_0,q_1,q_2\}$
The transition function $\delta$ is:

State	on 0	on 1	on 2
$q_0$	$q_0$	$q_1$	$q_2$
$q_1$	$q_d$	$q_1$	$q_2$
$q_2$	$q_d$	$q_d$	$q_2$
$q_d$	$q_d$	$q_d$	$q_d$

This satisfies the DFA requirement that there is exactly one transition for each state-symbol pair.

Definition of Deterministic Finite Automata (DFA definitions) - Defines DFA components and transition tables/diagrams. ↩

Visual state diagram (Mermaid)

Acceptance: inputs ending in $q_0,q_1,q_2$ are accepted; those ending in $q_d$ are rejected.

type="tip" title="Pro Tip: interpret $0^*1^*2^*$ as ordered blocks" content="Treat each regex factor ( $0^*$ , then $1^*$ , then $2^*$ ) as a phase. Your DFA’s state should encode “which phase we are in,” and any symbol that would move you backwards in phase must go to the dead state."

type="warning" title="Beware the alphabet assumption" content="If your DFA’s alphabet is larger than $\{0,1,2\}$ , then every extra symbol must also transition to the dead state, since the regex restricts the string to only 0s, 1s, and 2s."

Correctness sketch (why this DFA matches the regex)

Define the invariant: after reading any prefix $w$ :

If the DFA is in $q_0$ , then $w$ is of the form $0^i$ .
If the DFA is in $q_1$ , then $w$ is of the form $0^i1^j$ .
If the DFA is in $q_2$ , then $w$ is of the form $0^i1^j2^k$ .
If the DFA is in $q_d$ , then $w$ contains an order violation (a $0$ after a $1$ or $2$ , or a $1$ after a $2$ ).

The transition rules preserve this invariant by construction:

Moving from $q_0$ to $q_1$ on $1$ matches starting the $1^*$ block.
Moving from $q_1$ to $q_2$ on $2$ matches starting the $2^*$ block.
Any backwards symbol forces $q_d$ , matching that the regex does not allow reordering. Finally, accepting states are exactly those phases where the input can legally end.

Conceptual workflow for this DFA

Parse the ordered blocks

Recognize the pattern $0^*1^*2^*$ as three consecutive phases."

Create one state per phase

Use $q_0,q_1,q_2$ for $0^*,1^*,2^*$ ."

Add a dead state for violations

All out-of-order inputs go to $q_d$ ."

Mark accepting phases

Accept in any phase where the input may legally end."

Phase transitions summary

Allowed next symbols from each phase state (others go to dead).

FAQ: common edge cases

Knowledge Check

Question 1 of 4

Q1Single choice

In the DFA construction for $0^*1^*2^*$ , which set of states should be accepting?

$\{q_0,q_1,q_2\}$

$\{q_0\}$

$\{q_2\}$

$\{q_0,q_d\}$

Explore Related Topics

Constructing an LALR(1) Parsing Table for a Given Grammar (and Proving It Is Not SLR(1))

Language Theory: Interpreting the Regular Expression $(a \mid b)^*$

Convert an NFA to a DFA (Subset Construction) and Describe the Accepted Language

Browse all research articles

Construct a DFA for the Regular Expression r=0∗1∗2∗r = 0^*1^*2^*r=0∗1∗2∗