Bissoy.com
Doctors Medicines MCQs Q&A

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least?

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least? Correct Answer 2N

If the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.

Related Questions

Which of the following statement(s) is/are TRUE? (i) For every NFA with an arbitrary number of final states, there is an equivalent NFA with only one final state. (ii) A language that is accepted by a DFA will also be accepted by some NFA.
A nondeterministic finite automation with ε-moves is an extension of nondeterministic finite automation.
A deterministic finite automaton (DFA) D with alphabet ∑ = {a,b} is given below. Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
Which of the following options is correct? Statement 1: Initial State of NFA is Initial State of DFA. Statement 2: The final state of DFA will be every combination of final state of NFA.
For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language.
If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ?
For an automata, which of the following are equivalent variants? DFA,NFA and NFA with epsilon transitions
Let L ⊆ {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states? 
Let 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?
All the regular languages can have one or more of the following descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions Which of the following are correct?