Minimal dfa question


#1

construct a minimal dfa which accepts set of all string over {0,1,2} which when interpreted as terenary number(base 3 number) divisible by 5.


#2


in this link we found the answer for ternary strings divisible by number n.


#3

When you divide a number ω by n then reminder can be either 0, 1, …, (n - 2) or (n - 1). If remainder is 0 that means ω is divisible by n otherwise not. So, in my DFA there will be a state qr that would be corresponding to a remainder value r, where 0 <= r <= (n - 1), and total number of states in DFA is n.
After processing a number string ω over Σ, the end state is qr implies that ω % n => r (% reminder operator).

In any automata, the purpose of a state is like memory element. A state in an atomata stores some information like fan’s switch that can tell whether the fan is in ‘off’ or in ‘on’ state. For n = 5, five states in DFA corresponding to five reminder information as follows:

State q0 reached if reminder is 0. State q0 is the final state(accepting state). It is also an initial state.
State q1 reaches if reminder is 1, a non-final state.
State q2 if reminder is 2, a non-final state.
State q3 if reminder is 3, a non-final state.
State q4 if reminder is 4, a non-final state.

TD above is incomplete; and can only process strings of '0’s. Now add some more edges so that it can process subsequent number’s strings. Check table below, shows new transition rules those can be added next step:

┌──────┬──────┬─────────────┬─────────┐
│Number│Binary│Remainder(%5)│End-state│
├──────┼──────┼─────────────┼─────────┤
│One │1 │1 │q1 │
├──────┼──────┼─────────────┼─────────┤
│Two │10 │2 │q2 │
├──────┼──────┼─────────────┼─────────┤
│Three │11 │3 │q3 │
├──────┼──────┼─────────────┼─────────┤
│Four │100 │4 │q4 │
└──────┴──────┴─────────────┴─────────┘
To process binary string ‘1’ there should be a transition rule δ:(q0, 1)→q1
Two:- binary representation is ‘10’, end-state should be q2, and to process ‘10’, we just need to add one more transition rule δ:(q1, 0)→q2
Path: →(q0)─1→(q1)─0→(q2)
Three:- in binary it is ‘11’, end-state is q3, and we need to add a transition rule δ:(q1, 1)→q3
Path: →(q0)─1→(q1)─1→(q3)
Four:- in binary ‘100’, end-state is q4. TD already processes prefix string ‘10’ and we just need to add a new transition rule δ:(q2, 0)→q4
Path: →(q0)─1→(q1)─0→(q2)─0→(q4)

Five = 101
Above transition diagram in figure-2 is still incomplete and there are many missing edges, for an example no transition is defined for δ:(q2, 1)-?. And the rule should be present to process strings like ‘101’.
Because ‘101’ = 5 is divisible by 5, and to accept ‘101’ I will add δ:(q2, 1)→q0 in above figure-2.
Path: →(q0)─1→(q1)─0→(q2)─1→(q0)
Six = 110.

We can process ‘11’ in present TD in figure-3 as: →(q0)─11→(q3) ─0→(?). Because 6 % 5 = 1 this means to add one rule δ:(q3, 0)→q1.

Seven = 111

┌──────┬──────┬─────────────┬─────────┬────────────┬───────────┐
│Number│Binary│Remainder(%5)│End-state│ Path │ Add │
├──────┼──────┼─────────────┼─────────┼────────────┼───────────┤
│Seven │111 │7 % 5 = 2 │q2 │ q0─11→q3 │ q3─1→q2 │
└──────┴──────┴─────────────┴─────────┴────────────┴───────────┘
Nine = 1001

┌──────┬──────┬─────────────┬─────────┬──────────┬─────────┐
│Number│Binary│Remainder(%5)│End-state│ Path │ Add │
├──────┼──────┼─────────────┼─────────┼──────────┼─────────┤
│Nine │1001 │9 % 5 = 4 │q4 │q0─100→q4 │ q4─1→q4 │
└──────┴──────┴─────────────┴─────────┴──────────┴───────llL──┘

In TD-7, total number of edges are 10 == Q × Σ = 5 × 2. And it is a complete DFA that can accept all possible binary strings those decimal equivalent is divisible by 5.

Design DFA accepting Ternary numbers divisible by number n:

Step-1 Exactly same as for binary, use figure-1.

Step-2 Add Zero, One, Two

