Test: Non Deterministic Finite Automata


10 Questions MCQ Test Theory of Computation | Test: Non Deterministic Finite Automata


Description
This mock test of Test: Non Deterministic Finite Automata for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 10 Multiple Choice Questions for Computer Science Engineering (CSE) Test: Non Deterministic Finite Automata (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: Non Deterministic Finite Automata quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: Non Deterministic Finite Automata exercise for a better result in the exam. You can find other Test: Non Deterministic Finite Automata extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.
QUESTION: 1

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.

Solution:

Statement 1 and 2 always true for a given Language.

QUESTION: 2

Given Language: L= {ab U aba}*If X is the minimum number of states for a DFA and Y is the number of states to construct the NFA,|X-Y|=?

Solution:

Construct the DFA and NFA individually, and attain the difference of states.

QUESTION: 3

An automaton that presents output based on previous state or current input:

Solution:

A transducer is an automaton that produces an output on the basis of what input has been given currently or previous state.

QUESTION: 4

 If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ?

Solution:

The maximum number of sets for DFA converted from NFA would be not greater than 2n.

QUESTION: 5

NFA, in its name has ’non-deterministic’ because of :

Solution:

 Non deterministic or deterministic depends upon the definite path defined for the transition from one state to another or undefined(multiple paths).

QUESTION: 6

Which of the following is correct proposition?

Statement 1: Non determinism is a generalization of Determinism.

Statement 2: Every DFA is automatically an NFA

Solution:

 DFA is a specific case of NFA.

QUESTION: 7

Given Language L= {xϵ {a, b}*|x contains aba as its substring}Find the difference of transitions made in constructing a DFA and an equivalent NFA?

Solution:

The individual Transition graphs can be made and the difference of transitions can be determined.

QUESTION: 8

The construction time for DFA from an equivalent NFA (m number of node)is:

Solution:

From the coded NFA-DFA conversion.

QUESTION: 9

 If n is the length of Input string and m is the number of nodes, the running time of DFA is x that of NFA.Find x?

Solution:

Running time of DFA: O(n) and Running time of NFA =O(m2n).

QUESTION: 10

Which of the following option is correct?

Solution:

NFA, while computing strings, take parallel paths, make different copies of input and goes along different paths in order to search for the result. This creates the difference in processing speed of DFA and NFA.