Original posted on Erik Vold's Blog

## The Problem:

For the regular language *L* = { w | w mod 3 = 0 }, where the alphabet is {0,1,2,3,4,5,6,7,8,9}; give the deterministic finite automaton (DFA) for *L*, and convert this to a regular expression.

## The Solution:

The DFA ( *S*, Σ, *T*, *s*, *A* ):*S* = {q0,q1,q2}

Σ = {0,1,2,3,4,5,6,7,8,9}

T = (doing the state diagram below)*s* = {q0}*A* = {q0}

For shorthand I will divide the alphabet, Σ, into:

- A={0,3,6,9}
- B={1,4,7}
- C={2,5,8}

The state diagram:

Now to convert the DFA state diagram into a regular expression. This is done by converting the DFA into generalized non deterministic finite automaton (GNFA), and then converting the GNFA into a regular expression.

Notice in the above that I did two steps in one; I first converted the DFA into a GNFA (which is the easy part), then I removed the q0 state.

Removing the q1 state:

Finally, removing the q2 state:

Therefore the regular expression that defines the regular language *L* is:

(A+)∪((B∪A*B)(A∪CA*B)*CA*)∪((C∪A*C∪(B∪A*B)(A∪CA*B)*(B∪CA*C))(A∪BA*C∪(C∪BA*B)(A∪CA*B)*(B∪CA*C))*(BA*∪(C∪BA*B)(A∪CA*B)*CA*))

For further reading please see "Introduction to the Theory of Computation" by Michael Sipser