Cardinal Path’s response to COVID-19 Cardinal Path is sharing all we know to help marketers during COVID-19.  Learn more.

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:

DFA 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.

Conversion of DFA into GNFA, and removal of q0 state

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:

Removing the q1 state

Finally, removing the q2 state:

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

Sharing is caring!

Popular

COVID-19 Crisis Navigator​

In partnership with Dentsu, Cardinal Path helps you distill the overwhelming news and information into a bi-weekly report highlighting emerging trends and insights during the pandemic.

EXPLORE THE REPORT

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

Message Sent

Success!
Your message was received.

Thank you.

Message Sent

Thank you.

Message Sent

Thank you

Message Sent

Thank you.

Message Sent

Thank you

Message Sent

Thank you

Message Sent

Thank you.

Message Sent

Thank you.

Message Sent

Thank you for registering.

Message Sent

Thank you.

Click here to download access the tool.

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

2020 Online Behavior Live Dashboard

Message Sent

Thank you for registering.

Thank you for your submission.

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

Message Sent

Thank you for your submission.

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

Thank you for registering.

Cardinal Path is continuing with its series of free training. Next we are conducting training on Google Data Studio. Check it out here.
Cardinal Path hosted a live session to connect with you and answer all your questions on Google Analytics.
Get all the expertise and none of the consultancy fees in this not-to-be-missed, rapid-fire virtual event.

Thank you for submitting the form.

Thank you for submitting the form.

Message Sent

Thank you for registering.

Message Sent

Thank you for registering.

Message Sent

Success! Thank you
for reaching out.