#
Automata

\(
\def\Lang{\mathit{Lang}}
\def\devers#1#2{\colon#1\to#2}
\)

A finite *automaton* $M$ on the finite alphabet $A$ is composed of a
finite set $Q$ of *states*, of an *initial* state $q_0$,
of a set $T\subseteq Q$ of *terminal* states
and of a set $F\subseteq Q\times A\times Q$ of *labelled edges*
or *arcs* corresponding to state *transitions*.
We denote the automaton $M$ by the quadruplet
$(Q,q_0,T,F)$ or sometimes by just $(Q,F)$ when, for example, $q_0$ is
implicit and $T=Q$.
We say of an arc $(p,a,q)$ that it leaves state $p$ and
enters state $q$; state $p$ is the *source* of the arc,
letter $a$ its *label* and state $q$ its *target*.
A graphic representation of an automaton is displayed below.

The number of arcs exiting a given state is called the *outgoing
degree* of the state.
The *incoming degree* of a state is defined in a dual way.
By analogy with graphs, the state $q$ is a *successor* by the
letter $a$ of the state $p$ when $(p,a,q)\in F$; in the same
case, we say that the pair $(a,q)$ is a
*labelled successor* of state $p$.

A *path* of length $n$ in the automaton $M=(Q,q_0,T,F)$ is a sequence of
$n$ consecutive arcs
$\langle (p_0,a_0,p'_0),(p_1,a_1,p'_1),\dots,(p_{n-1},a_{n-1},p'_{n-1}) \rangle$
that satisfies $p'_k=p_{k+1}$ for $k=0,1,\dots,n-2$.
The *label* of the path is the word $a_0a_1\dots a_{n-1}$, its *origin*
the state $p_0$ and its *end* the state $p'_{n-1}$.
A path in the automaton $M$ is *successful*
if its origin is the initial state $q_0$ and
if its end is in $T$.
A word is *recognised* or *accepted* by the automaton if it is the label of a
successful path.
The language composed of the words recognised by the
automaton $M$ is denoted by $\Lang(M)$.

An automaton $M=(Q,q_0,T,F)$ is *deterministic* if for every pair
$(p,a)\in Q\times A$ there exists at most one state $q\in Q$ for
which $(p,a,q)\in F$.
In such a case, it is natural to consider the *transition function*
$\delta\devers{Q\times A}{Q}$ of the automaton defined for every arc
$(p,a,q)\in F$ by $\delta(p,a)=q$ and undefined elsewhere.
The function $\delta$ merely extends to words.

It is known that any language accepted by an automaton is also accepted by a
deterministic automaton and that there is a unique (up to state naming)
minimal deterministic automaton accepting it.