\section{Les automates}

Dans cette partie, nous parlerons des automates et plus particulièrement, nous
allons parler des automates sans \(\varepsilon\)-transition (des automates
utilisent des \(\varepsilon\)-transitions, comme ceux de
\textit{Thompson}~\cite{thompson1968programming}, qui sont utilisés par nos
ordinateurs). Pour autant, les automates que nous verrons ne sont pas limités
par le manque de ces transitions.

\subsection{Définition}

Comme dit précédemment, un automate est un objet mathématique reconnaissant un
langage. On notera \(M \in AFN(\Sigma, \eta)\) l'automate qui a pour transition
des valeurs dans \(\Sigma\), des valeurs \og{}d'état\fg{} dans \(\eta\). Et
\(AFN(\Sigma, \eta)\) l'ensemble des automates finis non déterministes de
valeur de transition dans \(\Sigma\) et de valeur d'état dans \(\eta\). On
écrira \(L(M)\) pour désigner le langage qu'il reconnait. Un automate est un
tuple qu'on peut écrire de cette forme \(M = (Q, I, F, \delta)\) avec~:

\begin{align*}
    Q & \subseteq \eta \quad \text{L'ensemble des états qui constituent
    l'automate}                                                                \\
    I & \subseteq Q \quad \text{L'ensemble des états initiaux}          \\
    F & \subseteq Q \quad \text{L'ensemble des états finaux}            \\
    \delta:~ & Q \times \Sigma \to 2^Q \quad \text{La fonction de transition}
\end{align*}

Un automate peut se représenter à l'aide d'un graphe orienté, valué,
particulier. Par exemple si on veut représenter \(M = (\{q_1, q_2, q_3, q_4,
q_5\}, \{q_1\},\{q_2, q_3\}, \delta)\) avec \(M \in AFN(\Sigma, \eta)\),
\(\Sigma = \{0, 1\}\), \(\eta = \{q_1, q_2, q_3, q_4, q_5\}\) et \(\delta\)
défini comme ceci~:

\begin{align*}
    \delta(q_1, 0) & = \{q_2, q_4\} & \delta(q_3, 1) & = \{q_4\} \\
    \delta(q_1, 1) & = \varnothing  & \delta(q_4, 0) & = \{q_5\} \\
    \delta(q_2, 0) & = \varnothing  & \delta(q_4, 1) & = \{q_3\} \\
    \delta(q_2, 1) & = \varnothing  & \delta(q_5, 0) & = \{q_4\} \\
    \delta(q_3, 0) & = \{q_3\}      & \delta(q_5, 1) & = \{q_5\} \\
\end{align*}

\begin{figure}[H]
    \centering
    \captionsetup{type=figure,justification=centering}
    \begin{tikzpicture}
        \tikzset{
            ->,
            >=stealth',
            node distance=3cm,
            every state/.style={thick},
            initial text=$ $,
        }
        \node[state, initial] (q1) {$q_1$};
        \node[state, accepting, right of=q1] (q2) {$q_2$};
        \node[state, above of=q2] (q4) {$q_4$};
        \node[state, accepting, right of=q2] (q3) {$q_3$};
        \node[state, right of=q4] (q5) {$q_5$};

        \draw   (q1) edge[above] node{0} (q4)
        (q1) edge[below] node{0} (q2)
        (q4) edge[bend right, below] node{1} (q3)
        (q4) edge[above] node{0} (q5)
        (q3) edge[above] node{1} (q4)
        (q3) edge[loop right] node{0} (q3)
        (q5) edge[bend right, above] node{0} (q4)
        (q5) edge[loop right] node{1} (q5);
    \end{tikzpicture}
    \caption{
        Exemple de représentation graphique d'un automate.
    }\label{fig:automata}
\end{figure}

Dans la Figure~\ref{fig:automata}, on peut voir que les états initiaux (dans
cet automate n'y a qu'un seul initial~; \(q_1\)) ont une petite flèche qui
pointe sur eux et que les états finaux ont un double contour. Et que les
transitions sont symbolisées par des flèches entre les états et que ces flèches
sont labellisées.

% \vphantom{}

% On parlera de l'inverse de l'automate \(M\) noté \(\overleftarrow{M}\) qui peut
% être défini de cette façon~:

% \begin{gather*}
%     \overleftarrow{M} = (Q, F, I, \delta') \quad \text{avec} \\
%     M = (Q, I, F, \delta) \notag \\
%     \forall (p, q) \in Q^2 ~|~ q \in \delta(p, a) \Rightarrow p \in \delta'(q, a) \notag
% \end{gather*}

% Donc si on veut représenter l'inverse de l'automate représenté dans la
% Figure~\ref{fig:automata}, ça nous donnerait ceci~:

% \begin{figure}[H]
%     \centering
%     \captionsetup{type=figure,justification=centering}
%     \begin{tikzpicture}
%         \tikzset{
%             ->,
%             >=stealth',
%             node distance=3cm,
%             every state/.style={thick},
%             initial text=$ $,
%         }
%         \node[state, accepting] (q1) {$q_1$};
%         \node[state, initial below, right of=q1] (q2) {$q_2$};
%         \node[state, above of=q2] (q4) {$q_4$};
%         \node[state, initial below, right of=q2] (q3) {$q_3$};
%         \node[state, right of=q4] (q5) {$q_5$};

%         \draw   (q4) edge[above] node{0} (q1)
%         (q2) edge[below] node{0} (q1)
%         (q3) edge[bend left, below] node{1} (q4)
%         (q5) edge[above] node{0} (q4)
%         (q4) edge[above] node{1} (q3)
%         (q3) edge[loop right] node{0} (q3)
%         (q4) edge[bend left, above] node{0} (q5)
%         (q5) edge[loop right] node{1} (q5);
%     \end{tikzpicture}
%     \caption{
%         Exemple de représentation graphique de l'inverse de l'automate de la
%         Figure~\ref{fig:automata}.
%     }\label{fig:automata_invserse}
% \end{figure}

% On voit bien que l'apparence de l'automate ne change pas les transitions sont
% juste inversées et les états initiaux sont devenus finaux et inversement.

\vphantom{}

On peut aussi étendre la fonction de transition \(\delta\) de manière qu'elle
ait comme signature~:

\[
    \delta: Q \times \Sigma^* \to 2^Q
\]

En la définissant récursivement de telle sorte~:

\begin{align*}
    \delta(q, \varepsilon) & = \{q\}                                                                       \\
    \delta(q, a \cdot w)   & = \bigcup_{q' \in \delta(q, a)} \delta(q', w) \quad \text{avec}~ a \in \Sigma
\end{align*}

\begin{example}
    Voici donc quelques exemples si on prend l'automate utilisé pour la
    représentation graphique (Figure~\ref{fig:automata})~:

    \begin{align*}
        \delta(q_1, 00)           & = \{q_5\}                                \\
        \delta(q_1, 11)           & = \varnothing                            \\
        \delta(q_1, \varepsilon)  & = \{q_1\}                                \\
        \delta(q_1, 00 \cdot 1^n) & = \{q_5\} \text{ avec } n \in \mathbb{N}
    \end{align*}
\end{example}

\vphantom{}

\begin{definition}
    Un automate est dit \textit{standard} quand il ne possède qu'un seul état
    initial non ré-entrant, aussi défini comme ceci~:

    \begin{gather*}
        M = (Q, \{i\}, F, \delta) \quad \text{avec} \\
        \forall p \in Q, \forall a \in \Sigma ~|~ i \notin \delta(p, a) \notag \\
        M \in AFN(\Sigma, \eta) \notag
    \end{gather*}
\end{definition}

\begin{definition}
    Un automate est \textit{homogène} lorsque, pour tous les états, les
    transitions allant vers cet état ont la même valeur. En d'autres termes,
    quand il respecte cette propriété~:

    \begin{gather*}
        M = (Q, I, F, \delta) \quad \text{avec} \\
        \forall (p, q, r) \in Q^3, \exists (a, b) \in \Sigma^2 ~|~ q \in \delta(p, a) \land q \in \delta(r, b) \Longrightarrow a = b \notag \\
        M \in AFN(\Sigma, \eta) \notag
    \end{gather*}
\end{definition}

\begin{definition}
    Un automate est qualifié d'\textit{accessible} lorsqu'en partant des
    initiaux, on peut arriver sur tous les états qui le composent. C'est-à-dire
    qu'il valide cette condition~:

    \begin{gather*}
        M = (Q, I, F, \delta) \quad \text{avec} \\
        \forall p \in Q, \exists w \in \Sigma^* ~|~ p \in \bigcup_{i \in I} \delta(i, w) \notag \\
        M \in AFN(\Sigma, \eta) \notag
    \end{gather*}
\end{definition}

\begin{definition}
    Un automate est considéré comme \textit{coaccessible} dès que, de tous les
    états, on peut arriver à un état final. Ceci veut dire qu'il atteste de
    cette particularité~:

    \begin{gather*}
        M = (Q, I, F, \delta) \quad \text{avec} \\
        \forall p \in Q, \exists w \in \Sigma^* ~|~ F \cap \delta(p, w) \neq \varnothing \notag \\
        M \in AFN(\Sigma, \eta) \notag
    \end{gather*}
\end{definition}

\begin{definition}
    Un automate est dit \textit{déterministe} quand tous ses états vont au
    maximum à un état par symbole et que l'automate ne possède qu'un seul état
    initial. Autrement dit qu'il valide cette propriété~:

    \begin{gather*}
        M = (Q, I, F, \delta) \quad \text{avec} \\
        |I| = 1 \land \forall q \in Q, \forall a \in \Sigma, | \delta(q, a) | \leq 1\\
        M \in AFN(\Sigma, \eta) \notag
    \end{gather*}

    On parlera de \textit{déterministe complet} lorsque tous ses états vont sur
    un état par symbole. C'est-à-dire qu'il respecte cette condition~:

    \begin{gather*}
        M = (Q, I, F, \delta) \quad \text{avec} \\
        |I| = 1 \land \forall q \in Q, \forall a \in \Sigma, | \delta(q, a) | = 1\\
        M \in AFN(\Sigma, \eta) \notag
    \end{gather*}
\end{definition}

\begin{example}
    Donc, l'automate représenté sur la Figure~\ref{fig:automata} est standard,
    non homogène, accessible et coaccessible. Car il possède bien un unique
    état initial (\(q_1\)), mais \(q_3\), \(q_4\) et \(q_5\) ne respecte pas la
    propriété pour être homogène, parce qu'ils ont des transitions allant vers
    eux avec des valeurs différentes. De plus, tous ses états sont accessibles
    depuis l'état initial. Et son inverse est, lui-même aussi, accessible et il
    n'est pas déterministe.
\end{example}

\begin{definition}
    Nous parlerons de sous-automate pour parler d'une \og{}région\fg{} d'un
    automate. \(N\) est un sous automate de \(M\) qu'on notera \(N \subseteq
    M\), s'il vérifie cette propriété~:

    \begin{gather*}
        N = (Q', I', F', \delta') \quad \text{avec} \\
        Q' \subseteq Q \land I' \subseteq Q' \land F' \subseteq Q' \\
        \delta' \text{ est une restriction de } \delta, \delta': Q' \to 2^{Q'}\\
        M = (Q, I, F, \delta) \land (M, N) \in (AFN(\Sigma, \eta))^2 \notag
    \end{gather*}
\end{definition}

Les automates pouvant être représentés à l'aide de graphes, on peut étendre les
propriétés sur les graphes aux automates. Par exemple, on pourra parler des
composantes fortement connexes d'un automate. Autrement dit, en partant de
n'importe quel état, on peut arriver à tous les autres états. Ainsi, ça veut
dire qu'un automate fortement connexe vérifierait ceci~:

\begin{gather*}
    M = (Q, I, F, \delta) \quad \text{avec} \\
    \forall (p, q) \in Q^2, \exists w \in \Sigma^* ~|~ q \in \delta(p, w) \notag \\
    M \in AFN(\Sigma, \eta) \notag
\end{gather*}

\begin{definition}
    Une autre notion qui est présente sur les graphes que nous allons adapter
    sur les automates est la notion de \textit{hamac}. Nous dirons qu'un
    automate est un \textit{hamac} lorsqu'il est standard, accessible et
    coaccessible (nous gardons le nom \textit{hamac} pour une raison de
    compréhension). Ceci veut dire qu'il peut être décrit comme ceci~:

    \begin{gather*}
        M = (Q, I, F, \delta) \quad \text{avec} \\
        standard(M) \land accessible(M) \land coaccessible(M) \\
        M \in AFN(\Sigma, \eta) \notag
    \end{gather*}
\end{definition}

\begin{definition}
    Une autre idée empruntée au graphe est la notion d'\textit{orbite}. Nous
    dirons qu'un sous-automate est une \textit{orbite}, si pour tout couple
    d'état \(i\) et \(t\), il existe un mot non vide permettant d'aller de
    \(i\) à \(t\). Aussi défini comme ceci~:

    \begin{gather*}
        \mathcal{O} = (Q, I, F, \delta) \quad \text{avec} \\
        \forall (p, q) \in Q^2, \exists w \in \Sigma^* \setminus \{\varepsilon\} ~|~ q \in \Sigma(p, w) \\
        \mathcal{O} \subseteq M \land M \in AFN(\Sigma, \eta)
    \end{gather*}

    \noindent Dans la même idée, nous parlerons d'\textit{orbite maximale}
    lorsque l'orbite n'est incluse dans aucune orbite différente. En d'autres
    termes, que l'orbite est fortement connexe sans prendre les chemins
    triviaux
    (mot vide).
\end{definition}

\begin{definition}
    Nous noterons \(In(\mathcal{O})\) et \(Out(\mathcal{O})\) respectivement
    l'ensemble des portes d'entrée et l'ensemble des portes de sortie de
    l'orbite \(\mathcal{O}\). Qui sont définies de cette façon~:

    \begin{gather*}
        In(\mathcal{O}) = \{p \in Q' ~|~ \exists a \in \Sigma, \exists q \in Q
        \setminus Q', p \in \delta(q, a)\} \cup I'\\
        Out(\mathcal{O}) = \{p \in Q' ~|~ \exists a \in \Sigma, \exists q \in Q
        \setminus Q', q \in \delta(p, a)\} \cup F'\\
        \text{avec} \\
        \mathcal{O} = (Q', I', F', \delta') \land M = (Q, I, F, \delta) \\
        \mathcal{O} \subseteq M \land M \in AFN(\Sigma, \eta)
    \end{gather*}
\end{definition}

\begin{definition}
    Avec ceci, on peut définir ce qu'est une \textit{orbite stable}. Une orbite
    est dite \textit{stable} quand pour toutes les sorties, il existe une
    transition vers toutes les entrées. C'est-à-dire que l'orbite vérifie
    ceci~:

    \begin{gather*}
        \forall q \in Out(\mathcal{O}), \exists a \in \Sigma ~|~ \delta(q, a) \cap In(\mathcal{O}) \neq \varnothing \\
        \text{avec} \\
        \mathcal{O} = (Q, I, F, \delta) \subseteq M \land M \in AFN(\Sigma, \eta)
    \end{gather*}

    \noindent On la qualifiera même de \textit{fortement stable} lorsqu'en
    supprimant toutes les transitions de portes des sorties vers les portes
    d'entrée, les orbites maximales de l'orbite sont stables et
    \textit{fortement stables}.
\end{definition}

\begin{definition}
    De même, on dira qu'une orbite est \textit{transversale} si toutes les
    entrées viennent des mêmes états et que toutes les sorties vont aux mêmes
    états. Autrement dit, que l'orbite valide cette propriété~:

    \begin{gather*}
        \forall (p, q) \in (Out(\mathcal{O}))^2, (\bigcup_{a \in \Sigma} \delta(p, a)) \cap Q \setminus Q' = (\bigcup_{a \in \Sigma} \delta(q, a)) \cap Q \setminus Q' \\
        \forall (p, q) \in (In(\mathcal{O}))^2, \{r \in Q \setminus Q' ~|~ \exists a \in \Sigma, p \in \delta(r, a)\} = \{r \in Q \setminus Q' ~|~ \exists a \in \Sigma, q \in \delta(r, a)\} \\
        \text{avec} \\
        \mathcal{O} = (Q', I', F', \delta) \subseteq M = (Q, I, F, \delta) \land M \in AFN(\Sigma, \eta)
    \end{gather*}

    \noindent Elle sera même \textit{fortement transversale} lorsqu'en
    supprimant toutes les transitions de portes des sorties vers les portes
    d'entrée, les orbites maximales de l'orbite sont transversales et
    \textit{fortement transversales}.
\end{definition}

\subsection{Fonction sur les automates}

Une des fonctions sur les automates est \(accept\) qui vérifie si le mot est
reconnu par l'automate. C'est-à-dire que si on prend le chemin décrit par le
mot donné en argument, on arrive sur un ou plusieurs états finaux. Elle a alors
pour signature~:

\[
    accept: AFN(\Sigma, \eta) \times \Sigma^* \to \mathbb{B}
\]

Elle peut être définie simplement comme ceci~:

\begin{align*}
    accept(M, w) = (\bigcup_{p \in I} \delta(p, w)) \cap F \neq \varnothing
\end{align*}

Une autre fonction sur les automates est \(homogenize\) qui renvoie l'automate
homogène qui reconnait le même langage que l'automate donné. Elle a ainsi comme
signature~:

\[
    homogenize: AFN(\Sigma, \eta) \to AFN(\Sigma, ((\Sigma \cup \{\varepsilon\}) \times \eta))
\]

Elle peut être définie de cette façon~:

\begin{gather*}
    homogenize(M) = N \quad \text{avec}                                                          \\
    \forall (p, q) \in Q^2, \exists a \in \Sigma ~|~ p \in \delta(q, a) \Rightarrow (a, p) \in Q' \\
    \forall (p, q) \in Q^2, \forall a \in \Sigma ~|~ p \notin \delta(q, a)
    \Rightarrow (\varepsilon, p) \in Q' \\
    \forall p \in I, \forall a \in \Sigma \cup \{\varepsilon\} ~|~ (a, p) \in Q' \Rightarrow (a, p) \in I' \\
    \forall p \in F, \forall a \in \Sigma \cup \{\varepsilon\} ~|~ (a, p) \in Q' \Rightarrow (a, p) \in F' \\
    \forall (p, q) \in Q, \exists a \in \Sigma, \forall b \in \Sigma \cup \{\varepsilon\} ~|~ (b, q) \in Q', p \in \delta(q, a) \Rightarrow (p, a) \in \delta'((b, q), a) \\
    M = (Q, I, F, \delta) \in AFN(\Sigma, \eta) \\
    N = (Q', I', F', \delta') \in AFN(\Sigma, ((\Sigma \cup \{\varepsilon\})
    \times \eta))
\end{gather*}

On remarque bien que par construction l'automate résultant est homogène, parce
que les états sont devenus un couple entre leur valeur et leur transition
entrante. Ce qui fait que toutes les transitions vers l'état \((a, p)\) ont
tous pour valeur \(a\).

\subsection{Conclusion}

Comme nous venons de voir, les automates sont des outils pour reconnaitre des
mots d'un langage. L'une de leurs grandes forces est leur simplicité. Toutes
les opérations sur les automates peuvent donc être automatisées. Ce qui fait
que cet objet est très intéressant dans le monde de l'informatique. En
revanche, l'un de ses points faibles est que pour nous humain, il est difficile
de représenter un automate autrement que par une représentation graphique.
Contrairement aux expressions régulières. Il serait alors intéressant de
pouvoir convertir une expression régulière en automate. On pourrait se poser la
question \og{}est-ce-que c'est toujours possible de convertir une expression
régulière en automate\fg{}, la réponse est oui, car selon le théorème de
Kleene~\cite{Kleene1951RepresentationOE}, toute expression régulière peut être
représentée par un automate fini. Nous allons voir un algorithme pour faire
cette conversion dans la prochaine section.