What are the minimum and maximum numbers of initial, dead, unreachable and final states in a valid n-state finite automaton whose accepted language is not φ?
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 exactly one initial state. Dead and unreachable states can number from 0 up to n − 1. A non-empty language needs at least 1 final state, and all n states can be final.More Theory of Computation and Compilers questions
- Which of the following finite automata recognise the language L = {a, b}*? A. M = ({q0}, {a, b}, δ, q0, {q0}) with δ(q0, a) = {q0}, δ(q0, b…
- Which of the following statements are correct? A. Syntax-directed translation can be applied in type checking. B. Syntax-directed translati…
- Match List I with List II (stack and input configurations)List I List II A. Initial configuration of stack and input in LL parsing I. $ | w…
- The precedence of regular-expression operators from lowest to highest is:
- Consider the following statements: A. For every regular language, we can design a Turing machine. B. For every context-free language, we ca…
- The transition function δ in a multi-tape Turing machine (k tapes) is defined as: