Automata Theory test on “Finite Automata with Epsilon Transition”.
1. According to the given transitions, which among the following are the epsilon closures of q1 for the given NFA?
Δ (q1, ε) = {q2, q3, q4}
Δ (q4, 1) =q1
Δ (q1, ε) =q1
a) q4
b) q2
c) q1
d) q1, q2, q3, q4
Answer: d
Clarification: The set of states which can be reached from q using ε-transitions, is called the ε-closure over state q.
2. State true or false?
Statement: An NFA can be modified to allow transition without input alphabets, along with one or more transitions on input symbols.
a) True
b) False
Answer: a
Clarification: It is possible to construct an NFA with ε-transitions, presence of no input symbols, and that is called NFA with ε-moves.
3. State true or false?
Statement: ε (Input) does not appears on Input tape.
a) True
b) False
Answer: a
Clarification: ε does not appears on Input tape, ε transition means a transition without scanning a symbol i.e. without moving the read head.
4. Statement 1: ε- transition can be called as hidden non-determinism.
Statement 2: δ (q, ε) = p means from q it can jump to p with a shift in read head.
Which among the following options is correct?
a) Statement 1 and 2, both are correct
b) Statement 1 and 2, both are wrong
c) Statement 1 is correct while Statement 2 is wrong
d) Statement 1 is wrong while Statement 2 is correct
Answer: c
Clarification: The transition with ε leads to a jump but without any shift in read head. Further, the method can be called one to introduce hidden non-determinism.
5. ε- closure of q1 in the given transition graph:
a) {q1}
b) {q0, q2}
c) {q1, q2}
d) {q0, q1, q2}
Answer: c
Clarification: ε-closure is defined as the set of states being reached through ε-transitions from a starting state.
6. Predict the total number of final states after removing the ε-moves from the given NFA?
a) 1
b) 2
c) 3
d) 0
Answer: c
Clarification: The NFA which would result after eliminating ε-moves can be shown diagramatically.
7. For NFA with ε-moves, which among the following is correct?
a) Δ: Q X (∑ U {ε}) -> P(Q)
b) Δ: Q X (∑) -> P(Q)
c) Δ: Q X (∑*) -> P(Q)
d) All of the mentioned
Answer: a
Clarification: Due to the presence of ε symbol, or rather an epsilon-move, the input alphabets unites with it to form a set including ε.
8. Which among the following is false?
ε-closure of a subset S of Q is:
a) Every element of S ϵ Q
b) For any q ϵ ε(S), every element of δ (q, ε) is in ε(S)
c) No other element is in ε(S)
d) None of the mentioned
Answer: d
Clarification: All the mentioned are the closure properties of ε and encircles all the elements if it satisfies the following options:
a) Every element of S ϵ Q
b) For any q ϵ ε(S), every element of δ (q, ε) is in ε(S)
c) No other element is in ε(S)
9. The automaton which allows transformation to a new state without consuming any input symbols:
a) NFA
b) DFA
c) NFA-l
d) All of the mentioned
Answer: c
Clarification: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.
10. e-transitions are
a) conditional
b) unconditional
c) input dependent
d) none of the mentioned
Answer: b
Clarification: An epsilon move is a transition from one state to another that doesnt require any specific condition.
11. The __________ of a set of states, P, of an NFA is defined as the set of states reachable from any state in P following e-transitions.
a) e-closure
b) e-pack
c) Q in the tuple
d) None of the mentioned
Answer: a
Clarification: The e-closure of a set of states, P, of an NFA is defined as the set of states reachable from any state in P following e-transitions.
12. The e-NFA recognizable languages are not closed under :
a) Union
b) Negation
c) Kleene Closure
d) None of the mentioned
Answer: d
Clarification: The languages which are recognized by an epsilon Non deterministic automata are closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Negation
e) Star
f) Kleene closure