GATE2025_CS1_Q28

A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?

Note: This is a Multiple Select Question (MSQ). The goal is to identify all the FALSE statements.

✅ Final Answer:

The only FALSE statement among the options is (D).

🔹 Short Answer:

Statement (D) is false because the subset construction theorem guarantees an equivalent DFA with *at most* 2ⁿ states. This contradicts the claim that *every* DFA for the language *must* have *more than* 2ⁿ states. Statements (A) and (B) are true because the given n-state NFA might not be minimal. Statement (C) is the definition of the NFA-to-DFA conversion power bound.

🔸 Long Answer:

This question tests your understanding of the relationship between NFAs and DFAs, particularly the implications of the subset construction algorithm.

Core Concept: NFA to DFA Conversion (Subset Construction)

Any regular language accepted by an NFA with n states can also be accepted by a DFA. The standard algorithm to convert an NFA to a DFA is the subset construction. In this process, each state in the new DFA corresponds to a *subset* of states from the original NFA. Since a set of n elements has 2ⁿ possible subsets, the resulting DFA will have at most 2ⁿ states. This is a fundamental upper bound.

Analysis of Each Statement:

• (A) L may have an accepting NFA with < n states.
  This statement is TRUE. The given NFA with n states is not guaranteed to be minimal. A minimal NFA is one with the fewest possible states. We can always add redundant or unreachable states to a minimal NFA, creating a larger one that accepts the same language. Therefore, a smaller NFA might exist.
• (B) L may have an accepting DFA with < n states.
  This statement is TRUE. The minimal DFA for a language can sometimes have fewer states than a non-minimal NFA for the same language. For example, an NFA for the language (a|b)* could be built with 3 states, but its equivalent minimal DFA has only 1 state.
• (C) There exists a DFA with ≤ 2ⁿ states that accepts L.
  This statement is TRUE. This is the direct result of the subset construction theorem. It guarantees the existence of at least one DFA (the one produced by the algorithm) that accepts L and has a number of states less than or equal to 2ⁿ.
• (D) Every DFA that accepts L has > 2ⁿ states.
  This statement is FALSE. This is a very strong claim using the word "Every". It is demonstrably false because statement (C) guarantees that there is at least one DFA with *at most* 2ⁿ states. You cannot have one DFA with ≤ 2ⁿ states and simultaneously have *every* DFA with > 2ⁿ states. The upper bound from subset construction is not a lower bound. Therefore, this statement is false, making it a correct answer to the question.

Bibliography:
- Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. (Chapter 2.3: Equivalence of NFA's and DFA's).
- Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning. (Theorem 1.39).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.