1. For any DFA state {qi,qj…qm} If some qj is a final state in the NFA Then {qi,qj…qm}, is a final state in the DFA.
a) True
b) False
Explanation: It the standard procedure to convert NFA to DFA.
2. What is the relation between NFA-accepted languages and DFA accepted languages?
a) >
b) <
c) =
d) <=
Explanation: The no of languages accepted by NFA and DFA is equal.
3. In regular expressions, the operator ‘*’ stands for?
a) Concatenation
b) Selection
c) Iteration
d) Addition
Explanation: It indicates iterations which can vary from zero to any number.
4. NFA-εs are defined because certain properties can be more easily proved on them as compared to NFA.
a) True
b) False
Explanation: NFA-ε can be transformed into a NFA always, the properties are also true for NFAs.
5. E(q) is known ε-closure of q.
a) True
b) False
Explanation: The ε-closure of a set of states Z of an NFA is defined as the set of states reachable from any state in Z following ε-transitions.
6. ε-transitions does not add any extra capacity of recognizing formal.
a) True
b) False
Explanation: ε-transitions provides a convenient transition in the systems whose current states are not precisely known.
7. Which of the following CFG’s can’t be simulated by an FSM?
a) S->Sa/b
b) S->aSb/ab
c) S->abX, X->cY, Y->d/aX
d) None of the mentioned
Explanation: generates the set {an bn, n=1,2,3 ….}which is not regular.
8. The transitions which does not take an input symbol are called ___________
a) ε-transitions
b) λ-transitions
c) ε-transitions & λ-transitions
d) none of the mentioned
Explanation: The transitions taking an input symbol are called ε-transitions or λ-transitions.
9. A nondeterministic finite automation with ε-moves is an extension of nondeterministic finite automation.
a) True
b) False
Explanation: Both are equivalent.
10. Is an ordinary NFA and a NFA-ε are equivalent.
a) True
b) False
Explanation: Yes ordinary NFA and NFA-ε are the same, in that, given either one, one can construct the other, which recognizes the same language.