0 votes 0 votes How many DFA with four states can be constructed over the alphabet ∑= {a, b} with designated initial state? A. 416 * 24 B. 220 C. 216 D. 224 Theory of Computation theory-of-computation finite-automata minimal-state-automata regular-expression + – Shashi Shekhar 1 asked Sep 2, 2017 Shashi Shekhar 1 560 views answer comment Share Follow See 1 comment See all 1 1 comment reply LeenSharma commented Sep 2, 2017 reply Follow Share https://gateoverflow.in/15855/calculate-number-dfas-possible-with-designated-initial-state 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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. kapilbk1996 answered Sep 7, 2017 kapilbk1996 comment Share Follow See all 2 Comments See all 2 2 Comments reply Kaluti commented Sep 9, 2017 reply Follow Share answer is 2^(16) * 2^(4) = 2^(20) 0 votes 0 votes Udit Gupta 1 commented Sep 16, 2017 reply Follow Share Please explain how this formula works 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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..! Shubham Shukla 6 answered Oct 24, 2017 Shubham Shukla 6 comment Share Follow See all 0 reply Please log in or register to add a comment.