1 votes 1 votes The number of different DFA's with two states X and Y,where X is the initial state,over the alphabet $\sum$ = {0,1,2} Theory of Computation finite-automata counting + – Prajwal Bhat asked Feb 4, 2017 Prajwal Bhat 1.1k views answer comment Share Follow See 1 comment See all 1 1 comment reply mohit chawla commented Feb 4, 2017 reply Follow Share i am getting 256. what is the answer? 0 votes 0 votes Please log in or register to add a comment.
Best answer 5 votes 5 votes every state has 2 possibility nd for final states there r 2*2 choices nd for inital state there is no choice total no of dfa=1*4*26=256 saurabh rai answered Feb 4, 2017 selected Feb 4, 2017 by Prajwal Bhat saurabh rai comment Share Follow See all 2 Comments See all 2 2 Comments reply Kaushik.P.E commented Feb 4, 2017 reply Follow Share If both the states are final then whatever may be the transitions it will accept all possible strings in the language. So if both the states are final then shouldn't there be only one DFA. So shouldn't the answer be 1*(3*26+1)? or is the structure of the DFA the concern here and should we ignore the language? 0 votes 0 votes Prajwal Bhat commented Feb 5, 2017 reply Follow Share It doesn't matter what languages it accepts, we need only total number of DFA's possible with that description! 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes the answer must be 256... bcz at state can either be final or non final i.e.there will be 2*2=4 choice are there. and at each state each input will have two possibility either it will remain at that state or move to another state and there are 3 input so there will be 2*2*2=8 possibility of movement from each state by taking 3 inputs at X we will have 8 possibility and at Y we have 8 too.. hence total no.of dfa possible=4*8*8=256 Ritesh Singh answered Feb 4, 2017 Ritesh Singh comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes Answer : 256 Explanation no. of possible combinations for final states --> 4 no. of possible combinations for transactions from x --> 8 (23) no. of possible combinations for transactions from y --> 8 (23) thus the total possible combinations are --> 4 * 8 * 8 = 256 bhargav9873 answered Feb 26, 2017 bhargav9873 comment Share Follow See all 0 reply Please log in or register to add a comment.