The Gateway to Computer Science Excellence
+27 votes
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
in Theory of Computation by
retagged by | 3.7k views

4 Answers

+41 votes
Best answer

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: 

edited by

@Bikram sir 

is this minimal dfa fine 



No, it is not correct.. from final state q3 with 0 you have to go only q1 , not with 1. With 1 you can go only to q2.

Why so ? just see the regular expression given  (0+1)*10 that means it always starts with 0 . Tht's why from q3 with '10' q1 is not possible, only 0 is possible..

your dfa will reject "1010"... which is in language.

joshi_nitish @Bikram sir 

it means order matters now got it 

@Arjun sir your DFA isn't accepting "1010"

 habedo007 Junior .. no .. its accepting 1010 ...

Yes it is... Don't know why I said that before.
@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.
+4 votes
Ans 3
+2 votes
atleast 3 states  require to for this regular expresssion.
+1 vote
Make NFA from given R.E and then convert it to DFA, you'll get Arjun Sir's DFA and Answer as 3 states!
I don't think so , plz draw the nfa and its conversion I am getting more than 3 states .
When u r answering any question ... give ur own views which will nt be same as other answers ...When u want to add point or doubt... comment under best answer .... where is the diagram of nfa u r suggesting .... vague explanation ...

Puja Mishra i think you are not doing any productive work, i have seen a lot of similar comment from you, this comment is a part of guideline, if you are doing this for gaining points then it's of no use but irritating. I hope you don't post unnecessary video URLs also as it causes lots of scrolling, and why am i saying this because you post a lot of youtube urls irrespective of the content. i hope you refrain from this activity.

you really don't answer any question, so please..

Right on, brother!

see this is the actual procedure

Your final dfa can't accept string 110 so wrong moves
Now it is corrected.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,438 answers
95,266 users