The Gateway to Computer Science Excellence
+2 votes
360 views

https://gateoverflow.in/10853/how-many-dfas-exist-with-three-states-over-the-input-alphabet
For n states and m input alphabets we can have the formula for total no of DFA 
n×nnm×2n=nnm+1×2n
----  my doubt is that can we generalize a result like above for no of dfa that accepts empty language.
after so many effort i m not able to get that... 

in Theory of Computation by Boss (12.3k points) | 360 views

1 Answer

+1 vote

Yes of course we can generalise it.

We know that for a dfa comprising of n states and m input alphabets ,

No of DFA possible = n * nnm * 2n assuming that the DFA is a labelled one and hence the choice of start state matters

Now coming to your question , we need to accept an empty language.As we know final states are meant for acceptance only.So if we want that we accept the empty language what we need to do is just we do not choose any of the states as the final state and hence all states will be rejecting states and hence we will get empty language.By empty language we mean nothing is accepted.

So given an initial state there is only 1 way of choosing final state and that is not choosing any of the state as the final state

Hence the 3rd term "2n" in general expression reduces to 1 only.

Hence no of DFA which accepts empty language = n * nnm

                                                                       =  nnm+1

by Veteran (101k points)
0

@habibkhan i think in a dfa(out of n * nnm * 2n  ) that have no final state accept empty language no doubt but what about those dfawhich contains final state and that final state is unreachable .
for example suppose n=2 and m=2(0,1) so no of dfa that are not having any final state=n * nnm  = 32
but no of dfa that accept empty language are 40 so we have 8 extra i think these r comming bcoz of  " final state that is unreachable"
am i right ??
nd thnx for ur effort......

0

is this not a valid DFA that accept empty language 
    

0
Ya I got ur point but such dfa's are already counted.U cannot double count for them
0

but this dfa has a final state nd according to ur result n*nmn this have no final state and
plzz varify this with for example suppose n=2 and m=2(0,1) so no of dfa that are not having any final state=n * nnm  = 32 
but no of dfa that accept empty language are 40 so we have 8 extra

0
Ok I got ur point..Yes I agree that it is going to be complicated.Convinced

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
50,666 questions
56,159 answers
193,767 comments
93,762 users