Compilers Questions and Answers for Experienced people on “The NFA with Epsilon – Moves”.
1. NFA-εs are defined because certain properties can be more easily proved on them as compared to NFA.
a) True
b) False
Answer: a
Clarification: NFA-ε can be transformed into a NFA always, the properties are also true for NFAs.
2. E(q) is known ε-closure of q.
a) True
b) False
Answer: a
Clarification: 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.
3. ε-transitions does not add any extra capacity of recognizing formal.
a) True
b) False
Answer: a
Clarification: ε-transitions provides a convenient transition in the systems whose current states are not precisely known.
4. 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
Answer: b
Clarification: generates the set {an bn, n=1,2,3 ….}which is not regular.
5. The transitions which does not take an input symbol are called ___________
a) ε-transitions
b) λ-transitions
c) ε-transitions & λ-transitions
d) none of the mentioned
Answer: c
Clarification: The transitions taking an input symbol are called ε-transitions or λ-transitions.
6. A nondeterministic finite automation with ε-moves is an extension of nondeterministic finite automation.
a) True
b) False
Answer: a
Clarification: Both are equivalent.
7. Is an ordinary NFA and a NFA-ε are equivalent.
a) True
b) False
Answer: a
Clarification: Yes ordinary NFA and NFA-ε are the same, in that, given either one, one can construct the other, which recognizes the same language.
8. Which of the following is a correct statement?
a) { If an bn | n = 0,1, 2, 3 ..} is regular language
b) Strings with equal number of a’s and b’s denies a regular language
c) L (A* B*)∩ B gives the set A
d) None of the mentioned
Answer: c
Clarification: If we include A and B in a set and if we write A* it means except then A i.e. B same as B* means except then B i.e. so if we intersect (A*B*) and B then get A because in any regular language. If we write A-B then A-B=A intersection B’ so if we intersect A and B means A-B So the intersection of (A*B*) and B = (BA). intersection B means (BA)-B’ and B’=A so (BA) intersection(A)=A.