727 views

1 Answer

Best answer
3 3 votes

Frankly, This Question belongs to Discrete Mathematics (Counting the number of Functions) But has been asked with a little flavor of TOC in it. Ultimately the Solution goes as "Number of functions from a set of $m$ elements to set of $n$ elements which is $n^m$.

We know, For DFA, $\delta$ is the State Transition function which is a Total function. $\delta : Q \times \Sigma \rightarrow Q$

The domain of $\delta$ i.e. $Q \times \Sigma$ , it contains 8 elements(4 states * 2 alphabets) And the Co-domain i.e. $Q$ contains 4 elements. So, Number of Transition functions from $Q\times \Sigma$ to $Q$ will be $4^8$.

Now Initial State is Fixed as given in the Question. But Final State(s) could be anything. 

So, we can have $2^4$ combinations for Final States ($\binom{4}{0} + \binom{4}{1} + \binom{4}{2} + \binom{4}{3} + \binom{4}{4} = 2^4$)

So, Finally Answer would be $2^4 \times 4^8 = 2^{20}$

• selected by
Position:
Show:

No related questions found