Given an arbitary non-deterministic finite automaton (NFA) with N states, the…
2001
Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least
- A.
N2
- B.
2N
- C.
2N
- D.
N!
Attempted by 34 students.
Show answer & explanation
Correct answer: B
To find an equivalent DFA from an arbitrary NFA with N states, we use the Subset Construction Algorithm (also known as Tompson's subset construction).
1. The Upper Bound (2N)
In an NFA, the machine can be in multiple states simultaneously. When we track these combinations to create a deterministic machine (DFA), every single state in the new DFA corresponds to a subset of states from the original NFA.
If the NFA has a set of states S = {q1, q2,......, qN}, the state space of the new DFA will be a subset of the Power Set of S, denoted as P(S).
The total number of elements in a power set of a set with N elements is calculated as:
Max DFA States = |P(S)| = 2N