Theory Of Computatioj

“Non Deterministic Finite Automata – Introduction”

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.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true and Statement 2 is false
c) Statement 1 can be true and Statement 2 is true
d) Statement 1 is false and Statement 2 is also false
Answer: a

Explanation: Statement 1 and 2 always true for a given Language.


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|=?
a) 2
b) 3
c) 4
d) 1
Answer: a

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


3. An automaton that presents output based on previous state or current input:
a) Acceptor
b) Classifier
c) Transducer
d) None of the mentioned.
Answer: c

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


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