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

retagged | 2.6k views

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
0

@Bikram sir

is this minimal dfa fine

+3

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.
Ans 3
by Boss (13.4k points)
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.

0
Right on, brother!
+4

see this is the actual procedure

1
2