Technology Services

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

Cardinal Path

Share
Published by
Cardinal Path

Recent Posts

Optimizing user experiences with Digital Experience Analytics (DXA) platforms

As consumers become increasingly digitally savvy, and more and more brand touchpoints take place online,…

2 weeks ago

Enabling Value-Based Bidding with Google Tightlock

Marketers are on a constant journey to optimize the efficiency of paid search advertising. In…

4 weeks ago

Resolving “Unassigned” Traffic in GA4

Unassigned traffic in Google Analytics 4 (GA4) can be frustrating for data analysts to deal…

1 month ago

This website uses cookies.