Non Deterministic Finite Automata – Introduction

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.

• Statement 1 is true and Statement 2 is true

• Statement 1 is true and Statement 2 is false

• Statement 1 can be true and Statement 2 is true

• Statement 1 is false and Statement 2 is also false

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|=?

• 2

• 3

• 4

• 1

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

• Acceptor

• Classifier

• Transducer

• None of the mentioned.

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

• 128

• 127

• 68

• 67

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

• The result is undetermined

• The choice of path is non-deterministic

• The state to be transited next is non-deterministic

• All of the mentioned

Which of the following is correct proposition?

Statement 1: Non determinism is a generalization of Determinism.

Statement 2: Every DFA is automatically an NFA

• Statement 1 is correct because Statement 2 is correct

• Statement 2 is correct because Statement 2 is correct

• Statement 2 is false and Statement 1 is false

• Statement 1 is false because Statement 2 is false

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?

• 2

• 3

• 4

• 1

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

• O(m2)

• O(2m)

• O(m)

• O(log m)

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?

• 1/m2

• 2m

• 1/m

• log m

Which of the following option is correct?

• NFA is slower to process and its representation uses more memory than DFA

• DFA is faster to process and its representation uses less memory than NFA

• NFA is slower to process and its representation uses less memory than DFA

• DFA is slower to process and its representation uses less memory than NFA