Computer Sciences > GATE 2025 SET-1 > Finite Automata
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?
A
L may have an accepting NFA with < n states.
B
L may have an accepting DFA with < n states.
C
There exists a DFA with ≤2n states that accepts L.
D
Every DFA that accepts L has >2n states.

Correct : d

Explanation:
1. Concept of NFA to DFA Conversion: By the subset construction algorithm, any Non-Deterministic Finite Automaton (NFA) with n states can be converted into an equivalent Deterministic Finite Automaton (DFA). The maximum possible number of states in this equivalent DFA is 2n. 2. Evaluate Statement (a): A regular language can be represented by multiple different NFAs. If the given NFA with n states is not minimized, there could easily exist an alternative NFA that accepts the same language using fewer than n states. Hence, this statement is True.

3. Evaluate Statement (b): While converting an NFA to a DFA typically increases or keeps the state count the same, it is completely possible for a language to have a DFA with fewer states than a poorly optimized, redundant NFA. Hence, this statement is True.

4. Evaluate Statement (c): According to the powerset construction, the upper bound for the number of states in the equivalent DFA is exactly 2n. Since the minimum DFA will always have less than or equal to 2n states, there definitively exists a DFA with ≤ 2n states that accepts L. Hence, this statement is True.

5. Evaluate Statement (d): As established by the standard upper bound rule (≤ 2n), a DFA accepting L will always have at most 2n states (and can often have far fewer after state minimization). It is completely false to claim that every DFA must have strictly greater than 2n states. Hence, this statement is False.

6. Conclusion: Since the question explicitly asks for the FALSE statement(s), option (d) is the correct choice.

Similar Questions

Which one of the following regular expressions correctly represents the language of the finite automaton given below?
#783 MCQ
Consider the following deterministic finite automaton (DFA) defined over the alphabet, &Sigma;={a,b}. Identify which of the following language(s) is/are accepte...
#1393 MCQ
Let &Sigma;={1,2,3,4}. For x&isin;&Sigma;*, let prod(x) be the product of symbols in x modulo 7. We take prod(&epsilon;)=1, where &epsilon; is the null string.F...
#1467 NAT

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......