┌───────┬───────┬─────────────┬─────────┬──────────────┐
│Decimal│Ternary│Remainder(%5)│End-state│ Add │
├───────┼───────┼─────────────┼─────────┼──────────────┤
│Zero │0 │0 │q0 │ δ:(q0,0)→q0 │
├───────┼───────┼─────────────┼─────────┼──────────────┤
│One │1 │1 │q1 │ δ:(q0,1)→q1 │
├───────┼───────┼─────────────┼─────────┼──────────────┤
│Two │2 │2 │q2 │ δ:(q0,2)→q3 │
└───────┴───────┴─────────────┴─────────┴──────────────┘

Step-3 Add Three, Four, Five

┌───────┬───────┬─────────────┬─────────┬─────────────┐
│Decimal│Ternary│Remainder(%5)│End-state│ Add │
├───────┼───────┼─────────────┼─────────┼─────────────┤
│Three │10 │3 │q3 │ δ:(q1,0)→q3 │
├───────┼───────┼─────────────┼─────────┼─────────────┤
│Four │11 │4 │q4 │ δ:(q1,1)→q4 │
├───────┼───────┼─────────────┼─────────┼─────────────┤
│Five │12 │0 │q0 │ δ:(q1,2)→q0 │
└───────┴───────┴─────────────┴─────────┴─────────────┘

Step-4 Add Six, Seven, Eight

┌───────┬───────┬─────────────┬─────────┬─────────────┐
│Decimal│Ternary│Remainder(%5)│End-state│ Add │
├───────┼───────┼─────────────┼─────────┼─────────────┤
│Six │20 │1 │q1 │ δ:(q2,0)→q1 │
├───────┼───────┼─────────────┼─────────┼─────────────┤
│Seven │21 │2 │q2 │ δ:(q2,1)→q2 │
├───────┼───────┼─────────────┼─────────┼─────────────┤
│Eight │22 │3 │q3 │ δ:(q2,2)→q3 │
└───────┴───────┴─────────────┴─────────┴─────────────┘
Step-5 Add Nine, Ten, Eleven

┌───────┬───────┬─────────────┬─────────┬─────────────┐
│Decimal│Ternary│Remainder(%5)│End-state│ Add │
├───────┼───────┼─────────────┼─────────┼─────────────┤
│Nine │100 │4 │q4 │ δ:(q3,0)→q4 │
├───────┼───────┼─────────────┼─────────┼─────────────┤
│Ten │101 │0 │q0 │ δ:(q3,1)→q0 │
├───────┼───────┼─────────────┼─────────┼─────────────┤
│Eleven │102 │1 │q1 │ δ:(q3,2)→q1 │
└───────┴───────┴─────────────┴─────────┴─────────────┘

Step-6 Add Twelve, Thirteen, Fourteen

┌────────┬───────┬─────────────┬─────────┬─────────────┐
│Decimal │Ternary│Remainder(%5)│End-state│ Add │
├────────┼───────┼─────────────┼─────────┼─────────────┤
│Twelve │110 │2 │q2 │ δ:(q4,0)→q2 │
├────────┼───────┼─────────────┼─────────┼─────────────┤
│Thirteen│111 │3 │q3 │ δ:(q4,1)→q3 │
├────────┼───────┼─────────────┼─────────┼─────────────┤
│Fourteen│112 │4 │q4 │ δ:(q4,2)→q4 │
└────────┴───────┴─────────────┴─────────┴─────────────┘

Total number of edges in transition diagram figure-12 are 15 = Q × Σ = 5 * 3 (a complete DFA). And this DFA can accept all strings consist over {0, 1, 2} those decimal equivalent is divisible by 5.
If you notice at each step, in table there are three entries because at each step I add all possible outgoing edge from a state to make a complete DFA (and I add an edge so that qr state gets for remainder is r)!

To add further, remember union of two regular languages are also a regular. If you need to design a DFA that accepts binary strings those decimal equivalent is either divisible by 3 or 5, then draw two separate DFAs for divisible by 3 and 5 then union both DFAs to construct target DFA (for 1 <= n <= 10 your have to union 10 DFAs).

If you are asked to draw DFA that accepts binary strings such that decimal equivalent is divisible by 5 and 3 both then you are looking for DFA of divisible by 15 ( but what about 6 and 8?).

Note: DFAs drawn with this technique will be minimized DFA only when there is no common factor between number n and base e.g. there is no between 5 and 2 in first example, or between 5 and 3 in second example, hence both DFAs constructed above are minimized DFAs. If you are interested to read further about possible mini states for number n and base b read paper: Divisibility and State Complexity.