The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
How many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything?

answer is 20 or 64?
asked in Theory of Computation by Active (2.9k points)
edited by | 219 views
pls share the solution. I'm getting 64
Share your solution, i will check !

Note that they are asking the FA for (a+b)*
first we've to map 4 combinations of states and I/P symbol to two states [QxΣ->Q]

[(X, a), (X, b), (Y,a), (Y, b)] --> [X, Y]

so we get $2^4$=16

initial state is X=1 choice

final states we've 2*2 choices

so total 16*2*2*1=64


pls tell where I'm going wrong

1 Answer

+1 vote
Best answer

20 is right.





answered by Boss (33.4k points)
selected by

@Saideepak Bejawada


One thing still not clear

u mean these 8 entries 

  a b













Now, these 8 entries can go any of 4 states

So, why not $8^{4}?$ why $4^{8}?$

Another point is it could go, any one state or 2 state or 3 state or all 4 state right?

I mean suppose $\left \{ q_{0},a \right \}$ can be $\Phi$ or $q_{0}$ or $q_{1}$ or$q_{2}$ or $q_{3}$ or $\left \{ q_{0}q_{1}\right \}$ or $\left \{ q_{0}q_{2}\right \}$ or $\left \{ q_{1}q_{2}\right \}$ or ....................$\left \{ q_{0}q_{1}q_{2}q_{3}\right \}$ 

Have u calculated all of these?



the transition function of DFA is a mapping QxΣ->Q i.e. set of combination of states and alphabets to set of states

hence $4^8$

[for two sets A and B where |A|=m and |B|=n then total number of mappings of f: A->B is $n^m$


Another point is it could go, any one state or 2 state or 3 state or all 4 state right?

@srestha in your question you've mentioned DFA. so there is no question of non determinism

I mean suppose {q0,a} can be Φ or q0 or q1 or q2 or q3 or {q0q1} or {q0q2} or {q1q2} or ....................{q0q1q2q3}

 regarding this I'm not sure as in the question it's not mentioned whether the DFA is minimal or not. But I think we don't require it

It is not nondeterminism. Even deterministic grammar can form it
in DFA how can a state go to multiple states for an input?
yes if some state are combined in minimal DFA
Given the point that we need to find all possible DFA's, for every state on every alphabet there exists a single unique transition to another state(Defintion of DFA). By this, we can say a transition can't go to Φ or any multiple states , the transition can be to any one of 4 states, that is why we have considered 4 possibilities for every transition.


In the qxn it is no where mentioned as minimal DFA's.

@srestha in minimal DFA when several states are combined then it forms one state not multiple state. Eg- if q1 and q2 are combined to form {q1, q2} then it is a single state. hence, there can be only one transition only for a given input


nothing about the DFA has been mentioned in the question. so we assume that it is in minimal form
ok understood

thanks :)

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,083 questions
53,206 answers
70,426 users