The Gateway to Computer Science Excellence
+23 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 Veteran (105k points)
retagged by | 2.8k views

4 Answers

+37 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: 

by Veteran (425k points)
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
by Boss (13.5k points)
+2 votes
atleast 3 states  require to for this regular expresssion.
by (365 points)
+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!
by Loyal (8.3k points)
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

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
50,647 questions
56,497 answers
100,811 users