\section{Les expressions régulières}

Dans cette section, nous parlerons d'expressions régulières (\textit{ER}). Nous
allons nous concentrer sur un type bien particulier d'expressions régulières
qui ne seront pas les expressions régulières que nous pouvons voir plus
quotidiennement dans le domaine de l'informatique, les expressions régulières
\textit{UNIX}. Mais plut\^{o}t une version plus simple de celles-ci.

\subsection{Définition}

Nous allons noter une expression régulière \(E \in Exp(\Sigma)\), c'est-à-dire
une expression régulière où les symboles sont inclus dans l'ensemble \(\Sigma\)
et où \(Exp(\Sigma)\) représente l'ensemble des expressions sur \(\Sigma\).
Cette expression reconnait un langage qu'on pourra appeler \(L(E)\). Nous
pouvons définir une expression régulière récursivement de cette manière~:

\begin{align}
    E & = \varepsilon                 \\
    E & = a                           \\
    E & = F + G                       \\
    E & = F \cdot G                   \\
    E & = F^*                         \\
    E & = (F)\label{align:parenthese} \\
    \makebox[0pt][c]{
        \phantom{E } \text{
            avec \(E\), \(F\) et \(G\) des expressions régulières sur \(\Sigma\) et \(a\)
            un symbole de \(\Sigma\)
        }
    } \notag
\end{align}

On notera que \(*\) est prioritaire sur \(\cdot\) qui est lui-même prioritaire
sur \(+\) et qu'ils sont tous deux associatifs à gauche. On comprend donc
pourquoi l'équation~(\ref{align:parenthese}) existe, elle est là pour des
raisons de priorité. Il est alors évident de calculer les diverses fonctions
sur celle-ci, c'est pour cela qu'on ne précisera pas son
calcul\label{subsec:parenthese}. On peut définir chaque équation comme ceci~:

\vphantom{}

\begin{itemize}
    \item[\textbullet] \textbf{\(E = \varepsilon\)~:}
        Représente le mot vide, de ce fait un mot de longueur zéro. Il peut être
        parfois représenté par \og{}\$\fg{}.

        \vphantom{}

    \item[\textbullet] \textbf{\(E = a\)~:} Représente un symbole
        présent dans l'ensemble \(\Sigma\)

        \vphantom{}

    \item[\textbullet] \textbf{\(E = F + G\)~:} Représente l'union
        des deux expressions régulières \(F\) et \(G\). Par abus de langage, on
        peut aussi dire \(F\) \og{}ou\fg{} \(G\) pour représenter cette union.

        \vphantom{}

    \item[\textbullet] \textbf{\(E = F \cdot G\)~:}
        Représente la concaténation des deux expressions régulières \(F\) et
        \(G\).

        \vphantom{}

    \item[\textbullet] \textbf{\(E = F^* \)~:} Représente l'union infinie de
        copie de \(F\), cette répétition incluant la puissance zéro et donc le
        mot vide.
\end{itemize}

\vphantom{}

Pour calculer le langage que dénote l'expression régulière, on peut le calculer
récursivement de cette manière~:

\begin{align*}
    L(\varepsilon) & = \{\varepsilon\} \\
    L(a) & = \{a\}           \\
    L(F + G) & = L(F) \cup L(G)  \\
    L(F \cdot G) & = L(F) \cdot L(G) \\
    L(F^*) & = (L(F))^*        \\
    \makebox[0pt][c]{
        \phantom{E } \text{
            avec \(F\) et \(G\) des expressions régulières sur \(\Sigma\) et \(a\)
            un symbole de \(\Sigma\)
        }
    } \notag
\end{align*}

