Non-deterministic Finite Automaton

Aka. NFA. Has multiple transitions for the same input symbol are allowed. Can have multiple possible starting states.

More flexible in terms of construction and may simplify the process of creating an FA for a regular language. Useful for theorem-proving.

Transition Function

Defined as $\delta: Q \times \Sigma \rightarrow 2^Q$. The function maps a state and an input symbol to a set of possible next states, rather than a single state as in DFA.

Extended Transition Function

Defined as $\delta^*: Q \times \Sigma^* \rightarrow 2^Q$. It handles strings instead of individual symbols. $\delta^*(q, x)$ is the set of states reachable from state $q$ after reading string $x$.

Rules:

• $\delta^*(q, \lambda) = \{q\}$
• $\delta^*(q, ya) = \bigcup_{p \in \delta^*(q, y)} \delta(p, a)$
  Union of the sets of states reachable from each state in $\delta^*(q, y)$ after reading symbol $a$.

Acceptance by a NFA

Let $M = (Q, \Sigma, q_0, A, \delta)$.

A string $x \in \Sigma^*$ is accepted iff $\delta^*(q_0, x) \cap A \neq \varnothing$.

A string is accepted if at least one of the states reachable from the start state after reading the string is an accepting state.