(Ordinary) Finite Automata

Definition: An A is a finite automaton (FA) iff A is a tuple

$$\langle Q, I, F, \Sigma, \Delta \rangle$$

with

1. Q is a finite set of states
2. I $\subseteq$ Q is the set of initial states
3. F $\subseteq$ Q is the set of final states
4. $\Sigma$ is a finite input alphabet
5. $\Delta$ $\subseteq$ Q $\times$ $\Sigma^{*}$ $\times$ Q is the set of transitions

A run of the automaton $A$ -or an execution- over an input word $w$ is a sequence $\varrho = \varrho(0)\varrho(1)...\varrho(i)...$ such that $\langle \varrho(i),w(i),\varrho(i+1)\rangle \in \Delta$ for $i \geq 0$ and $\varrho(0) = q_{0}$.

An automaton usually can have more than only one run and these runs are different. Therefore one can for an automaton $A$ define the set $EXEC(A)$ as the smallest set of executions of the automaton $A$ with the requirement that for all $\varrho, \varrho' \in EXEC(A)$ it holds that $\varrho \ne \varrho'$.