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

Related MCQs

• Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below: A B P - Q q R S r R S s R S The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
• Which of the following is true with respect to Kleene’s theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine.
• Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)
• Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?
• Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression
• Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
• How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1)(0+1)…..N times?
• The minimum state automaton equivalent to the above FSA has the following number of states
• The set that can be recognized by a deterministic finite state automaton is
• Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is