FOR FREE YEAR SOLVED

Question: Find mod function i.e. one binary number divided by 3 and find the remainder or modulus

Take an example:

Now, how many states require to begin a mod 4 = 0 DFA (Divisible by 4). In general, the number of steps in minimal DFA which accept all strings divisible n.

(Binary Number) mod n = 0.

Binary Number is congruent to zero modulo n or Binary Number is divisible by N.

Now if N = 4 then it requires 4 states to design mod 4 = 0 but it is not minimal DFA.

Remainders – 0 1 2 3.

But above DFA is not minimized.

Underlined ones minimized at 3 states

Here anyone

Now we discuss some important cases:

Minimal DFA which accept all strings divisible by N  mod N = 0

1. If N = prime number then no. of state at minimal DFA = n

Like N = 3 = prime then mod 3 has 3 states.

2. If N is not prime then it has two cases.

• $\mathbf{N}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{2}}^{\mathbf{k}}$  ( exact power of 2 ) then no. of state at minimal DFA = k + 1

Like $\mathbf{N}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{4}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{2}}^{\mathbf{2}}$  then mod 4 has 2 + 1 = 3 state at minimal DFA (mod 4 =0 )

• $\mathbf{N}\mathbf{ }\mathbf{\ne }\mathbf{ }{\mathbf{2}}^{\mathbf{k}}$  in that case, there is no method we should check it manually.

Pattern string accepted by (mod 3 = 0) machine

0, 11, 110, 1001, 1100, 1111…. 

Pattern string accepted by (mod 4 = 0) machine

0, 100, 1000, 1100, 10000, 10100, …..

Notice the pattern it is ending with 00

So, it is the same DFA that accept strings ending with 00

Some examples:

1. Number of states at minimal DFA of mod 8 = 0. So, mod $\mathbf{8}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{2}}^{\mathbf{3}}$ so, no. of minimum state 3 + 1 = 4

2. Number of states at minimal DFA of mod 12 = 0. It is not exact power of 2.

   So, in that case, there is no short cut method we have to solve.