Nondeterministic Finite Automata

Definition

A nondeterministic finite automata $N = (Q, \Sigma , \delta , q_0, F)$ is a list where $Q$ and $\Sigma $ are finite sets, $\delta : Q \times \Sigma \to \powerset{Q}$, $q_0 \in Q$ and $F \subset Q$. A nondeterministic finite automata with empty moves $N = (Q, \Sigma , \delta , q_0, F)$ is a list where $Q$ and $\Sigma $ are finite sets, $\delta : Q \times (\Sigma \cup \set{\varnothing}) \to \powerset{Q}$, $q_0 \in Q$ and $F \subset Q$.

As with finite automata, we call $Q$ the states, $\Sigma $ the alphabet, $\delta $ the transition function, $q_0$ the start state, and $F$ the accept states (or final states). An input $u \in \str(\Sigma )$ results in a state sequence $x \in \str(Q)$ with $x_1 = q_0$ and $x_{i+1} = \delta (x_i, u_i)$ for $i = 1, \dots , \num{u}$.

Main result

For any automata $M$, there exists a nondeterminstic finite automata $N$ such that $N$ accepts the same languages as $M$.¹ For this reason, a language is regular if and only if some nondeterministic finite automaton accepts it.

1. Future editions will include an account. ↩︎