Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true?
Subset construction converts an $n$-state NFA into a DFA with at most $2^n$ states, and the minimal DFA is no larger, so $k\le2^n$. No lower bound holds in general.
More Regular Expressions and Finite Automata questions
GATE 2018 CS Q62– Given a language L, define Li as follows: L0=\\ and Li=Li-1 L for all i>0. The order of a…
GATE 2015 CS (CS1) Q49– [Two DFAs, each with two states. DFA M: the start state loops on b, reads a to move to the…
GATE 2016 CS (CS1) Q28– Which one of the following regular expressions represents the language: the set of all…
GATE 2017 CS (CS1) Q32– Consider the language L given by the regular expression (a + b)* b (a + b) over the…
GATE 2014 CS (CS1) Q26– For the finite automaton shown, find the set of reachable states after input 0011.
GATE 2014 CS (CS1) Q46– Which regular expressions represent the shown DFA? I: 0*1(1+00*1)*; II: 0*1*1+11*0*1; III:…