The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+23 votes
2.6k views
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 (99.6k points)
retagged by | 2.6k views

4 Answers

+35 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 (418k points)
edited by
0

@Bikram sir 

is this minimal dfa fine 

+3

set2018 

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..

+5
your dfa will reject "1010"... which is in language.
0

joshi_nitish @Bikram sir 

it means order matters now got it 

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

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

0
Yes it is... Don't know why I said that before.
0
@Bikram Veteran

when ever we convert nfa to dfa is it always we get minimal dfa.can anyone explain plz
0
No.we have to further reduce the DFA (if possible) using myhill-nerode theorem or using concept of equivalence classes.
0
Minimization of DFA -- standard algorithm exist in any TOC textbook.
+4 votes
Ans 3
by Boss (13.4k 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 (8k points)
+1
I don't think so , plz draw the nfa and its conversion I am getting more than 3 states .
+1
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 ...
+5

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..

0
Right on, brother!
+4

see this is the actual procedure

Answer:

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
49,984 questions
55,135 answers
190,487 comments
85,105 users