Math and science::Theory of Computation

Nondeterministic finite automata (NFA)

Nondeterministic finite automata definition

A nondeterministic finite automaton is a 5-tuple $$(Q, \Sigma, \delta, q_0, F)$$, where

1. $$Q$$ is a finite set called the states,
2. $$\Sigma$$ is a finite set called the alphabet,
3. [...] is the transition function,
4. $$q_0 \in Q$$ is the start sate, and
5. $$F \subseteq Q$$ is the set of accept states.

String acceptance

Let $$M = (Q, \Sigma, \delta, q_0, F)$$ be a NFA, let $$w$$ be a string over the alphabet $$\Sigma$$, and let $$\Sigma_{\varepsilon} = \Sigma \cup \{\varepsilon\}$$ (where $$\varepsilon$$ represents [...]).

Then $$M$$ accepts $$w$$ iff we can write $$w = y_1y_2...y_m$$ where $$y_i \in \Sigma_{\varepsilon}$$ and there exists a sequence of states in $$Q$$, $$r_0, r_1, ..., r_m$$, meeting three conditions:
1. $$r_0 = q_0$$
2. [...]
3. $$r_m \in F$$

$$w$$ is rejected iff it is not accepted.

Every nondeterministic finite automaton has an equivalent [...] (two machines are equivalent iff they recognize the same language). The proof of this is worth studying.