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

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}

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

Popular Posts

The Emergence of Digital Continents is Driving a Paradigm Shift in Measurement

Popular Categories
Our Picks

Where Are You on the Path to Accelerated Digital Transformation?

Popular Tags

Your one-stop-shop for everything Google Marketing Platform, designed to help marketers stay informed and up-to-date on product news, solutions, how-toâ€™s, and more.