Question

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

The question was posed to me in an interview.

This intriguing question originated from Finite Automata with Epsilon Transition topic in section Finite Automata of Automata Theory

Answer 1

Right answer is (a) Δ: Q X (∑ U {ε}) -> P(Q)

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