TestBook Test Series: Theory Of Computation - Finite Automata

Question

The minimum number of states in a DFA that recognizes the language L = (000 + 0000)* over the alphabet {0}.

Answer 1

7 states

Comments

you never makes starting state ha ?

Answer 2

0,3,6,9,12,15 no of 0's accepted by  (000)*

0,4,8,12,16,20 no of 0's accepted by (0000)*

Union of these two we will get..

0,3,4,6,7,8,9,10,11 (by union of above defined two)

After 6 zeros if we add any no of 0's always accepted by the given language..

So it requires 6+1 = 7 minimum no.of states...

Answer 3

Number of Final state =4

Number of Non-Final state =3

Minimum Number of states=7

Comments

but we can make it by a combination of both.

For 7 0's first take 4 0's and the after 3 0's   or you can  take first 3 0's and after you can take 4 0's

$0000000 = $ $\left \{ 000 \right \}\cup \left \{ 0000 \right \}$

for 9 0's you can take 000 3 times

${000000000}=\left \{000 \right \}\cup \left \{ 000 \right \} \cup \left \{ 000 \right \}$

 

For 11 0's take 0000 2 times and 000 one time

${00000000000}=\left \{ 0000 \right \}\cup \left \{ 0000 \right \} \cup \left \{ 000 \right \}$

---

Thanks. But then why doesn't DFA has a final state as 5th one??Since if there is a self-loop then to all values >=5 can be included in there??

---

can you generate string 00000 from language $(000+0000)^{*}$??

Answer 4

6 states 3 final states and 3 non-final state

first ,fourth and fifth are final state and second third and sixth state  are non- final

Comments

Number of final state =4 Right?

---

can you please design its state diagram ?.. because ans given is 7 .

---

vijaycs07 i did msitake. it should be 7.

checck my dfa.