Test: Non Deterministic Finite Automata

# Test: Non Deterministic Finite Automata - Computer Science Engineering (CSE)

Test Description

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

Test: Non Deterministic Finite Automata for Computer Science Engineering (CSE) 2023 is part of Theory of Computation preparation. The Test: Non Deterministic Finite Automata questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Non Deterministic Finite Automata MCQs are made for Computer Science Engineering (CSE) 2023 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Non Deterministic Finite Automata below.
Solutions of Test: Non Deterministic Finite Automata questions in English are available as part of our Theory of Computation for Computer Science Engineering (CSE) & Test: Non Deterministic Finite Automata solutions in Hindi for Theory of Computation course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Non Deterministic Finite Automata | 10 questions in 10 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Theory of Computation for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Non Deterministic Finite Automata - 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.

Detailed Solution for Test: Non Deterministic Finite Automata - Question 1

Statement 1 and 2 always true for a given Language.

Test: Non Deterministic Finite Automata - 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|=?

Detailed Solution for Test: Non Deterministic Finite Automata - Question 2

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

Test: Non Deterministic Finite Automata - Question 3

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

Detailed Solution for Test: Non Deterministic Finite Automata - Question 3

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

Test: Non Deterministic Finite Automata - Question 4

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

Detailed Solution for Test: Non Deterministic Finite Automata - Question 4

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

Test: Non Deterministic Finite Automata - Question 5

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

Detailed Solution for Test: Non Deterministic Finite Automata - Question 5

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

Test: Non Deterministic Finite Automata - 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

Detailed Solution for Test: Non Deterministic Finite Automata - Question 6

Explanation : DFA is a specific case of NFA.

Test: Non Deterministic Finite Automata - 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?

Detailed Solution for Test: Non Deterministic Finite Automata - Question 7

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

Test: Non Deterministic Finite Automata - Question 8

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

Detailed Solution for Test: Non Deterministic Finite Automata - Question 8

From the coded NFA-DFA conversion.

Test: Non Deterministic Finite Automata - 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?

Detailed Solution for Test: Non Deterministic Finite Automata - Question 9

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

Test: Non Deterministic Finite Automata - Question 10

Which of the following option is correct?

Detailed Solution for Test: Non Deterministic Finite Automata - Question 10

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.

## Theory of Computation

18 videos|56 docs|44 tests
Information about Test: Non Deterministic Finite Automata Page
In this test you can find the Exam questions for Test: Non Deterministic Finite Automata solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Non Deterministic Finite Automata, EduRev gives you an ample number of Online tests for practice

## Theory of Computation

18 videos|56 docs|44 tests