#virtual gate

Question

Q.How many possible finite automata are ther with two states x and y , where x is always initial state with alphabet a and b, that accept everthing?? plz explain??

Comments

two states:

to accept everything there are two cases

1. first state is final and second state is not reachable : 4 possibilities

2. both the state are final : 16 possibilities

so total=20 dfa possible

---

My answer is 16.Plz verify.

---

Sir....In the question....They have mention the word FA (in general it means NFA). But this solution is for DFA.

Answer 1

There are a total of 64 DFAs.

Generally the total DFAs are divided into four categories.
1.X as non-final and Y as non-final
2.X as final and Y as non-final
3.X as non-final and Y as final
4.Both X,Y as final
So for example if we take first category,then again we have 4 posibilities in the view of X and 4 in view of Y.

They are for X(initial state):
1.from X both a,b transitions are going to X only

2.from X on transition a goes to Y and on transition b goes to X

3.from X on transition 'a' goes to X and on transition 'b' goes to Y

4.from X both the transitions a,b leads to state Y

Similarly for Y we have 4.

So for the first case in X we can have 4 Y cases. For total 4 X combinations we can have16(4*4).

Similarly for remaining 3 DFA categories we can have 48(3*16).
So a total of 64 DFAs are possible

Comments

@vamsi how can we have first case here possible where there's no final state [to accept everything there should be atleast one final state] and Language accepted by automata is everything ??

Answer 2

for y we have   delta:y,alphabet-> Q

here |alphabet|=2

|Q|=2

delta combinations on y are 2*2=4

y can be final or non-final

so 2 choices on y after selecting delta

by product rule  2*4=8

8 differnt DFA possible