Finite Automaton

To make our concepts sufficiently generic to satisfy a broad range of algorithmic constraints, we add to the classical automaton definition a set of tags, that is, any data associated to a state and needed to apply an algorithm. We will however omit tag-related considerations whenever they are not relevant.

Let $A(\Sigma, Q, I, F, \Delta, T, \tau)$ be a 7-tuple of finite sets defined as follows :

$\Sigma$	An alphabet
$Q$	A set of states
$I \subseteq Q$	A set of initial states
$F \subseteq Q$	A set of final states (also called terminal or accepting states)
$\Delta \subseteq (Q \times \Sigma \cup \{ \epsilon \} \times Q)$	A set of transitions
$T$	A set of tags
$\tau \subset (Q \times T)$	A set mapping a state to its associated tag

We distinguish one special state noted 0 and called the null or sink state. The label of a transition $(q, \sigma, p) \in \Delta$ is the letter $\sigma$, $q$ is the source state and $p$ is the destination state or aim. When $\sigma = \epsilon$ (the empty word) the transition is said to be an $\epsilon$-transition.
We call incoming transitions (respectively outgoing transitions) of a state $s$, the set of transitions $(q, \sigma, p) \in \Delta$ such that $p = s$ (respectively $q = s$). By default, the transitions of a state are its outgoing transitions.

We will write $P(X)$ for the powerset of a set $X$ and $\vert X\vert$ for its number of elements.


To access $\Delta$ we define two transition functions and :

$$\ensuremath{\delta_{1}} \: : \: Q \times \Sigma \cup \{ \epsilon \} \rightarrow P(Q)$$

$$\ensuremath{\delta_{2}} \: : \: Q \rightarrow P(\Sigma \times P(Q))$$

retrieves the set of transitions targets given the source state and a letter. allows to access the set of all the outgoing transitions of a given state.

can be naturally extended to words :

$\ensuremath{\delta_{1}} ^{*} \: : Q \times \Sigma^{*}$	$\rightarrow$	$P(Q)$
$(q, \epsilon)$	$\mapsto$	$q$
$(q, w \cdot a)$	$\mapsto$	$\ensuremath{\delta_{1}} (\ensuremath{\delta_{1}} ^{*}(q,w), a)$

The right context of a state $q$ is the set of letters labelling the outgoing transitions of $q$ : $\ensuremath{\vec{c}}(q) = \{ \sigma \in \Sigma \mid \exists p \in Q, \: (q, \sigma, p) \in \Delta \}$.
A path is a sequence $c = t_{1} \: t_{2} \: ... \: t_{n}$ of transitions $t_{i} = (q_{i}, \sigma_{i}, p_{i})$ such that $\forall i, t_{i} \in \Delta$ and for $i < n$, $q_{i+1} = p_{i}$. The path length $n$ is noted $\vert c\vert$ and its label is the concatenation of the transitions letters : $w = \sigma_{1} \: \sigma_{2} \: ... \: \sigma_{n}$.

The language recognized by an automaton $A$ is defined by :

$$L(A) = \{ w \in \Sigma ^{*} \mid \ensuremath{\delta_{1}} ^{*}(I, w) \cap F \not= \emptyset \}$$

that is, the labels of the paths leading from an initial state to a final state.

An automaton is said to be deterministic iff $I$ is a singleton and there is at most one transition per state which is labeled by a given alphabet letter, that is, $\vert\ensuremath{\delta_{1}} (q)\vert \leq 1$, $\forall q \in Q$. In this case, is defined as :

$$\ensuremath{\delta_{1}} (q, \sigma) = \left\{ \begin{array}{l... ...p) \in \Delta$} \\ 0 & \mbox{otherwise} \end{array} \right.$$

The sink state acts as failure value for the transition function.