search
Log In
0 votes
223 views


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} ]

in Theory of Computation
edited by
223 views

2 Answers

3 votes
Number is states in minimal DFA=8

Number of states in minimal NFA =4

So difference is 4.
0
I AM NOT GETTING MINIMAL DFA AS 8. I AM GETTING MINIMAL DFA AS 5
0
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

Somoshree Datta 5 YEPP I DID THAT WAY AND BY THAT I GOT 5

0
How did u get it as 5??please check it once and confirm..There are 8 distinct states in the dfa..
0

Somoshree Datta 5 YEPP ITS 8 SILLY MISTAKE OF LAST STATE

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

Related questions

0 votes
2 answers
1
292 views
How may Moore/Mealy m/c are possible with two states X & Y for the input alphabet {a, b} and output alphabet {0, 1} , where x is always the initial state?
asked Jan 6, 2019 in Theory of Computation prisonmatch 292 views
0 votes
1 answer
3
...