GATE CSE 2015 Set 2 | Question: 53

Question

The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.

Answer 1

All strings ending with $10$. So, we need $3$ states.

1. From first state on $1$, we go to second state. 
2. From second state on $0$ we go to third state.
3. From third state on $0$ we go to first state and on $1$ we go to second state. 

Only third state is final. 

L = (0+1)*10 Minimal DFA will be as follows: 

Comments

@Bikram Veteran

when ever we convert nfa to dfa is it always we get minimal dfa.can anyone explain plz

---

No.we have to further reduce the DFA (if possible) using myhill-nerode theorem or using concept of equivalence classes.

---

Minimization of DFA -- standard algorithm exist in any TOC textbook.

Answer 2

atleast 3 states  require to for this regular expresssion.
.

Comments

why we cant use dead state…

 

and when we will use it. i am little bit confuse, some time when  ques. ask for minimal  dfa we use it and sometime not,

pls tell me when we use dead state and when not

Answer 3

Make NFA from given R.E and then convert it to DFA, you'll get Arjun Sir's DFA and Answer as 3 states!

Comments

see this is the actual procedure

---

Your final dfa can't accept string 110 so wrong moves

---

Now it is corrected.

Answer 4

Minimun number of states req. by DFA = 3