\( \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

Finite automata

A finite automaton (plural: automata) is a model of computation. Finite automata and their probabilistic counterpart Markov chains are useful tools when attempting to recognize patterns in data. Their formal definition has a 1-1 correspondence with a type of state diagram.

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

  1. \( Q \) is a finite set called the [...],
  2. \( \Sigma \) is a finite set called the [...],
  3. \( \delta : Q \times \Sigma \to Q \) is the [...],
  4. \( q_0 \in Q \) is the [...], and
  5. \( F \subseteq Q \) is the set of [...].

Processing of input

When an automaton receives an input string, it can either accept or reject it. A string is accepted if the automaton is in an accept state once the full input string is processed. Formally this is described as:

String acceptance

Let \( M = (Q, \Sigma, \delta, q_0, F) \) be a finite automaton and let \( w = w_1w_2...w_n \) be a string where each \( w_i \) is a member of the alphabet \( \Sigma \). Then \( M \) accepts \( w \) iff a sequence of states \( r_0, r_1, ..., r_n \) is \( Q \) exists with three conditions:

  1. \( r_0 = [...] \)
  2. \( r_{i+1} =  [...]  \text{ for } i = 0, ..., n - 1\), and
  3. [...]

\( w \) is rejected iff it is not accepted.

If \( A \) is the set of all [...] that [...], we say that \( A \) is the [...] of machine \( M \) and write [...]. We say that M [...] A.

State machine representation

A finite automaton has a 1-1 correspondence with a graphical state machine representation.