The Gateway to Computer Science Excellence
0 votes
145 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 by (197 points)
edited by | 145 views

2 Answers

+2 votes
Number is states in minimal DFA=8

Number of states in minimal NFA =4

So difference is 4.
by Active (5k points)
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
by Active (1.2k points)
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,737 questions
57,316 answers
198,360 comments
105,087 users