CODEWITHSUNDEEP
theoryregular-languagefinite-automatadfaautomata
trama
trama

Reputation: 1401

How to design a DFA for the following language?

How do I go about designing a DFA for:

Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

set of decimal digits.

L = {w| The decimal number represented by w leaves an odd remainder when divided by seven.}

So far, I have (hand) drawn out seven states (q0 - q6), with the odd number of q states being accepting.

Where do I go from here?

Upvotes: 2

Views: 1121

Answers (1)

templatetypedef
templatetypedef

Reputation: 372664

I would construct this in two steps:

  1. Construct a DFA whose states keep track of the remainder of w when divided by seven. You can do this by constructing states 0, 1, 2, 3, ..., 6 and linking them as follows: if w leaves a remainder of r when divided by 7 and the next digit is d, then you want to end up in the state corresponding to 10r + d (mod 7). This will give ten outgoing links from each state. It will be annoying to compute these links, but you only have to do it once.

  2. Mark states 1, 3, and 5 as accepting and everything else as rejecting.

Hope this helps!

Upvotes: 1

Related Questions