1. FSM with output capability can be used to add two given integer in binary representation. This is
a) True
b) False
c) May be true
d) None of the mentioned
Explanation: Use them as a flip flop output.
2. 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
Explanation: Statement 1 and 2 always true for a given Language.
3. 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
Explanation: Construct the DFA and NFA individually, and the attain the difference of states.
4. An automaton that presents output based on previous state or current input:
a) Acceptor
b) Classifier
c) Transducer
d) None of the mentioned.
Explanation: A transducer is an automaton that produces an output on the basis of what input has been given currently or previous state.
5. If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ?
a) 64
b) 32
c) 128
d) 127
Explanation: The maximum number of sets for DFA converted from NFA would be not greater than 2n.
6. NFA, in its name has ’non-deterministic’ because of :
a) The result is undetermined
b) The choice of path is non-deterministic
c) The state to be transited next is non-deterministic
d) All of the mentioned
Explanation: Non deterministic or deterministic depends upon the definite path defined for the transition from one state to another or undefined(multiple paths).
7. Which of the following is correct proposition?
Statement 1: Non determinism is a generalization of Determinism.
Statement 2: Every DFA is automatically an NFA
a) Statement 1 is correct because Statement 2 is correct
b) Statement 2 is correct because Statement 2 is correct
c) Statement 2 is false and Statement 1 is false
d) Statement 1 is false because Statement 2 is false
Explanation: DFA is a specific case of NFA.
8. 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?
a) 2
b) 3
c) 4
d) Cannot be determined
Explanation: The individual Transition graphs can be made and the difference of transitions can be determined.
9. The construction time for DFA from an equivalent NFA (m number of node)is:
a) O(m2)
b) O(2m)
c) O(m)
d) O(log m)
Explanation: From the coded NFA-DFA conversion.
10. 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?
a) 1/m2
b) 2m
c) 1/m
d) log m
Explanation: Running time of DFA: O(n) and Running time of NFA =O(m2n).