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

Similar Questions

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
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
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

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......
Question Options

Contributed by: