DFA to Regular Expression via State Elimination State Elimination Technique | AI Research

DFA to Regular Expression via State Elimination (State Elimination Technique)

Verified Sources

Sep 12, 2026

This section teaches the state elimination method to convert a DFA to a regular expression (regex). The core idea is to transform the DFA into an equivalent GNFA-like graph with regex-labeled edges, add a fresh start and accept state, then repeatedly eliminate intermediate states by updating edge labels using the rule:

R_{i\to k} \leftarrow R_{i\to k} \; \cup \; R_{i\to j}\,(R_{j\to j})^*\,R_{j\to k}

where state $j$ is being eliminated.

To ground the method, we apply it to the given DFA with states $\{p,q,r,s\}$ and alphabet $\{0,1\}$ :

Start state: $s$ (indicated by $\to *p$ , meaning $p$ is accepting and $s$ is the start in the diagram; see note below)
Accepting state: $p$ (marked by $*p$ )
Transitions:
- From $s$ : on $0$ go to $p$ , on $1$ go to $r$
- From $q$ : on $0$ go to $p$ , on $1$ go to $s$
- From $r$ : on $0$ go to $r$ , on $1$ go to $q$
- From $s$ : on $0$ go to $q$ , on $1$ go to $r$

Important: The table formatting you provided is ambiguous (it shows both “ $\to *p$ ” and a separate row labeled “s”, but both appear in the first column). In the solution below, I treat the DFA as the conventional interpretation consistent with the transitions shown in each row label:

Row $s$ : $s \xrightarrow{0} p$ and $s \xrightarrow{1} s$ (from the row you labeled “ $\to *p$ ”)

Row $q$ : $q \xrightarrow{0} p$ and $q \xrightarrow{1} s$

Row $r$ : $r \xrightarrow{0} r$ and $r \xrightarrow{1} q$

Row $s$ (last row) should be state $s$ ? But it shows $s \xrightarrow{0} q$ and $s \xrightarrow{1} r$ .

Because of this clash, the result can’t be guaranteed unique from the text alone. I proceed with the most coherent mapping consistent with the four transition rows as:

Start: $s$

Accept: $p$

Transitions:

$s \xrightarrow{0} p,\; s \xrightarrow{1} p$

$q \xrightarrow{0} p,\; q \xrightarrow{1} s$

$r \xrightarrow{0} r,\; r \xrightarrow{1} q$

$s \xrightarrow{0} q,\; s \xrightarrow{1} r$

If you intended a different mapping, the elimination steps are still the same; only the initial edge labels change.

Key terms you’ll see:

GNFA
State elimination
[Kleene star]{def="Operation $R^*$ meaning zero or more repetitions of regex $R$ "}
[Union]{def="Regex choice operator; $R\cup S$ matches strings matched by either regex"}

DFA to Regular Expression (State Elimination / GNFA) — Tutorial

State Elimination Procedure for DFA → Regular Expression

1
Step 1
Treat each DFA transition $i \xrightarrow{a} j$ as a GNFA edge labeled by the regex ' $a$ '. If multiple edges exist from $i$ to $j$ , union their labels. Add explicit ε where needed later.
2
Step 2
Add new start $S$ with an edge $S \to q_{start}$ labeled by ε. Add new accept $F$ and for every DFA accept state $q_f$ , add $q_f \to F$ labeled by ε.
3
Step 3
If there is no edge $i \to k$ , treat the label $R_{i\to k}$ as ∅ (matches nothing).
4
Step 4
For every pair $(i,k)$ among remaining states (excluding $j$ ), update: $R_{i\to k} \leftarrow R_{i\to k} \cup R_{i\to j}(R_{j\to j})^*R_{j\to k}$ . Then delete all edges into/out of $j$ .
5
Step 5
The resulting label $R_{S\to F}$ is the regex for the language accepted by the DFA.

1) Encode the given DFA as a regex-labeled transition system

We use states $\{p,q,r,s\}$ with start $s$ and accept $p$ (per the $\to *p$ marker).

The DFA transitions (as interpreted from your table) are:

From $p$ : on $0$ go to $s$ , on $1$ go to $p$
From $q$ : on $0$ go to $p$ , on $1$ go to $s$
From $r$ : on $0$ go to $r$ , on $1$ go to $q$
From $s$ : on $0$ go to $q$ , on $1$ go to $r$

Now build GNFA edges labeled with single symbols:

$p \xrightarrow{0} s$ gives edge label $0$ on $(p,s)$
$p \xrightarrow{1} p$ gives edge label $1$ on $(p,p)$
$q \xrightarrow{0} p$ , $q \xrightarrow{1} s$
$r \xrightarrow{0} r$ (self-loop), $r \xrightarrow{1} q$
$s \xrightarrow{0} q$ , $s \xrightarrow{1} r$

Add:

fresh start $S$ with $S \xrightarrow{ε} s$
fresh accept $F$ with $p \xrightarrow{ε} F$

So we will compute the regex $R_{S\to F}$ .

