340 views

1 Answer

Best answer
3 votes
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

Related questions

0 votes
0 votes
1 answer
1
Abhishek3301 asked Feb 6
10 views
Number of states in a minimal deterministic finite automata that accepts the language L = {(a + b) a* b*} What should be the answer to this question?
0 votes
0 votes
1 answer
3
0 votes
0 votes
2 answers
4
jugnu1337 asked Sep 3, 2023
345 views
FIND the no of 2 state dfa with the designated initial state possible over {a,b,c} which accept empty language is equal to