\section{Les automates de Glushkov}\label{sec:glushkov}

Le terme \og{}automate de Glushkov\fg{} est un abus de langage, faisant
référence aux automates que l'algorithme de transformation d'expression
régulière en automate, appelé algorithme de Glushkov produit. Son nom vient de
l'informaticien soviétique Victor Glushkov qui est son
créateur~\cite{V_M_Glushkov_1961}.

\subsection{Définition}

Nous appliquerons cet algorithme à l'aide de la fonction \(glushkov\) qui a
donc pour signature~:

\[
    glushkov: Exp(\Sigma) \to AFN(\Sigma, \mathbb{N})
\]

Et a ainsi, on peut définir cette fonction de cette façon~:

\begin{align*}
    glushkov (E) & = (Q, \{0\}, F, \delta) \quad \text{avec}                                                                      \\
    Q & \leftarrow \{n ~|~ n \in \mathbb{N} \land 0 \leq n < m\}                                                       \\
    F & \leftarrow \{n ~|~ (a, n) \in Last\} \cup (\{0\} \cdot Null)                                                   \\
    \forall q                    \in \delta(p, a) & ~|~ \begin{cases} (a, q) \in First, & \text{si } p = 0 \\ (a, q) \in Follow((b, p)) & \text{sinon} \end{cases} \\
    (E', m)                                       & \leftarrow linearization(E)                                                                                    \\
    (First, Last, Null, Follow)                   & \leftarrow flnl(E')
\end{align*}

\begin{example}
    Vu qu'un dessin vaut toujours mieux que mille mots, voici un exemple de
    l'automate résultant de la transformation de cette expression \(E = (a+b)
    \cdot a^* \cdot b^* \cdot (a+b)^*\).

    \begin{figure}[H]
        \centering
        \captionsetup{type=figure,justification=centering}
        \begin{tikzpicture}
            \tikzset{
                ->,
                >=stealth',
                node distance=2.25cm,
                every state/.style={thick},
                initial text=\( \),
            }
            \node[state, initial] (0) {\(0\)};
            \node[state, accepting, right of=0, below of=0] (1) {\(1\)};
            \node[state, accepting, right of=0, above of=0] (2) {\(2\)};
            \node[state, accepting, right of=2, below of=2] (3) {\(3\)};
            \node[state, accepting, right of=3] (4) {\(4\)};
            \node[state, accepting, right of=4, above of=4] (5) {\(5\)};
            \node[state, accepting, right of=5] (6) {\(6\)};

            \draw   (0) edge[below] node{\(a\)} (1)
            (0) edge[above] node{\(b\)} (2)
            (1) edge[below] node{\(a\)} (3)
            (2) edge[above] node{\(a\)} (3)
            (1) edge[bend right=1.5cm, below] node{\(b\)} (6)
            (2) edge[bend left=1.5cm, above] node{\(b\)} (6)
            (1) edge[bend right, below] node{\(a\)} (5)
            (2) edge[bend left, above] node{\(a\)} (5)
            (1) edge[bend left=2mm, below] node{\(b\)} (4)
            (2) edge[bend right=2mm, above] node{\(b\)} (4)
            (3) edge[above] node{\(b\)} (4)
            (3) edge[loop left] node{\(a\)} (3)
            (3) edge[bend left, above] node{\(a\)} (5)
            (3) edge[bend right=1.75cm, below] node{\(b\)} (6)
            (4) edge[above] node{\(a\)} (5)
            (4) edge[bend right, below] node{\(b\)} (6)
            (4) edge[loop above] node{\(b\)} (4)
            (5) edge[bend right, below] node{\(b\)} (6)
            (5) edge[loop above] node{\(a\)} (5)
            (6) edge[bend right, above] node{\(a\)} (5)
            (6) edge[loop right] node{\(b\)} (6);
        \end{tikzpicture}
        \caption{
            Exemple de représentation graphique de l'automate résultant de
            \(glushkov(E)\).
        }\label{fig:automata_glushkov}
    \end{figure}
\end{example}

\vphantom{}

On peut remarquer qu'il y a des propriétés intéressantes sur cet automate.
C'est ce que l'on va étudier maintenant.

\subsection{Propriétés~:}

Nous verrons ici plusieurs propriétés sur les automates de Glushkov, mais nous
n'en ferons pas la preuve, nous en donnerons une justification, mais pas une
réelle preuve (preuve disponible dans ce
document~\cite{DBLP:journals/tcs/CaronZ00}).

\vphantom{}

\begin{enumerate}
    \item Les automates de Glushkov sont \textit{standards}, car par construction,
      il ne peut avoir qu'un seul état initial (0) non ré-entrant.

          \vphantom{}

    \item L'automate a \(n + 1\) avec \(n\) le nombre de symboles de l'expression
      régulière. Le \(+ 1\) vient du fait que nous ajoutons un état \(0\) qui a
      des transitions vers les \(First\).

          \vphantom{}

    \item Les automates de Glushkov sont accessibles et coaccessibles. C'est dû au
      fait que chaque symbole dans l'expression régulière est accessible et
      coaccessible et que cette propriété ne se perd pas lors de la
      transformation.

          \vphantom{}

    \item L'automate de Glushkov est homogène. Cela résulte de sa construction, car
      pour qu'un état aille sur un autre état, il faut qu'il ait dans ses
      \textit{Follow} \((a, n)\) avec \(a\) le symbole de la transition et
      \(n\) la valeur de l'état. Et étant donné que pour chaque couple \((b,
      m)\) il ne peut n'avoir que ce couple avec comme seconde valeur \(m\)
      alors la transition vers cet état sera toujours la même.

          \vphantom{}

    \item Les automates de Glushkov sont des hamacs. Car ils sont standard,
      accessible et coaccessible. Et que toutes leurs orbites maximales sont
      fortement stables et transversales.

          \vphantom{}
\end{enumerate}

\subsection{Conclusion}

L'algorithme de Glushkov permet de convertir une expression régulière en
automate. Avec les expressions régulières, on peut simplement décrire un
langage et avec les automates, on peut simplement savoir si un mot est reconnu.
Il est très utilisé en \textit{informatique}, parce que pour les humains, il
est plus simple de décrire un langage avec une expression régulière. Et les
machines comprennent très facilement les automates. Ce qui fait qu'il est
possible de faire des \textit{programmes informatiques} qui reconnaissent un
langage et exécutent des tâches à chaque mot.