Question

For a Non-deterministic Finite Automaton (NDFA) with \( N \) number of states, the equivalent Deterministic Finite Automaton (DFA) has \( D \) number of states. Then, possible number of states in DFA can be defined as:

• A. \( N \times 2 \)
• B. \( N + 2 \)
• C. \( 2^N \)
• D. \( N \times D \)

Hint:

When converting from NDFA to DFA, the number of DFA states can grow exponentially, and the maximum number of states is \( 2^N \), where \( N \) is the number of states in the NDFA.

Answer 1

The Correct Option is C

Step 1: Understanding NDFA to DFA conversion.
In the conversion from a Non-deterministic Finite Automaton (NDFA) to a Deterministic Finite Automaton (DFA), the number of states in the DFA is determined by the power set of the states of the NDFA. For an NDFA with \( N \) states, the DFA may have up to \( 2^N \) states because each state of the DFA corresponds to a subset of states of the NDFA.

Step 2: Conclusion.
Therefore, the possible number of states in the equivalent DFA is \( 2^N \), making the correct answer (3).