Question

What is the transitional function of an NFA?

(a) Q X Σ→Q

(b) Q X Σ→2Q

(c) Q X Σ→2n

(d) Q X Σ→Qn

I got this question during an online exam.

This interesting question is from Finite Automata in division Finite Automata and Regular Expression of Compiler

Answer 1

The correct option is (b) Q X Σ→2Q

To explain: Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q to 2Q. All the elements of Q a state, the transition function, q0 the initial state and A the set of accepting states.

Then a nondeterministic finite automaton is a 5-tuple < Q,  , q0,  , A >.