\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of a sidewalk
Show Answer
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \require{physics} \require{ams} \require{mathtools} \)
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.