Automata Theory Questions and Answers – Finite Automata with Epsilon Transition

This set of Automata Theory test focuses 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
View Answer

Answer: d
Explanation: 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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: a
Explanation: ε does not appears on Input tape, ε transition means a transition without scanning a symbol i.e. without moving the read head.
advertisement
advertisement

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
View Answer

Answer: c
Explanation: 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}
View Answer

Answer: c
Explanation: ε-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
View Answer

Answer: c
Explanation: 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
View Answer

Answer: a
Explanation: Due to the presence of ε symbol, or rather an epsilon-move, the input alphabets unites with it to form a set including ε.
advertisement

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
View Answer

Answer: d
Explanation: 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
View Answer

Answer: c
Explanation: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.
advertisement

10. e-transitions are
a) conditional
b) unconditional
c) input dependent
d) none of the mentioned
View Answer

Answer: b
Explanation: 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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: d
Explanation: 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

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for tests, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.