regex - Design DFA accepting binary strings divisible by a number 'n'

Question

I need to learn how to design a DFA such that given any number 'n', it accepts binary strings {0, 1} whose decimal equivalent number is divisible by 'n'.

There will be different DFAs for different 'n', but can somebody give a basic approach that I should follow to proceed with any number 0 < n < 10 .

Answer 1

Below, I have written an answer for n equals to 5, but you can apply same approach to draw DFAs for any value of n and 'any positional number system' e.g binary, ternary...

First lean the term 'Complete DFA', A DFA defined on complete domain in δ:Q × Σ→Q is called 'Complete DFA'. In other words we can say; in transition diagram of complete DFA there is no missing edge (e.g. from each state in Q there is one outgoing edge present for every language symbol in Σ). Note: Sometime we define partial DFA as δ ? Q × Σ→Q (Read: How does “δ:Q × Σ→Q” read in the definition of a DFA).

Design DFA accepting Binary numbers divisible by number 'n':

Step-1: 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 q_r 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 q_r 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:

1. State q₀ reached if reminder is 0. State q₀ is the final state(accepting state). It is also an initial state.
2. State q₁ reaches if reminder is 1, a non-final state.
3. State q₂ if reminder is 2, a non-final state.
4. State q₃ if reminder is 3, a non-final state.
5. State q₄ if reminder is 4, a non-final state.

Using above information, we can start drawing transition diagram TD of five states as follows:

Figure-1

So, 5 states for 5 remainder values. After processing a string ω if end-state becomes q₀ that means decimal equivalent of input string is divisible by 5. In above figure q₀ is marked final state as two concentric circle.
Additionally, I have defined a transition rule δ:(q₀, 0)→q₀ as a self loop for symbol '0' at state q₀, this is because decimal equivalent of any string consist of only '0' is 0 and 0 is a divisible by n.

Step-2: 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            │q

₁ │ ├──────┼──────┼─────────────┼─────────┤ │Two │10 │2 │q₂ │ ├──────┼──────┼─────────────┼─────────┤ │Three │11 │3 │q₃ │ ├──────┼──────┼─────────────┼─────────┤ │Four │100 │4 │q₄ │ └──────┴──────┴─────────────┴─────────┘

1. To process binary string '1' there should be a transition rule δ:(q₀, 1)→q₁
2. Two:- binary representation is '10', end-state should be q₂, and to process '10', we just need to add one more transition rule δ:(q₁, 0)→q₂
   Path: →(q₀)─1→(q₁)─0→(q₂)
3. Three:- in binary it is '11', end-state is q₃, and we need to add a transition rule δ:(q₁, 1)→q₃
   Path: →(q₀)─1→(q₁)─1→(q₃)
4. Four:- in binary '100', end-state is q₄. TD already processes prefix string '10' and we just need to add a new transition rule δ:(q₂, 0)→q₄
   Path: →(q₀)─1→(q₁)─0→(q₂)─0→(q₄)

Figure-2

Step-3: 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 δ:(q₂, 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 δ:(q₂, 1)→q₀ in above figure-2.
Path: →(q₀)─1→(q₁)─0→(q₂)─1→(q₀)
with this new rule, transition diagram becomes as follows:

Figure-3

Below in each step I pick next subsequent binary number to add a missing edge until I get TD as a 'complete DFA'.

Step-4: Six = 110.

We can process '11' in present TD in figure-3 as: →(q₀)─11→(q₃) ─0→(?). Because 6 % 5 = 1 this means to add one rule δ:(q₃, 0)→q₁.

Figure-4

Step-5: Seven = 111

┌──────┬──────┬─────────────┬─────────┬────────────┬───────────┐
│Number│Binary│Remainder(%5)│End-state│ Path       │ Add       │
├──────┼──────┼─────────────┼─────────┼────────────┼───────────┤
│Seven │111   │7 % 5 = 2    │q

₂ │ q₀─11→q₃ │ q₃─1→q₂ │ └──────┴──────┴─────────────┴─────────┴────────────┴───────────┘

Figure-5

Step-6: Eight = 1000

┌──────┬──────┬─────────────┬─────────┬──────────┬─────────┐
│Number│Binary│Remainder(%5)│End-state│ Path     │ Add     │
├──────┼──────┼─────────────┼─────────┼──────────┼─────────┤
│Eight │1000  │8 % 5 = 3    │q

₃ │q₀─100→q₄ │ q₄─0→q₃ │ └──────┴──────┴─────────────┴─────────┴──────────┴─────────┘

Figure-6

Step-7: Nine = 1001

┌──────┬──────┬─────────────┬─────────┬──────────┬─────────┐
│Number│Binary│Remainder(%5)│End-state│ Path     │ Add     │
├──────┼──────┼─────────────┼─────────┼──────────┼─────────┤
│Nine  │1001  │9 % 5 = 4    │q

₄ │q₀─100→q₄ │ q₄─1→q₄ │ └──────┴──────┴─────────────┴─────────┴──────────┴─────────┘

Figure-7

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  │
└───────┴───────┴─────────────┴─────────┴──────────────┘

Figure-8

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 │
└───────┴───────┴─────────────┴─────────┴─────────────┘

Figure-9

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 │
└───────┴───────┴─────────────┴─────────┴─────────────┘

Figure-10

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 │
└───────┴───────┴─────────────┴─────────┴─────────────┘

Figure-11

Step-6 Add Twelve, Thirteen, Fourteen

┌────────┬───────┬─────────────┬─────────┬─────────────┐
│Decimal │Ternary│Remainder(%5)│End-state│  Ad