There are exactly ____ different finite automata with three states 𝑥, 𝑦 and…
2015
There are exactly ____ different finite automata with three states 𝑥, 𝑦 and 𝑧 over the alphabet {𝑎,𝑏} where 𝑥 is always the start state.
- A.
64
- B.
256
- C.
1024
- D.
5832
Attempted by 121 students.
Show answer & explanation
Correct answer: D
Answer: 5832
Explanation:
Count the transition functions: there are 3 states and 2 input symbols, so there are 3 × 2 = 6 transitions to specify. Each transition can go to any of the 3 states, so the number of possible transition functions is 3^6 = 729.
Count the choices of accepting states: each of the 3 states may independently be accepting or not, giving 2^3 = 8 possible sets of accepting states.
Multiply the independent choices: total number of deterministic finite automata (with the start state fixed) is 729 × 8 = 5832.
Note: The start state is specified as x, so it does not contribute additional choices.
A video solution is available for this question — log in and enroll to watch it.