How many DFA with 4 state can be constructed over alphabet a and b with desiginated intial state?

Question

Please tell the approach , I am not getting that when initial state is designated then won't we consider it as like 4C1 since any of the four states could be initial state since we don't know which of the states would be designated ?

Answer 1

Initial state is fixed. Now from initial state, transitions for symbols $a$ and $b$ can be to any of the 4 states, so there are $4*4=2^4$ possibilities. Similarly, from 2nd, 3rd and 4th state, there are $2^4$ possible transitions for each state i.e. we have $2^4*2^4*2^4*2^4=2^{16}$ possible transitions.

Each state also has 2 possibilities of being final state or not, so there are $2^4$ possibilities for choosing final states.

So total number of DFAs = $2^{16}*2^4 = 2^{20}$.

Comments

We multiply because transition for symbols $a$ and $b$ are independent events i.e. for each possible transition over $a$, there are 4 possible transitions over $b$. If you add the possibilities, it means we can do transition either over $a$ or $b$, but we have to do over both.

---

Taking 2 states P & Q and two symbols 'a' & 'b' ; Q is final state, If P on a & b goes to P itself then Q is unreachable and therefore should it be considered as 2 state DFA?

Answer 2

initial state designated means u have fixed one of starting state as initial.Let x,y,z,w be states and a,b symbols.Let x be initial state.From initial state for symbol a and b we can have transition to any of the state .So total 2^4 transition possible from initial state. Similarly for w,y,z we have 2^4 transitions.Total no of transitions =2^4*2*4*2^4*2^4=2^16 .Now each state can be either final or non final.Total no of possible configuration=2*2*2*2=2^4 o ans will be 2^20 if state is designated else if it is not any  one of state can be initial so we multiply 2^20 by 4C1

Comments

could you please elaborate the answer?

---

finally got the meaning of desiginated initial sate ....thank you so much.

---

Why we are multiplying 2^4*2^4*2^4*2^4=2^16 as it is given a designated initial state i.e fixed initial state so shouldn’t it be 2^4+2^4+2^4+2^4=2^6

Answer 3

Suppose there are 'M' number of states in a DFA and 'N' number of input alphabets then the total number of DFAs is Given by the formula ((2^M) * (M ^ (M.N)))

HERE M=4 and N=2

Therefore number of DFAs is(( 2^4) * (4^8))

=((2^4) * (2^16))=2^20