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.6k 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 Shaik Masthan commented Mar 25, 2019 reply Follow Share is a FA with 0 final states, can accepts (a+b)* ? 2 votes 2 votes aditi19 commented Mar 26, 2019 reply Follow Share I think final states should be 2C1+2C2 as @Shaik Masthan pointed that DFA with no final states cannot accept (a+b)* then the answer should be 3*16=48 but in the answer key it is 20 0 votes 0 votes Verma Ashish commented Mar 26, 2019 reply Follow Share What if we try for nfa .or can we include epsilon transitions? 0 votes 0 votes aditi19 commented Mar 26, 2019 reply Follow Share I think we can since they've mentioned FA only 0 votes 0 votes Shaik Masthan commented Mar 26, 2019 reply Follow Share @aditi19 in 2C1 ==> only one state is final, let initial state is not final state ===> it can't accept epsilon ==> those states you have to eliminae. i am again saying 20 is correct answer ! try to analyse on the paper, then you will understood ! @Verma Ashish actually the question is about DFA, i hope aditi make mistake while typing ! 1 votes 1 votes abhishekmehta4u commented Mar 26, 2019 reply Follow Share i am updating now 0 votes 0 votes Verma Ashish commented Mar 26, 2019 reply Follow Share @Shaik Masthan. 👍 you are right..(20 is correct). 0 votes 0 votes aditi19 commented Mar 26, 2019 reply Follow Share this is the question @Shaik Masthan so I haven't made any typing mistake 0 votes 0 votes Shaik Masthan commented Mar 26, 2019 reply Follow Share @aditi19 then they will made the mistake, don't worry about it, it should be DFA @abhishekmehta4u check the second one, it should be like a and b both reach q0 from q0 a and b both reach q1 from q1 and q0 is final state but not q1. 2 votes 2 votes prashant dubey commented Apr 8, 2019 reply Follow Share but in question mentioned that it accept everything but epsilon is not accepted by 2 (where only Y is final state) DFA . because epsilon is also a valid string of (a+b)* anyone please explain. 0 votes 0 votes aditi19 commented Apr 9, 2019 reply Follow Share @prashant dubey see @Shaik Masthan last comment 0 votes 0 votes srestha commented Apr 9, 2019 reply Follow Share In ans what is 1) and 3) point mean? From some reject state a and b coming to final state, which has no connection with other state, what the language could be? 0 votes 0 votes Verma Ashish commented Apr 9, 2019 reply Follow Share @srestha in all possible DFAs language accepted is same.. $(a+b)^*$ 1 votes 1 votes srestha commented Apr 9, 2019 reply Follow Share Check 1) and 3) carefully here it is not initial state, nor even final we can eliminate 2nd state, as it has no meaning @abhishekmehta4u 0 votes 0 votes srestha commented Apr 9, 2019 reply Follow Share @Shaik Masthan What will be answer if X and Y both can be initial state? 0 votes 0 votes srestha commented Apr 9, 2019 reply Follow Share @aditi19 See similar kind question I found "The number of DFA's with 4 states which can be constructed over the alphbet $\Sigma =\left \{ a,b \right \}$ with designated initial state are $2^{n}$, then the value of n is _________" what will be ans ?? 2 votes 2 votes Saideepak Bejawada commented Apr 9, 2019 reply Follow Share @srestha n=20 (2^4)*(4^8) = 2^20. am i right? 0 votes 0 votes aditi19 commented Apr 9, 2019 reply Follow Share @srestha regarding to your question "The number of DFA's with 4 states which can be constructed over the alphbet Σ={a,b}Σ={a,b} with designated initial state are 2n2n, then the value of n is _________" QxΣ->Q [8 combinations of states and alphabets has to be mapped to 4 states] 4*2->4 => $4^8$ A DFA has only one initial state for final states we've 2*2*2*2 choices=$2^4$ so total we've $4^8*1*2^4=2^{16}*2^0*2^4=2^{20}$ I'm getting n=20 1 votes 1 votes aditi19 commented Apr 9, 2019 reply Follow Share @srestha if there is no restriction on initial states then answer will be $2^4*1*2*2=2^{6}$ 0 votes 0 votes srestha commented Apr 9, 2019 reply Follow Share @aditi19 1)why initial state u r taking 1 choice? among 4 states, there can be any one initial right? means $\binom{4}{1}$ 2) why r u taking each state final as 2 choices? U mean either for a state, it will be final or nonfinal =>that is why 2 choices? right? 3) and why $4^{8}$ ? 4 states 2 symbols= So, 8 combination like $\left ( q_{0},a \right )$,$\left ( q_{1},a \right )$,$\left ( q_{2},a \right )$,$\left ( q_{3},a \right )$,$\left ( q_{0},b \right )$......$\left ( q_{3},b \right )$=i.e. 8 combinations Now any combination will take or not take it So, 2 choices are there then is it not $2^{8}$?? where am I wrong? 4)designated with initial state=> means anyone can be initial state right? 0 votes 0 votes srestha commented Apr 9, 2019 reply Follow Share @Saideepak Bejawada explain plz 0 votes 0 votes Saideepak Bejawada commented Apr 9, 2019 reply Follow Share @srestha 1. Designated initial state means that the initial state is already fixed. 2. If you consider the transition table, there are 4 states and 2 alphabets so 8 entries total in the table. In each of the entry any of the possible 4 states can appear. So total no.of possible combinations will be 4x4x....8 times = 4^8. 3.Coming to the final states, nothing is mentioned regarding final states, so we need to consider all possible final states, which will be 2^4 (4c0( 0 final states ) + 4c1( 1 final state ) + 4c2( 2 final states) + 4c3( 3 final states ) + 4c4( all final states) ) 4. So total no.of possible dfa's will be (2^4)*(4^8) = 2^20. Hope I'm clear 3 votes 3 votes srestha commented Apr 9, 2019 reply Follow Share @Saideepak Bejawada yes One thing still not clear u mean these 8 entries a b $q_{0}$ $q_{1}$ $q_{2}$ $q_{3}$ ____ ____ ____ ____ ____ ____ ____ ____ Now, these 8 entries can go any of 4 states So, why not $8^{4}?$ why $4^{8}?$ Another point is it could go, any one state or 2 state or 3 state or all 4 state right? I mean suppose $\left \{ q_{0},a \right \}$ can be $\Phi$ or $q_{0}$ or $q_{1}$ or$q_{2}$ or $q_{3}$ or $\left \{ q_{0}q_{1}\right \}$ or $\left \{ q_{0}q_{2}\right \}$ or $\left \{ q_{1}q_{2}\right \}$ or ....................$\left \{ q_{0}q_{1}q_{2}q_{3}\right \}$ Have u calculated all of these? 0 votes 0 votes aditi19 commented Apr 9, 2019 i edited by aditi19 Apr 9, 2019 reply Follow Share @srestha the transition function of DFA is a mapping QxΣ->Q i.e. set of combination of states and alphabets to set of states hence $4^8$ [for two sets A and B where |A|=m and |B|=n then total number of mappings of f: A->B is $n^m$ 1 votes 1 votes aditi19 commented Apr 9, 2019 reply Follow Share Another point is it could go, any one state or 2 state or 3 state or all 4 state right? @srestha in your question you've mentioned DFA. so there is no question of non determinism I mean suppose {q0,a} can be Φ or q0 or q1 or q2 or q3 or {q0q1} or {q0q2} or {q1q2} or ....................{q0q1q2q3} regarding this I'm not sure as in the question it's not mentioned whether the DFA is minimal or not. But I think we don't require it 1 votes 1 votes srestha commented Apr 9, 2019 reply Follow Share It is not nondeterminism. Even deterministic grammar can form it 0 votes 0 votes aditi19 commented Apr 9, 2019 reply Follow Share in DFA how can a state go to multiple states for an input? 0 votes 0 votes srestha commented Apr 9, 2019 reply Follow Share yes if some state are combined in minimal DFA 0 votes 0 votes Saideepak Bejawada commented Apr 9, 2019 reply Follow Share Given the point that we need to find all possible DFA's, for every state on every alphabet there exists a single unique transition to another state(Defintion of DFA). By this, we can say a transition can't go to Φ or any multiple states , the transition can be to any one of 4 states, that is why we have considered 4 possibilities for every transition. 1 votes 1 votes 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.