Regex to automata and back

Why it exists

Regular expressions, DFAs and NFAs describe the same class of languages (Kleene's theorem). The proof is two algorithms: a regular expression is turned into an automaton (this is how a scanner generator works) and an automaton into a regular expression (this is how GATE asks "write the expression for this DFA"). The state counts of the constructions are standard exam facts.

Prerequisites

You need regular expressions (regular expressions) and the subset construction (subset construction); the final DFA is usually minimised (DFA minimisation).

Precise definitions

Kleene's theorem. For a language $L$ the following are equivalent: $L$ is the language of a DFA; of an NFA; of an $\varepsilon$-NFA; of a regular expression.

Chain of constructions:

$\text{regular expression} \xrightarrow{\text{Thompson}} \varepsilon\text{-NFA} \xrightarrow{\text{subset construction}} \text{DFA} \xrightarrow{\text{state elimination or Arden}} \text{regular expression}.$

Thompson's construction builds, by induction on the expression, an $\varepsilon$-NFA $N(r)$ with these properties: exactly one start state (no edge enters it) and exactly one accepting state (no edge leaves it) and at most two edges leaving any state.

• $N(\varepsilon)$: start $\xrightarrow{\varepsilon}$ accept. $N(a)$: start $\xrightarrow{a}$ accept. $N(\emptyset)$: two states, no edge.
• Union $r \mid s$: a new start state with $\varepsilon$ edges to the starts of $N(r)$ and $N(s)$; $\varepsilon$ edges from their accepting states to a new accepting state.
• Concatenation $rs$: an $\varepsilon$ edge from the accepting state of $N(r)$ to the start state of $N(s)$ (the variant used here; some books identify the two states instead, which saves a state).
• Star $r^*$: a new start and a new accepting state; $\varepsilon$ edges new start $\to$ start of $N(r)$, accepting of $N(r)$ $\to$ new accepting, new start $\to$ new accepting (zero copies), accepting of $N(r)$ $\to$ start of $N(r)$ (repeat).

Size. $N(r)$ has at most twice as many states as $r$ has symbols and operators, and at most twice as many transitions; the NFA is linear in the length of the expression (checked on 300 random expressions).

How it works

The three building blocks

The union machine for $a \mid b$ has $6$ states: the new start, the two machines ($2$ states each) and the new accepting state. Run it on $b$: the closure of the start contains both branches; the $b$ branch moves, and the closure after the move reaches the accepting state.

Concatenation $ab$ has $4$ states: the two-state machines of $a$ and $b$ joined by an $\varepsilon$ edge.

The star $a^*$ has $4$ states: the extra $\varepsilon$ edge start $\to$ accept lets the empty string through, and the back edge allows repeated $a$'s.

A full example: $a (b \mid c)^*$

The construction has $10$ states: $2$ for the first $a$, $6$ for the union $b \mid c$ (two for $b$, two for $c$, a new start and a new accepting state), and $2$ more for the start and accepting states of the star; the concatenation adds only an $\varepsilon$ edge. Running it on $abcb$ keeps a small set of states active at every step, which is the NFA behaviour that the subset construction turns into a DFA.

For a feel of the sizes (computed with the construction above): the NFA, the DFA from the subset construction and the minimal DFA have

(The counts of DFA states include the dead state when the language needs one. Other textbooks give other NFA sizes because their rule for concatenation or star differs, for example by identifying states in a concatenation; the quantity GATE asks, the minimal DFA, does not depend on the variant.)

From a DFA to a regular expression: state elimination

1. Add a new start state $S$ with an $\varepsilon$ edge to the old start, and a new accepting state $F$ with $\varepsilon$ edges from every old accepting state (make the old accepting states ordinary).
2. Label every edge with a regular expression; parallel edges are merged with $\mid$.
3. Remove the original states one at a time. To remove state $q$: for every pair of states $p \to q \to r$ add the label $(p \to q)\,(q \to q)^*\,(q \to r)$ to the edge $p \to r$ (joined with any edge already there; the loop term is omitted if $q$ has no loop).
4. When only $S$ and $F$ remain, the label of the edge $S \to F$ is the regular expression.

Worked on the DFA for "ends with $01$" ($q_0 \xrightarrow{1} q_0$, $q_0 \xrightarrow{0} q_1$, $q_1 \xrightarrow{0} q_1$, $q_1 \xrightarrow{1} q_2$, $q_2 \xrightarrow{0} q_1$, $q_2 \xrightarrow{1} q_0$, $q_2$ accepting) removing $q_2$, then $q_0$, then $q_1$:

The result is $1^* 0 (0 \mid 10 \mid 1 1 1^* 0)^* 1$; verified equal to the DFA on all strings up to length $12$. A different elimination order gives a different expression: for this DFA the six orders gave six different expressions, all equivalent. The expression is not unique and not automatically short; the order matters.

Arden's rule

An equation system is simpler to solve by hand. Let $X_i$ be the set of strings that lead from the start to state $i$. For the DFA above:

$X_0 = \varepsilon \mid X_0 1 \mid X_2 1, \qquad X_1 = X_0 0 \mid X_1 0 \mid X_2 0, \qquad X_2 = X_1 1.$

Arden's rule. If $\varepsilon \notin A$, the equation $X = A X \mid B$ has the unique solution $X = A^* B$, and the mirror equation $X = X A \mid B$ has the unique solution $X = B A^*$. (If $\varepsilon \in A$ the solution is not unique, for example $A = \varepsilon$, $B = b$: both $\{b\}$ and every language containing $b$ solve $X = X \mid b$.) The paths-to-a-state system above has the symbols appended on the right, so the second form applies. Substitute $X_2$ into the others:

$X_1 = X_0 0 \mid X_1 (0 \mid 10) \Rightarrow X_1 = X_0 0 (0 \mid 10)^*, \qquad X_0 = \varepsilon \mid X_0 (1 \mid 0 (0 \mid 10)^* 1 1) \Rightarrow X_0 = (1 \mid 0 (0 \mid 10)^* 11)^*.$

The language of the DFA is $X_2 = X_1 1 = (1 \mid 0 (0 \mid 10)^* 11)^* \, 0 (0 \mid 10)^* \, 1$, again verified against the DFA on all strings up to length $12$.

Other methods

• Derivatives (Brzozowski). The derivative $r / a$ is the expression for $\{w : aw \in L(r)\}$; the distinct derivatives are the states of a DFA directly built from the expression (finitely many, if expressions are simplified).
• The formula $R_{ij}^{k}$. Strings from $i$ to $j$ using only intermediate states numbered at most $k$: $R_{ij}^{k} = R_{ij}^{k-1} \mid R_{ik}^{k-1} (R_{kk}^{k-1})^* R_{kj}^{k-1}$. It is state elimination written as a recurrence.

Size

Converting an expression to an NFA is linear. Converting a DFA to an expression can produce an expression of exponential length in the worst case (quoted, not proved here); that is why GATE gives small DFAs.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The scanner of a compiler is this pipeline (lexical analysis); closure properties are proved with these constructions (closure properties).

PYQs

Which one of the following regular expressions is
equivalent to the language accepted by the DFA given
below?

Let M be the 5-state NFA with ε-transitions shown in the
diagram below

Which one of the following regular expressions
represents the language accepted by M ?

Consider the following definition of a lexical token id for an
identifier in a programming language, using extended
regular expressions:
letter→[A-Za-z]
digit→[0-9]
id→letter(letter|digit)*
Which one of the following Non-deterministic
Finite-state Automata with - transitions accepts the
set of valid identifiers? (A double-circle denotes a
final state)

Consider the Deterministic Finite-state Automaton (DFA)
A shown below. The DFA runs on the alphabet {0, 1},
and has the set of states {s, p, q, r}, with s being the start
state and p being the only final state.

Which one of the following regular expressions
correctly describes the language accepted by A?

Which one of the following regular expression correctly
represents the language of the finite automata given
below?

Consider the alphabet Σ = {0, 1}, the null/empty string λ
and the sets of strings X0, X1 and X2 generated by the
corresponding grammar. X0, X1 and X2 are related as
follows :
X0 = 1X1
X1 = 0X1 + 1X2
X2 = 0X1 + {λ}
Which of the following choices precisely represents the
strings in X0?

Which of the regular expressions given below represent
the following DFA?

I)0*1(1+00*1)*
II)0*1*1+11*0*1
III) (0+1)*1

Match the following NFAs with the regular expressions
they correspond to:

1. ε + 0(01*1 + 00)*01*
2. ε + 0(10*1 + 00)*0
3. ε + 0(10*1 + 10)*1
4. ε + 0(10*1 + 10)*10*

Consider the following Finite State Automaton:

The language accepted by this automaton is given by the
regular expression

Consider the regular expression
 R = (a + b)*(aa + bb)(a + b)*
Which of the following non-deterministic finite
automata recognizes the language defined by the
regular expression R?
Edges labelled λ denote transitions on the empty
string.

Consider the regular expression R = (a + b)*(aa + bb)(a + b)*
Which deterministic finite automaton accepts the
language represented by the regular expression R ?

Self-check

Revision card

References