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.
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.
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|λ))|λ
And, finally, node 7
’s simplification, skipping a few steps:
7 = a(a(ab7)|b(ab)*(aaab7|bb7|λ))|λ
7 = aa(ab7)|ab(ab)*(aaab7|bb7|λ)|λ
7 = aaab7|ab(ab)*aaab7|ab(ab)*bb7|ab(ab)*λ|λ
7 = (aaab|ab(ab)*aaab|ab(ab)*bb)7|(ab(ab)*λ|λ)
7 = (aaab|ab(ab)*aaab|ab(ab)*bb)*(ab(ab)*λ|λ)
and the last node removal step, followed by removing λ
s.
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.
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.
Looking for comments…