2 votes 2 votes How many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything? answer is 20 or 64? Theory of Computation theory-of-computation finite-automata virtual-gate-test-series + – aditi19 asked Mar 24, 2019 • edited Apr 5, 2019 by Lakshman Bhaiya aditi19 1.5k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Shaik Masthan commented Mar 24, 2019 reply Follow Share 20 1 votes 1 votes aditi19 commented Mar 25, 2019 reply Follow Share pls share the solution. I'm getting 64 0 votes 0 votes Shaik Masthan commented Mar 25, 2019 reply Follow Share Share your solution, i will check ! Note that they are asking the FA for (a+b)* 0 votes 0 votes aditi19 commented Mar 25, 2019 i edited by aditi19 Mar 25, 2019 reply Follow Share first we've to map 4 combinations of states and I/P symbol to two states [QxΣ->Q] [(X, a), (X, b), (Y,a), (Y, b)] --> [X, Y] so we get $2^4$=16 initial state is X=1 choice final states we've 2*2 choices so total 16*2*2*1=64 pls tell where I'm going wrong 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes 20 is right. abhishekmehta4u answered Mar 25, 2019 • selected Mar 26, 2019 by aditi19 abhishekmehta4u comment Share Follow See all 32 Comments See all 32 32 Comments reply Show 29 previous comments Saideepak Bejawada commented Apr 9, 2019 reply Follow Share @srestha In the qxn it is no where mentioned as minimal DFA's. 2 votes 2 votes aditi19 commented Apr 9, 2019 reply Follow Share @srestha in minimal DFA when several states are combined then it forms one state not multiple state. Eg- if q1 and q2 are combined to form {q1, q2} then it is a single state. hence, there can be only one transition only for a given input also nothing about the DFA has been mentioned in the question. so we assume that it is in minimal form 1 votes 1 votes srestha commented Apr 9, 2019 reply Follow Share ok understood thanks :) 0 votes 0 votes Please log in or register to add a comment.