\begin{example}
    On comprendra ainsi que l'expression \(E = a+c \cdot d\) avec \(E \in
    Exp(\Sigma)\) et \(\Sigma = \{a, b, c, d\}\), dénote le langage \(L(E) =
    \{a, cd\}\). Car on peut représenter \(E\) comme ceci~:

    \begin{figure}[H]
        \centering
        \captionsetup{type=figure,justification=centering}
        \begin{tikzpicture}[
                mycircle/.style={
                        draw,
                        circle,
                        minimum height=.75cm,
                        minimum width=.75cm
                    },
                mysquare/.style={
                        draw,
                        rectangle,
                        minimum height=.5cm,
                        minimum width=.5cm,
                    }
            ]
            \node[mysquare] (plus) {+}
            child {node[mycircle] (a) {a}}
            child {
                    node[mysquare] (point) {.}
                    child {node[mycircle] (c) {c}}
                    child {node[mycircle] (d) {d}}
                };

            \node[right=3mm of d] {\(\{d\}\)};
            \node[left=3mm of c] {\(\{c\}\)};
            \node[right=3mm of point] {\(\{cd\}\)};
            \node[left=3mm of a] {\(\{a\}\)};
            \node[above=3mm of plus] {\(\{a, cd\}\)};
        \end{tikzpicture}
        \caption{
            Représentation de l'expression régulière à l'aide d'un arbre syntaxique
        }\label{fig:arbre_syn}
    \end{figure}

    Comme on peut voir sur la Figure~\ref{fig:arbre_syn}, grâce à cette
    représentation, on peut calculer simplement le langage reconnu par
    l'expression régulière (ici représenté par les ensembles à c\^{o}té de
    chaque arbre).
\end{example}

% \vphantom{}

% \begin{example}

