What is the minimum and maximum number of initial, dead, unreachable and final states in a n valid ' ' state finite automaton, where the φ language accepted is not ' '?

1. AMinimum 1, 1, 1, 1; Maximum 1, n − 1, n − 1, n
2. BMinimum 1, 0, 0, 0; Maximum 1, n − 1, n − 1, n
3. CMinimum 1, 0, 0, n; Maximum 1, n, n − 1, n − 1
4. DMinimum 1, 0, 0, 1; Maximum 1, n − 1, n − 1, n

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: D. Minimum 1, 0, 0, 1; Maximum 1, n − 1, n − 1, n

Explanation

There is always exactly 1 initial state. Dead and unreachable states can be 0, and the language is non-empty, so at least 1 final state. At most n − 1 states can be dead or unreachable (the start state is neither), and all n can be final.