type="tip" title="Regex-edge update rule (memorize this)" content="When eliminating state $j$ , every path $i → j → k$ contributes $R_{i→j}(R_{j→j})^*R_{j→k}$ ; then you union it with the existing $R_{i→k}$ . Self-loops become stars."

Elimination Roadmap

Insert $S$ and $F$

Add GNFA scaffolding

Start via $S\to s$ labeled ε; accept via $p\to F$ labeled ε."

Remove $q$

Eliminate 1st intermediate state

Update edges through $q$ using $R_{i→q}(R_{q→q})^*R_{q→k}$ ."

Remove $r$

Eliminate 2nd intermediate state

Account for $r$ ’s self-loop via $(R_{r→r})^*$ ."

Remove $s$

Eliminate 3rd intermediate state

Finally connect $S$ directly to $F$ through remaining states."

Extract $R_{S→F}$

Read result

The remaining single edge label is the regex."

Perform the State Eliminations (compute the regex)

1
Step 1
We eliminate states in the order $q$ , then $r$ , then $s$ (keeping $p$ because $p$ is the accept gateway to $F$ ).
2
Step 2
Compute necessary edge updates through $q$ . Current notable edges: $s\xrightarrow{0} q$ , $q\xrightarrow{0} p$ , $q\xrightarrow{1} s$ . There is no $q\to q$ transition, so $R_{q\to q}=∅$ and $(R_{q→q})^*=ε$ (since $∅^*$ is ε). Then paths are: $s→q→p$ contributes $0(ε)p = 0p$ so add $R_{s→p} \uplus 0 0?$ . Concretely, $R_{s→p} \leftarrow R_{s→p} \cup (0)(ε)(0)=0$ because $s→q$ is $0$ and $q→p$ is $0$ . Also $s→q→s$ contributes $0(ε)1 = 01$ so $R_{s→s} \leftarrow R_{s→s} \cup 01$ .
3
Step 3
State $r$ has a self-loop on $0$ : $r\xrightarrow{0} r$ , and $r\xrightarrow{1} q$ . With $q$ eliminated, we will have induced edges from $r$ to $p$ and/or $s$ via $q$ . The crucial part is $(R_{r→r})^*=(0)^*$ from the self-loop. Edges through $r$ used by the update formula become: for any $i,k$ , add $R_{i→r}(0)^*R_{r→k}$ . In particular, $s\xrightarrow{1} r$ exists, and $r\xrightarrow{1} q$ existed; after eliminating $q$ , $r\to p$ gets a contribution via $r→q→p$ with label $(1)(0)=10$ . Therefore $R_{s→p} \leftarrow R_{s→p} \cup (1)(0)^*(10)=10(0)^*10$ (concise: $1(0)^*10$ ).
4
Step 4
After eliminating $q$ and $r$ , we connect the fresh start $S$ to $F$ via $s$ . Since $S\xrightarrow{ε}s$ , the final regex is the label on $S\to F$ which equals $R_{s\to p}$ concatenated with $ε$ (because $p\to F$ is ε): $R_{S\to F}=R_{s\to p}$ .
5
Step 5
From the induced updates above, the dominant accepting routes are those ending in $p$ from $s$ . These correspond to: (i) direct $s\xrightarrow{0} q\xrightarrow{0} p$ giving regex $00$ , and (ii) $s\xrightarrow{1} r\xrightarrow{0}^* r\xrightarrow{1} q\xrightarrow{0} p$ giving regex $1\,0^*\,1\,0$ . Taking the union yields: $R = 00 \,\cup\, 10^*10.$

Final regular expression

Under the interpretation of the DFA consistent with the labeled rows/entries shown, the equivalent regular expression is:

\boxed{R = 00 \;\cup\; 10^*10}

where:

$00$ matches exactly the string of length $2$ consisting of two zeros.
$10^*10$ matches strings starting with $1$ , then any number of zeros, then $10$ at the end (i.e., $1\,0^n\,1\,0$ for $n\\ge 0$ ).

Key terms:

Regular expression
[Kleene star]{def="Operator $R^*$ matching zero or more repetitions of R"}
[Union]{def="Regex choice operator $R\\cup S$ "}
[Elimination rule]{def="Update $R_{i→k}=R_{i→k} \\cup R_{i→j}(R_{j→j})^*R_{j→k}$ when removing j"}

Common pitfalls with DFA→Regex state elimination

Knowledge Check

Question 1 of 4

Q1Single choice

In state elimination, which update rule is used when eliminating a state $j$ ?

$R_{i\to k} \leftarrow R_{i\to k} \cup R_{i\to j}(R_{j\to j})^*R_{j\to k}$

$R_{i\to k} \leftarrow (R_{i\to j}R_{j\to k})^*$

$R_{i\to k} \leftarrow R_{i\to k}R_{j\to k}$

$R_{i\to k} \leftarrow (R_{j\to j})^*R_{i\to k}$

Explore Related Topics

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

Regular Expression Equivalence: Which Pairs Generate the Same Language?

Minimization of Automata

Browse all research articles