%     On comprendra aussi que l'expression \(E' = \varepsilon + b^* \cdot a\), dénote
%     le langage \(L(E') = \{\varepsilon, b^* \cdot a\}\).

%     \begin{figure}[H]
%         \centering
%         \captionsetup{type=figure,justification=centering}
%         \begin{tikzpicture}[
%                 mycircle/.style={
%                         draw,
%                         circle,
%                         minimum height=.75cm,
%                         minimum width=.75cm
%                     },
%                 mysquare/.style={
%                         draw,
%                         rectangle,
%                         minimum height=.5cm,
%                         minimum width=.5cm,
%                     }
%             ]
%             \node[mysquare] (plus) {+}
%             child {node[mycircle] (epsilon) {\(\varepsilon\)}}
%             child {
%                     node[mysquare] (point) {\(\cdot \)}
%                     child {
%                             node[mysquare] (etoile) {*}
%                             child {
%                                     node[mycircle] (b) {b}
%                                 }
%                         }
%                     child {node[mycircle] (a) {a}}
%                 };

%             \node[right=3mm of a] {\(\{a\}\)};
%             \node[left=3mm of b] {\(\{b\}\)};
%             \node[left=3mm of etoile] {\(\{b^*\}\)};
%             \node[right=3mm of point] {\(\{b^* \cdot a\}\)};
%             \node[left=3mm of epsilon] {\(\{\varepsilon\}\)};
%             \node[above=3mm of plus] {\(\{\varepsilon, b^* \cdot a\}\)};
%         \end{tikzpicture}
%         \caption{
%             Représentation de l'expression régulière à l'aide d'un arbre syntaxique
%         }
%     \end{figure}

% \end{example}

\subsection{Fonction sur les \textit{ER}}

Plusieurs informations sur les expressions régulières nous seront utiles, comme
l'ensemble des premiers/derniers symboles des mots du langage décrit par
l'expression. Il serait aussi intéressant de savoir si son langage contient le
mot vide. Et d'avoir les successeurs des symboles, c'est-à-dire les symboles
suivant un symbole donné.

\vphantom{}

On pourrait calculer individuellement chaque information, mais nous pouvons
calculer tout d'un coup avec une fonction qu'on pourrait appeler \(flnf\). Elle
permet de calculer un tuple contenant toutes ces informations pour une
expression régulière donné.

\vphantom{}

On aurait donc pour une expression régulière \(E\) sur l'alphabet \(\Sigma\),
ceci~:

\begin{center}
    \(flnf(E) = (F, L, \Theta, \delta)\)

    \begin{itemize}
        \item[\textbullet] \(F \subseteq \Sigma\)~: Ensemble des premiers
            symboles de l'expression régulière

            \vphantom{}

        \item[\textbullet] \(L \subseteq \Sigma\)~: Ensemble des derniers
            symboles de l'expression régulière

            \vphantom{}

        \item[\textbullet] \(\Theta\) =
            \(
            \begin{cases}
                \{ \varepsilon \}, & \text{si } \varepsilon \in L(E) \\
                \varnothing        & \text{sinon}
            \end{cases}
            \)

            \vphantom{}

        \item[\textbullet] \(\delta\)~: \(\Sigma \to 2^{\Sigma}\) fonction
            renvoyant les successeurs du symbole donné
    \end{itemize}
\end{center}

La fonction \(flnf\) a donc comme signature~:

\begin{align*}
    flnf: Exp(\Sigma) \to (2^{\Sigma} \times 2^{\Sigma} \times
    \{\varnothing,\{\varepsilon\}\} \times \Sigma \to 2^{\Sigma})
\end{align*}

Et peut-être calculée de cette manière, pour \(E\) et \(G\) des expressions
régulière sur l'alphabet \(\Sigma\) et \(a\) un symbole de \(\Sigma\)~:

\begin{align*}
    flnf(\varepsilon) & = (\varnothing, \varnothing, \varepsilon, \delta) ~|~
    \delta(a) = \varnothing, a \in \Sigma                                     \\
    \vphantom{} \notag                                                        \\
    flnf(a) & = (\{a\}, \{a\}, \varnothing, \delta) ~|~ \delta(a) =
    \varnothing, a \in \Sigma
\end{align*}

\begin{gather*}
    flnf(E + G) = (F \cup F', L \cup L', \Theta \cup \Theta', \delta'')~
    \text{avec} \\
    \delta''(a) = \delta(a) \cup \delta'(a) ~|~ \forall a \in \Sigma \notag \\
    (F, L, \Theta, \delta) = flnf(E) \land (F', L', \Theta', \delta') = flnf(G) \notag
\end{gather*}

\begin{gather*}
    flnf(E \cdot G) = (F'', L'', \Theta \cap \Theta', \delta'')~ \text{avec} \\
    F'' = F \cup F' \cdot \Theta \notag \\
    L'' = L' \cup L \cdot \Theta' \notag \\
    \delta''(a) = \begin{cases} \delta(a) \cup \delta'(a) \cup F', & \text{si}~ a \in L \\ \delta(a) \cup \delta'(a) & \text{sinon}\end{cases} ~|~ \forall a \in \Sigma\notag \\
    (F, L, \Theta, \delta) = flnf(E) \land (F', L', \Theta', \delta') = flnf(G) \notag
\end{gather*}

\begin{gather*}
    flnf(E^*) = (F, L, \{\varepsilon\}, \delta')~ \text{avec} \\
    \delta'(a) = \begin{cases} \delta(a) \cup F, & \text{si}~ a \in L \\ \delta(a) & \text{sinon}\end{cases} ~|~ \forall a \in \Sigma\notag \\
    (F, L, \Theta, \delta) = flnf(E) \notag
\end{gather*}

\begin{remark}
    Il existe un isomorphisme entre les fonctions et les couple antécédents,
    images. Ce qui fait que la fonction des successeurs pourra être représenté
    à l'aide d'un couple.
\end{remark}

\begin{example}
    Prenons par exemple l'expression régulière suivante \(E = a \cdot b + c
    \cdot d\), avec \(E \in Exp(\Sigma)\) et \(\Sigma = \{a, b, c, d\}\).
    Toujours à l'aide d'un arbre syntaxique, on peut calculer ce que
    \(flnf(E)\) donnerait.

    \begin{figure}[H]
        \centering
        \captionsetup{type=figure,justification=centering}
        \begin{tikzpicture}[
                level 1/.style={
                        sibling distance=6cm
                    },
                level 2/.style={
                        sibling distance=3cm
                    },
                mycircle/.style={
                        draw,
                        circle,
                        minimum height=.75cm,
                        minimum width=.75cm
                    },
                mysquare/.style={
                        draw,
                        rectangle,
                        minimum height=.5cm,
                        minimum width=.5cm,
                    }
            ]
            \node[mycircle] (plus) {+}
            child {
                    node[mysquare] (point) {\(\cdot\)}
                    child {node[mycircle] (a) {a} }
                    child {node[mycircle] (b) {b} }
                }
            child {
                    node[mysquare] (point2) {\(\cdot\)}
                    child {node[mycircle] (c) {c} }
                    child {node[mycircle] (d) {d}}
                };

            \node[below=3mm of a] {\((\{a\}, \{a\}, \varnothing, \varnothing)\)};
            \node[below=3mm of b] {\((\{b\}, \{b\}, \varnothing, \varnothing)\)};
            \node[below=3mm of c] {\((\{c\}, \{c\}, \varnothing, \varnothing)\)};
            \node[below=3mm of d] {\((\{d\}, \{d\}, \varnothing, \varnothing)\)};

            \node[left=3mm of point] {\((\{a\}, \{b\}, \varnothing, \{(a, b)\})\)};
            \node[right=3mm of point2] {\((\{c\}, \{d\}, \varnothing, \{(c, d)\})\)};

            \node[above=3mm of plus] {\((\{a, c\}, \{b, d\}, \varnothing, \{(a, b),(c, d)\})\)};
        \end{tikzpicture}
        \caption{
            Représentation de l'expression régulière à l'aide d'un arbre
            syntaxique.
        }
    \end{figure}

    Il advient que \(flnf(E) = \{\{a, c\}, \{b, d\}, \varnothing, \delta\}\)
    avec \(\delta\) qui est défini comme ceci~:

    \begin{align*}
        \delta(a) & = \{b\}       \\
        \delta(b) & = \varnothing \\
        \delta(c) & = \{d\}       \\
        \delta(d) & = \varnothing
    \end{align*}
\end{example}

\vphantom{}

\begin{example}
    Un autre exemple pourrait être \(E' = (a + b) \cdot c^*\), avec cet
    exemple, on voit l'utilité de la parenthèse, car sans elle la concaténation
    aurait été sur \(b \cdot c^*\). Et comme dit précédemment
    (\ref{subsec:parenthese}), son calcul revient à calculer l'expression
    contenue entre les parenthèses.

    \begin{figure}[H]
        \centering
        \captionsetup{type=figure,justification=centering}
        \begin{tikzpicture}[
                level 1/.style={
                        sibling distance=6cm
                    },
                level 2/.style={
                        sibling distance=3cm
                    },
                mycircle/.style={
                        draw,
                        circle,
                        minimum height=.75cm,
                        minimum width=.75cm
                    },
                mysquare/.style={
                        draw,
                        rectangle,
                        minimum height=.5cm,
                        minimum width=.5cm,
                    }
            ]
            \node[mycircle] (point) {\(\cdot\)}
            child {
                    node[mysquare] (plus) {\(+\)}
                    child {node[mycircle] (a) {a} }
                    child {node[mycircle] (b) {b} }
                }
            child {
                    node[mysquare] (etoile) {\(*\)}
                    child {node[mycircle] (c) {c} }
                };

            \node[below=3mm of a] {\((\{a\}, \{a\}, \varnothing, \varnothing)\)};
            \node[below=3mm of b] {\((\{b\}, \{b\}, \varnothing, \varnothing)\)};
            \node[below=3mm of c] {\((\{c\}, \{c\}, \varnothing, \varnothing)\)};

            \node[left=3mm of plus] {\((\{a, b\}, \{a, b\}, \varnothing, \varnothing)\)};
            \node[right=3mm of etoile] {\((\{c\}, \{c\}, \varepsilon, \{(c, c)\})\)};

            \node[above=3mm of point] {\((\{a, b\}, \{a, b, c\}, \varnothing, \{(a, c), (b, c), (c, c)\})\)};
        \end{tikzpicture}
        \caption{
            Représentation de l'expression régulière à l'aide d'un arbre
            syntaxique.
        }
    \end{figure}

    Ce qui fait que \(flnf(E') = (\{a, b\}, \{a, b, c\}, \varnothing,
    \delta')\) avec \(\delta'\) qui est défini comme décrit après~:

    \begin{align*}
        \delta'(a) & = \{c\}       \\
        \delta'(b) & = \{c\}       \\
        \delta'(c) & = \{c\}       \\
        \delta'(d) & = \varnothing
    \end{align*}

\end{example}

\vphantom{}

Une autre fonction qui s'applique aux expressions régulières est
\(linearization\)~; (elle peut paraitre inutile, mais) elle nous servira dans
la Section~\ref{sec:glushkov}. Sa signature est~:

\begin{gather*}
    linearization: Exp(\Sigma) \to Exp(\Sigma \times \mathbb{N}) \\
\end{gather*}

Elle peut être définie de cette manière, pour \(a \in \Sigma\) et \((E, F) \in
(Exp(\Sigma))^2\)~:

\begin{gather*}
    linearization(E) = \pi_2(linearization\_aux(E, 1)) \quad \text{avec}
\end{gather*}

\noindent Avec \(\pi_n\) la fonction de projection sur les tuples et
\(linearization\_aux\) définie récursivement comme ceci~:

\begin{gather*}
    linearization\_aux(\varepsilon, n) = (\varepsilon, n) \\
    linearization\_aux(a, n) = ((a, n), n + 1) \\
    linearization\_aux(E + F, n) = (E' + F', n'') \quad \text{avec} \\
    (E', n') \leftarrow linearization\_aux(E, n) \notag \\
    (F', n'') \leftarrow linearization\_aux(F, n') \notag \\
    linearization\_aux(E \cdot F, n) = (E' \cdot F', n'') \quad \text{avec} \\
    (E', n') \leftarrow linearization\_aux(E, n) \notag \\
    (F', n'') \leftarrow linearization\_aux(F, n') \notag \\
    linearization\_aux(E^*, n) = (E'^*, n') \quad \text{avec} \\
    (E', n') \leftarrow linearization\_aux(E, n) \notag
\end{gather*}

Avec cette définition, on peut voir que tous les symboles sont associés à un
unique entier. Ce qui fait que l'expression régulière résultante ne contient
que des symboles uniques. Et que, de ce fait, si deux couples partagent le même
entier, cela implique qu'ils ont la même valeur de symbole.

\begin{example}

    Si on prend l'expression régulière \(E = \varepsilon + b^* \cdot b\), avec
    \(E \in Exp(\Sigma)\) et \(\Sigma = \{a, b, c, d\}\).

    \begin{figure}[H]
        \centering
        \captionsetup{type=figure,justification=centering}
        \begin{tikzpicture}[
                mycircle/.style={
                        draw,
                        rectangle,
                        rounded corners=.375cm,
                        minimum height=.75cm,
                        minimum width=.75cm
                    },
                mysquare/.style={
                        draw,
                        rectangle,
                        minimum height=.5cm,
                        minimum width=.5cm,
                    }
            ]
            \node[mysquare] (1) {+}
            child {node[mycircle] {\(\varepsilon\)}}
            child {
                    node[mysquare] {\(\cdot \)}
                    child {
                            node[mysquare] {*}
                            child {
                                    node[mycircle] {b}
                                }
                        }
                    child {node[mycircle] {b}}
                };
            \node[mysquare, right=7cm of 1] (2) {+}
            child {node[mycircle] {\(\varepsilon\)}}
            child {
                    node[mysquare] {\(\cdot \)}
                    child {
                            node[mysquare] {*}
                            child {
                                    node[mycircle] {(b, 1)}
                                }
                        }
                    child {node[mycircle] {(b, 2)}}
                };

            \draw[line width=.5mm, -{Stealth[length=5mm, open]}] ($(1.east) + (1.5cm, -2cm)$) -- node[midway, above=2mm] {\(linearization\)} ($(2.west) + (-1.5cm, -2cm)$);
        \end{tikzpicture}
        \caption{
            Représentation à l'aide d'un arbre syntaxique de l'expression régulière
            une fois après avoir fait appel à \(linearization\) sur elle.
        }
    \end{figure}

\end{example}

\vphantom{}

\subsection{Conclusion}

On saisit aisément que ces expressions ont beau être simples (peu d'opération
comparé aux expressions régulières d'\textit{UNIX}). On peut voir qu'elles
permettent de décrire des langages très complexes et en quantité infinie. En
revanche, il est difficile de savoir si un mot est reconnu par une expression
régulière simplement. Par exemple est-ce que le mot \(eipipipipipip\) est
reconnu par cette expression \(((((o \cdot \varepsilon)+(\varepsilon \cdot
e))+((g\cdot \varepsilon) \cdot \varepsilon^*)) \cdot ((\varepsilon \cdot
i)\cdot (p+\varepsilon))^*)\)~? La réponse est oui. C'est pour cela qu'il
serait peut-être intéressant d'utiliser un autre objet pour reconnaitre des
mots, comme les automates que nous allons voir maintenant.