Number of FAs DOUBT 1

Question

The number of possible finite automaton with 3 states a0, a1 and a2 where a0 is always initial state over the alphabet {p, q} which accept empty language is _______

Comments

hitendra singh s

---

and does the question says a0 is fixed as the initial state?

---

hitendra singh again s

Answer 1

Here i have considered 3states to be A,B and C. As they have asked for #dfas that generate empty languages. (A is always initial state)

we will have 3 cases :

1)no final state that yields 729 DFA.

2)two final states that gives 81 DFA.

3)one final state and we will have four cases(here) = 2 * 144+2*4=296 DFAwe will have two more case of case 3. means 3.3 and 3.4.

when state A is isolated  and there is transition from state C to state B.(because for 3.1 we have not considered transition to state B from C).

so we will have two cases for final state where it either has transition to itself or state C but not to state A as it will not satisfy empty strings relation than.

	a	b
A	1	1
B (final state)	2	2
C	1	1

so here will have 4cases .

similarly for C (final state )we will have 4state.. )

so total #DFA= 729+81+296 = 1106 DFA.

Comments

plz ans this https://gateoverflow.in/250497/number-of-states-in-toc

---

found something wrong in this answer

https://gateoverflow.in/277966/self-doubt-toc#c278084

---

yes shaik masthan ,arvin left some case ,your logic seem to be right in the link

Answer 2

No. of possibilities for start state = 1 as it is fixed here.

No. of possibilities for final state = 2³ = 8 as any subset of the set of states can be the final state.

No. of possible transition functions = Number of possible functions from a set of 6 elements (Q×Σ) to a set of 3 elements (Q)

=3⁶ = 729

So, number of possible DFA's= 729 * 8 = 5832

Comments

@smishra fa is accepting empty language which means no final state which is only 1 way for final state not 8 so answer would be 3^6 =729

Nfas would be 2^18

---

condtion is that . initial state is fixed  . not final state . so we ca choose final state either of them thats why 8.

---

No there is only way of choosing final state..

@ShaikMasthan pls check it..