regular expressions

Question

1. How many DFA with four states can be constructed over the alphabet ∑= {a, b} with designated initial state?

A. 4¹⁶ * 2⁴     B. 2²⁰     C. 2¹⁶      D. 2²⁴

Comments

https://gateoverflow.in/15855/calculate-number-dfas-possible-with-designated-initial-state

Answer 1

required no. of DFA = (2^n)* n^(k*n)

where n -> states and k-> input symbols

now, in this question, n=4 and k=2

total DFA = (2^4) * 4^(4*2) = 2^20

option B is correct.

Comments

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

---

Please explain how this formula works

Answer 2

2^20 must be the answer...as we designated initial state means we have fixed some state as initial state we cant change it...the possible dfas can be one with no final state..another with 2 final state other with 3 final state and last one with all states as final i.e 4 final states..as every state on a and b as transistion can go on any 4 states so for each state on a and b we have 4 possibilities similarly for other states same possibilities total possible ways are 4^8..as we can fill these 8 gaps with 4 choices we have..so 4^8....now as we need to find all possible final states in dfa...so no. of dfa with all possible final states will be 4C0+4C1+4C2+4C3+4C4=16...so 16*(4^8)..i.e 2^20 on solving..!