Regular Expression to Determine if a Base 10 Number is Divisible by 5

The Problem:

Let L = { w | w mod 5 = 0 }, where the alphabet is {0,1,2,3,4,5,6,7,8,9}; give the DFA for L, and convert this in to a regular expression.

The Solution:

The DFA ( S, Σ, T, s, A ):
S = {q0,q1}
Σ = {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 alphbet, Σ, into:

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

The state diagram:

Now to convert the DFA state diagram into a regular expression. This is done by converting the DFA into GNFA, and then converting the GNFA into a Regular Expression.

Finally, removing the q1 state:

Therefore the Regular Expression that defines the Regular Language L is:
A∪B(B∪A+B)*A+

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