0 votes 0 votes The difference between the number of states in minimal DFA and minimal NFA, which accepts all strings end with 3rd bit as b is _____. [ Assume $\sum$ = {a,b} ] Theory of Computation made-easy-test-series theory-of-computation finite-automata + – jhaanuj2108 asked Sep 26, 2018 • edited Mar 4, 2019 by Aditi Singh jhaanuj2108 642 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes Number is states in minimal DFA=8 Number of states in minimal NFA =4 So difference is 4. Somoshree Datta 5 answered Sep 27, 2018 Somoshree Datta 5 comment Share Follow See all 5 Comments See all 5 5 Comments reply Deepanshu commented Sep 27, 2018 reply Follow Share I AM NOT GETTING MINIMAL DFA AS 8. I AM GETTING MINIMAL DFA AS 5 0 votes 0 votes Somoshree Datta 5 commented Sep 27, 2018 reply Follow Share Draw the NFA which will contain 4 states and then convert the NFA to DFA. once u convert it to DFA, u will get 8 states in minimal dfa. 0 votes 0 votes Deepanshu commented Sep 27, 2018 reply Follow Share Somoshree Datta 5 YEPP I DID THAT WAY AND BY THAT I GOT 5 0 votes 0 votes Somoshree Datta 5 commented Sep 27, 2018 reply Follow Share How did u get it as 5??please check it once and confirm..There are 8 distinct states in the dfa.. 0 votes 0 votes Deepanshu commented Sep 27, 2018 reply Follow Share Somoshree Datta 5 YEPP ITS 8 SILLY MISTAKE OF LAST STATE 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes In the NFA there are minimum of 4 states and when the NFA converted to DFA the number of states are 8 and that is minimum also. Now the difference b/w them is 8-4=4 pradeepchaudhary answered Sep 29, 2018 pradeepchaudhary comment Share Follow See all 0 reply Please log in or register to add a comment.