The language of every DFA is described by a regular expression.

This post depends on earlier posts about NFAs and Regular Expressions. It will not make sense without them.

From DFA to Regular Expression

Creating a regular expression from a DFA works by pieces. First, we create an partial regular expression for each node. For example, if node 1 transitions to node 2 on a a and transitions to node 3 on a b we write 1 = a2|b3. We also use a special symbol λ to represent accepting states, so if 1 was an accepting state we’d have 1 = a2|b3|λ.

Once we have all of the node’s partial regular expressions we repeatedly select one that isn’t a starting state and remove it. To do this, we observe the following identities.

x|y ≡ y|x. This is known as the commutative property.
x|y|z ≡ x|(y|z). This is known as the associative property.
x|(wy|wz) ≡ xw|(y|z). This is known as the distributive property.
1 = x1|y ≡ 1 = x*y. This is known as Arden’s rule.

To remove a node i we use the above identities to remove i from its own partial regular expression (if needed). This cannot be done if all of the parts of i’s partial regular expression end with i; in that case, i is a dead-end state and any rule or part thereof that includes i can simply be removed. We then replace every occurrence of i in other rules with i’s partial regular expression.

Once we have remove all nodes except the start node we remove all λ from the partial regular expression of the start node to obtain the answer.

Example

We now work through an example.

We first write down all of the partial regular expressions:

1 = a2|b4
2 = a3|b5
3 = a6|b4
4 = a4|b4
5 = a2|b6|λ
6 = a4|b7
7 = a2|b4|λ

We now start removing each state other than 1. The order doesn’t matter; we’ll simply work from 2 down to 7.

Since 2’s partial regular expression does not contain 2 we can simply replace 2 with its partial regular expression.

1 = a(a3|b5)|b4
3 = a6|b4
4 = a4|b4
5 = a(a3|b5)|b6|λ
6 = a4|b7
7 = a(a3|b5)|b4|λ

Likewise 3’s partial regular expression does not contain 3.

1 = a(a(a6|b4)|b5)|b4
4 = a4|b4
5 = a(a(a6|b4)|b5)|b6|λ
6 = a4|b7
7 = a(a(a6|b4)|b5)|b4|λ

We rearrange 4’s partial regular expression to be 4 = (a|b)4 and then discover it always ends in itself 4, so we eradicate it.

1 = a(a(a6)|b5)
5 = a(a(a6)|b5)|b6|λ
6 = b7
7 = a(a(a6)|b5)|λ

We rearrange 5’s partial regular expression in several steps
5 = a(a(a6)|b5)|b6|λ
5 = aa(a6)|ab5|b6|λ
5 = aaa6|ab5|b6|λ
5 = ab5|aaa6|b6|λ
5 = ab5|(aaa6|b6|λ)
5 = (ab)*(aaa6|b6|λ)
and then substitute it into the other partial regular expressions.

1 = a(a(a6)|b(ab)*(aaa6|b6|λ))
6 = b7
7 = a(a(a6)|b(ab)*(aaa6|b6|λ))|λ

Node 6 is trivial,

1 = a(a(ab7)|b(ab)*(aaab7|bb7|λ))
7 = a(a(ab7)|b(ab)*(aaab7|bb7|λ))|λ

1 = a(a(ab(aaab|ab(ab)*aaab|ab(ab)*bb)*(ab(ab)*λ|λ))|b(ab)*(aaab(aaab|ab(ab)*aaab|ab(ab)*bb)*(ab(ab)*λ|λ)|bb(aaab|ab(ab)*aaab|ab(ab)*bb)*(ab(ab)*λ|λ)|λ))

a(a(ab(aaab|ab(ab)*aaab|ab(ab)*bb)*(ab(ab)*)?)|b(ab)*(aaab(aaab|ab(ab)*aaab|ab(ab)*bb)*(ab(ab)*)?|bb(aaab|ab(ab)*aaab|ab(ab)*bb)*(ab(ab)*)?)?)

The result is ugly, but it is accurate. There are simpler regular expressions possible; for example, a(ab)*(bbba)*(aaba)*(aa|bb)?b. How to find a minimal regular expression is a topic for another post.

Thus, NFA = DFA = Regular Expression

Combining this result with part 1 and the equivalence of NFAs and DFAs, the set of languages an NFA can recognize is the same as the set of languages an DFA can recognize is the same as the set of languages a regular expression can describe.

This kind of equivalence is the basis of much of computability theory. There are many groupings of machines and descriptions, with the most commonly discussed being those in the Chomsky Hierarchy. We’ll explore more about why these matter in future posts.