The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
219 views
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
+1
20
0
pls share the solution. I'm getting 64
0
Share your solution, i will check !

Note that they are asking the FA for (a+b)*
0
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
0

@Saideepak Bejawada

yes 

One thing still not clear

u mean these 8 entries 

  a b

$q_{0}$

$q_{1}$

$q_{2}$

$q_{3}$

____

____

____

____

____

____

____

____

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?

+1

@srestha

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$

+1

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

0
It is not nondeterminism. Even deterministic grammar can form it
0
in DFA how can a state go to multiple states for an input?
0
yes if some state are combined in minimal DFA
+1
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.
+2

@srestha 

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

+1
@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

also

nothing about the DFA has been mentioned in the question. so we assume that it is in minimal form
0
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
184,553 comments
70,426 users