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, Σ, δ, q_{0}, F$ ), where:

$Q$ is a finite set called the [...],
$Σ$ is a finite set called the [...],
$δ : Q \times Σ \to Q$ is the [...],
$q_{0} \in Q$ is the [...], and
$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, Σ, δ, q_{0}, F)$ be a finite automaton and let $w = w_{1} w_{2} . . . w_{n}$ be a string where each $w_{i}$ is a member of the alphabet $Σ$ . Then $M$ accepts $w$ iff a sequence of states $r_{0}, r_{1}, . . ., r_{n}$ is $Q$ exists with three conditions:

$r_{0} = [. . .]$
$r_{i + 1} = [. . .] for i = 0, . . ., n - 1$ , and
[...]

$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.

22.03.2020