1,149 views
0 votes
0 votes
What is the minimum no of states in the finite automata that accept all the strings over {0,1} where its binary equivalent is congruent to 2 modulo 5? Please explain.

1 Answer

2 votes
2 votes

Finding automata for modulo relation

first construct state table then draw automata.

  0 1
A A B
B C D
C E A
D B C
E D E

State A corresponds to remainder '0' and state B corresponds to remainder '1,and state C corresponds to remainder '2',and so on.

Minimal no of state in automata is 5

Construction of table is for mod5 we need 5 states because 5 remainders(0,1,....4)

In every coloumn write sequentially states like A,B,C,D,E,A,B,C....repeat this procedure.

this is generalization for easy understanding.

Related questions

7 votes
7 votes
2 answers
2
debanjan sarkar asked Sep 30, 2016
4,377 views
Number of states in minimal finite automata that accepts all binary strings that starts with 101 and is divisible by 100.A. 102B. 103C. 104D. 105
2 votes
2 votes
1 answer
3
Purple asked Jan 28, 2016
13,847 views
Number of final state require to accept Φ in minimal finite automata.a) 1b) 2c) 3d) None of the mentioned
2 votes
2 votes
3 answers
4
Pranay Datta 1 asked Oct 3, 2015
1,197 views
no of state in minimal finite automata that accept the string from alphabet {a,b,c} where no of a is divisible by 2 or 3 and no of c is divisible by 6?? plzz explain!!!