Regular Expression to determine if a base 10 number is divisible by 3

I decided to work out the regular expression for matching mod3=0 positive decimal (base 10) integers today. I had a dream about the problem last night (remembering an old lecture) and could not find my notes with the solution (if I even wrote it down). So, after googling around for a bit, I gave up, and worked the solution out myself, because it looks like a good void to fill on the interwebs.

The Problem:

Let 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 (don't peak):

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.

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