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

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

Question Options

Contributed by: