0
$\begingroup$

Hello Folks, I am facing hard time in understanding this, basic question which says, 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?

What i understand is:

Number of possible inputs possible: (a,X), (a,Y), (b,X), (b,Y) i.e. 4;

so each input has option of going on 2 states, which sums up to be: 2^4;

I know to find total number of DFA, we need is Total number of transition * number of final state.

so, according to me answer need to be 2^4 * 2^2 = 2^6; but actual answer is 20 ? How it can be? Please throw some light on this !! Thankyou!!

$\endgroup$

1 Answer 1

1
$\begingroup$

Notice that the question also requires the automaton to accept everything. This means that if e.g., $X$ is not accepting, then you need to discount it.

Your count of the number of transition functions is correct, $2^4$. However, it's not true that the total number is $2^4$ times the number of final states, but rather the number of options for final states. Naively, this would be $4$: either both $X,Y$ are accepting, neither, just $X$ or just $Y$.

However, $X$ must be accepting, otherwise the empty word is not accepted. We now have to reason about whether $Y$ is accepting. If it is, then all transition functions are ok, and the automaton will accept everything. Thus, you have $2^4$ automata with $Y$ accepting.

If $Y$ is not accepting, then not all is lost - maybe $Y$ is not reachable from $X$. This happens when both transitions from $X$ are back to $X$. In this case, you can still point the transitions from $Y$ wherever you want, so you get $4$ additional DFAs.

So in total, you have $16+4=20$ options.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.