Question

1) How many two state FA can be drawn over an alphabet {0,1} which accepts the empty language?

Answer 1

Answer should be 20 if the Finite Automata is Deterministic, and 320 if the Finite Automata is Non Deterministic, under the ASSUMPTION that THE START STATE IS FIXED.

Points worth mentioning in order to answer this question:

1. If the FA accepts the empty set, either it has no accepting states, or it has one accepting state that you cannot reach from the other state (which must be the start state).

2. You should decide whether two automata are the same if they differ only in the names of the states. Suppose you call the states p and q. If I design one DFA with these states, changing the name of p to q and the name of q to p gives me a different automaton. Are these really different? What this really asks is whether your design of the DFA includes selecting which state is the start state, or will you simply agree that all 2-state DFA's have "the start state" and "the other state"?

3. Whether the finite automata is a DFA or an NFA?

Now, If the automata is a DFA whose two states are A & B, start state is FIXED to be A, and each transition is defined, then there would be total 4 transitions possible (delta(A, 0), delta(A, 1), delta(B, 0), delta(B, 1)).

If B is not a final state then each of these transition can have 2 choices (either A or B) so it will give 2^4 = 16 DFAs.

With B as the final state (which will be not accessible from A of course), delta(A, 0), delta(A, 1) will have only one choice(i.e. A itself) and delta(B, 0), delta(B, 1) will still have 2 choices(either A or B) so it will give 2^2 = 4 DFAs.

So under these conditions, the number of DFAs that accept empty language is 16+4=20.

In case of non – determinism, it is NOT NECESSARY TO DEFINE EACH TRANSITION so any transition can have 4 possible choices (not defined, A, B, both A&B).

Thus using the same reasoning as used for DFA, the number of NFAs that accept the empty language will be 4^4{if B is not a final state} + ((2^2) * (4^2)){if B is the final state} = 256 + 64 = 320.

P.S. If you are NOT ASSUMING the start state to be fixed then both of the answers will be simply multiplied by 2 (since once A can be the the start state and once B).So there will be 40 DFAs and 640 NFAs.

Comments

Thank a lot for the explanation Anurag.

Can anyone please explain me : 

If, N=number of states  and  M= number of input alphabets

1. For DFA 's How we can derive  N^NM  ? (for number of transition functions from a set of N*M elements to a set of N elements).
2.  For NFA, Is there any general formula like above?  

Also ,In NFA, how we are getting the below highlighted part in this explanation?

"Thus using the same reasoning as used for DFA, the number of NFAs that accept the empty language will be 4^4{if B is not a final state} + ((2^2) * (4^2)){if B is the final state} = 256 + 64 = 320."

---

If there are two states and one state is not reachable from start state, will we say the dfa has 1 state or 2 states? Why should we count unreachable state also?

Answer 2

We have two states - let them be A and B.

We always need a start state for DFA. Let it be A.

Now, A cannot be final state as then it'll accept empty string at least. So, we have two options for final state- either B or {}. Let the final state be B. Now, from A, all transitions must go to only A-  1 way. From B, transition can go to either A or B. So, we get 2*2 = 4 ways. Total no. of possible transitions  = 1 * 4 = 4.

Now, with {} as final state, all transitions are possible- transitions are from $Q \times \Sigma \to Q$, which gives $2^4 = 16$ possibilities. Thus, we get 4 + 16 = 20 DFAs with A as start state.

Similarly, 20 more with B as start state and total = 40 DFAs.

Answer 3

answer will be 40. 

total number of stages where no stage is final.= 2*1*2^4

intial stage can be selected as =2 possiblity

final stage s. =1 possiblity. which is choose no state as final state.

transition =2*2^4

now 8 more cases will be there .

4 combinations   where q1 is final state and q0 is non final state and also the initial stage and on giving both 0 & 1 q0 go to q0 while q1 go to
a) on giving both 0,1 q1 go to q1
b) on giving 0 q1 go to q1 while on giving 1 q1 go to q0
c) on giving 0 q1 go to q0 while on giving 1 q1 go to q1
d) on giving both 0,1 q1 go to q0

4 combinations   where q0 is final state and q1 is non final state and also the initial stage and on giving both 0 & 1 q1 go to q1 while q0 go to
a) on giving both 0,1 q0 go to q0
b) on giving 0 q0 go to q0 while on giving 1 q0 go to q1
c) on giving 0 q0 go to q1 while on giving 1 q0 go to q0
d) on giving both 0,1 q0 go to q1

Answer 4

Ans--only 2

Explanation-

Given language is "empty language".We have to construct a finite automata for this language.In general we consider "the construction of finite automata" as "the construction of DFA".So....

(a)If we take one state(initial state) and don't show any transition of any input symbol over this state,then this structure will not be a DFA because in a DFA there should be a transition of all input symbol over each state. (b)If we take one state(initial state) and show the transition of both input symbol 'a' and 'b' over this state, then also this will not be a DFA because there should be a final state. (c)If we take one state(initial state) and show the transition of both input symbol 'a' and 'b' over this state,and making this state final also then this FA will not be acceptor of "empty language". (d)If we take one initial state 'A'(not making final it) showing the transition of both input symbol over 'A' itself AND taking one another state 'B'(as final)showing the transition of both input symbol over the "transion edge" from final state 'B' to initial state 'A'('B'is UNREACHABLE STATE here).Then this structure will be a DFA but not minimal DFA because in minimal DFA we remove UNREACHABLE STATE. (e)similarly we cannot take concept of dead state in construction of minimal DFA.

SO NOW THE EXACT SOLUTION IS :-

" TAKE ONE INITIAL STATE 'A'(not making final it) and ONE ANOTHER STATE 'B'(making it final) and SHOW transition of both input symbol 'a' and 'b' over both state A' and 'B'. BUT don't connect both states with any transition edge. This is the desired minimal DFA which accepts "empty language".

 

Comments

leave all assumptions and just answer how man?? if it is asked what will be your answer

---

2*2^4*2^2

---

sourabh "Regarding connectedness, while a DFA need not be connected, every disconnected DFA is equivalent to a smaller one which is connected; the minimal DFA is always connected." so the dfa may be disconnected. 
source stackoverflow. now what u think.

http://stackoverflow.com/questions/21731715/dfa-without-final-state