2,102 views
5 votes
5 votes
  • $L_1 = \left \{ w \;\; | \;\; d(w) \text{ mod} \; 8 = 0 \right \}$
  • $L_2 = \left \{ w \;\; | \;\; d(w) \text{ mod} \; 4 = 0 \right \}$

$d(w) = \text{decimal value of binary string w}$ 

Minimum no of states in both the cases ?

2 Answers

4 votes
4 votes
According to my understanding a decimal numbers to be divided by 8 or 4 its binary should be ended with 000 nd 00 respectively includig null string.(i have considered LSB as a final state of DFA). so minimal DFA for L1 and L2 will consist of 4 and 3  states respectivally,. you can match it also with several binary codes of the numbers divided by 4 or 8..

correct me if I am wrong..
2 votes
2 votes
  • $L_2 = \left \{ w \;\; | \;\; d(w) \text{ mod} \; 4 = 0 \right \}$
  0 1
A0 A0 A1
A1 A10 A11
A10 A0 A1
A11 A10 A11

Now, we can merge these states in 2 states.

No. of state in minimal DFA is 2.

  •  $L_1 = \left \{ w \;\; | \;\; d(w) \text{ mod} \; 8 = 0 \right \}$
  0 1
A0 A0 A1
A1 A10 A11
A10 A100 A101
A11 A110 A111
A100 A0 A1
A101 A10 A11
A110 A100 A101
A111 A110 A111

 So, After merging the states DFA will be

 So. total number of state in final DFA is 4.

edited by

Related questions

0 votes
0 votes
0 answers
1
ankit-saha asked Mar 24, 2022
338 views
What will be the minimal DFA for $\left \{a^{n} :n mod 3 =0 \right \}\cup \left \{a^{n} :n mod 5 =1 \right \}$
0 votes
0 votes
2 answers
2
aditi19 asked Dec 14, 2018
1,503 views
Given following NFAfind the minimal equivalent DFA
1 votes
1 votes
1 answer
3
sripo asked Nov 6, 2018
2,977 views
What is the number of states for the above DFA,please draw NFA,DFA and minimised DFA for the same.Also won't the language not accept epsilon?
0 votes
0 votes
0 answers
4
Harshitha 123 asked Jun 12, 2018
405 views
How many states will be present in L={w/(n(a) + (2 n(b)mod 3)) lessthan 2} ? (I got 7 states is that correct)