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

Related MCQs

• Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:
• A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has
• A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
• 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?
• In which of the stated below is the following statement true? “For every non-deterministic machine M1, there exists as equivalent deterministic machine M2 recognizing the same language.”
• Which of the following statements is/are FALSE? (1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. (2) Turing recognizable languages are closed under union and complementation. (3) Turing decidable languages are closed under intersection and complementation (4) Turing recognizable languages are closed under union and intersection.
• State table of an FSM is given below. There are two states A And B, one input and one output. Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = 1 the minimum length of input string required will be
• Let n be the positive integer constant and L be the language with alphabet {a}. To recognize L the minimum number of states required in a DFA will be
• 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?
• Consider the state table of a finite state machine that has input x and a single output z. The shortest input sequence to reach the final state C if the initial state is unknown is