Let L be a set accepted by a non-deterministic finite automaton. The number of states in the…

Question

Let L be a set accepted by a non-deterministic finite automaton. The number of states in the non-deterministic finite automaton is |Q|. The maximum number of states in the equivalent deterministic finite automaton (DFA) that accepts L is

Accepted Answer

Correct answer: D — Concept — the subset (power-set) construction. Every non-deterministic finite automaton can be turned into a deterministic finite automaton that accepts exactly the same language. The construction that does this reads the non-determinism as a set of simultaneously live states: one state of the deterministic machine stands for the SET of states the non-deterministic machine could be in after reading the input so far. Because the deterministic states are therefore subsets of the state set Q, their number is bounded by the size of the power set P(Q). For a set of n elements the power set has 2n members, so the state count of the deterministic machine is bounded by 2 raised to the number of states of the non-deterministic one. Application to this automaton. The given automaton has |Q| states, so Q is a set with |Q| elements. Under the subset construction each state of the deterministic machine is a subset S ⊆ Q — the set of states reachable in the given automaton on the string read so far. Distinct deterministic states correspond to distinct subsets of Q, so the number of deterministic states cannot exceed |P(Q)|. Each of the |Q| states is either inside a given subset or outside it — two independent choices per state — so |P(Q)| = 2|Q|. The empty subset ∅ is one of these subsets. It is the trap (dead) state, entered when a symbol kills every surviving thread, and it is a genuine state of the deterministic machine, so it is counted. Cross-check on a small machine. Take |Q| = 2 with Q = {q0, q1}. The subsets are ∅, {q0}, {q1} and {q0, q1}: four in all, and 22 = 4 matches the formula. Automata are easy to construct on which the determinisation actually reaches every one of these subsets, so the bound is tight — it is attained, not merely an over-estimate. Contrast with the other values. Value What it counts / how it grows |Q| Only the |Q| singleton subsets. It would say determinisation never enlarges the machine, while the construction can reach any subset of Q. 2|Q| Linear growth with the given automaton, whereas the number of subsets of Q grows exponentially in |Q|. 2|Q| − 1 Every subset except the empty one. The trap state that the empty subset represents is a real state of the deterministic machine, so it belongs in the count. 2|Q| Every subset of Q, the empty one included. Result. The maximum number of states in the equivalent deterministic finite automaton that accepts L is 2|Q|.

Answer

A. |Q|

Answer

B. 2|Q|

Answer

C. 2|Q| − 1

Answer

D. 2|Q|

Value	What it counts / how it grows
\|Q\|	Only the \|Q\| singleton subsets. It would say determinisation never enlarges the machine, while the construction can reach any subset of Q.
2\|Q\|	Linear growth with the given automaton, whereas the number of subsets of Q grows exponentially in \|Q\|.
2\|Q\| − 1	Every subset except the empty one. The trap state that the empty subset represents is a real state of the deterministic machine, so it belongs in the count.
2\|Q\|	Every subset of Q, the empty one included.

Let L be a set accepted by a non-deterministic finite automaton. The number of…