path: root/notes-inf105.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usepackage[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}[subsection]
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newtheorem{defn}[comcnt]{Définition}
\newtheorem{prop}[comcnt]{Proposition}
\newtheorem{lem}[comcnt]{Lemme}
\newtheorem{thm}[comcnt]{Théorème}
\newtheorem{cor}[comcnt]{Corollaire}
\newtheorem{scho}[comcnt]{Scholie}
\newtheorem{algo}[comcnt]{Algorithme}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\title{THL (Théorie des langages)\\Notes de cours \textcolor{red}{provisoires}}
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pretolerance=8000
\tolerance=50000


%
%
%

{\footnotesize
\tableofcontents
\par}

\bigbreak

\section{Alphabets, mots et langages}

\subsection{Introduction, alphabets, mots et longueur}

\thingy L'objet de ces notes, au confluent des mathématiques et de
l'informatique, est l'étude des \textbf{langages} : un langage étant
un ensemble de \textbf{mots}, eux-mêmes suites finies de
\textbf{lettres} choisies dans un \textbf{alphabet}, on va commencer
par définir ces différents termes avant de décrire plus précisément
l'objet de l'étude.

\thingy Le point de départ est donc ce que les mathématiciens
appelleront un \textbf{alphabet}, et qui correspond pour les
informaticiens à un \textbf{jeu de caractères}.  Il s'agit d'un
ensemble \emph{fini}, sans structure particulière, dont les éléments
s'appellent \textbf{lettres}, ou encore \textbf{caractères} dans une
terminologie plus informatique.

Les exemples mathématiques seront souvent donnés sur un alphabet tel
que l'alphabet à deux lettres $\{a,b\}$ ou à trois lettres
$\{a,b,c\}$.  On pourra aussi considérer l'alphabet $\{0,1\}$ appelé
\textbf{binaire} (puisque l'alphabet n'a pas de structure
particulière, cela ne fait guère de différence par rapport à n'importe
quel autre alphabet à deux lettres).  Dans un contexte informatique,
des jeux de caractères (=alphabets) souvent importants sont ASCII,
Latin-1 ou Unicode : en plus de former un ensemble, ces jeux de
caractère attribuent un numéro à chacun de leurs éléments (par
exemple, la lettre A majuscule porte le numéro 65 dans ces trois jeux
de caractères), mais cette structure supplémentaire ne nous
intéressera pas ici.  Dans tous les cas, il est important pour la
théorie que l'alphabet soit \emph{fini}.

L'alphabet sera généralement fixé une fois pour toutes dans la
discussion, et désigné par la lettre $\Sigma$ (sigma majuscule).

\thingy Un \textbf{mot} sur l'alphabet $\Sigma$ est une suite finie de
lettres (éléments de $\Sigma$) ; dans la terminologie informatique, on
parle plutôt de \textbf{chaîne de caractères}, qui est une suite finie
(=liste) de caractères.  Le mot est désigné en écrivant les lettres
les unes à la suite des autres : autrement dit, si $x_1,\ldots,x_n \in
\Sigma$ sont des lettres, le mot formé par la suite finie
$x_1,\ldots,x_n$ est simplement écrit $x_1\cdots x_n$.  À titre
d'exemple, $abbcab$ est un mot sur l'alphabet $\Sigma = \{a,b,c,d\}$,
et \texttt{foobar} est un mot (=chaîne de caractères) sur l'alphabet
ASCII.  (Dans un contexte informatique, il est fréquent d'utiliser une
sorte de guillemet pour délimiter les chaînes de caractères : on
écrira donc \texttt{\char`\"foobar\char`\"} pour parler du mot en
question.  Dans ces notes, nous utiliserons peu cette convention.)

L'ensemble des mots sur un alphabet $\Sigma$ est généralement
désigné $\Sigma^*$ (on verra que l'étoile fait partie d'un usage plus
général qui sera défini ci-dessous).  Par exemple, si $\Sigma =
\{0,1\}$, alors $\Sigma^*$ est l'ensemble (infini !) dont les éléments
sont toutes les suites finies binaires (=suites finies de $0$ et
de $1$).

\thingy Le nombre $n$ de lettres dans un mot $w \in \Sigma^*$ est
appelé la \textbf{longueur} du mot, et généralement notée $|w|$ ou
bien $\ell(w)$ : autrement dit, si $x_1,\ldots,x_n \in \Sigma$, alors
la longueur $\ell(x_1\cdots x_n)$ du mot $x_1\cdots x_n$, vaut $n$.
Ceci coïncide bien avec la notion usuelle de longueur d'une chaîne de
caractères en informatique.  À titre d'exemple, sur l'alphabet
$\Sigma=\{a,b,c,d\}$, la longueur du mot $abbcab$ vaut $6$ (on écrira
$|abbcab|=6$ ou bien $\ell(abbcab)=6$).

\thingy Quel que soit l'alphabet, il existe un unique mot de
longueur $0$, c'est-à-dire un unique mot n'ayant aucune lettre, appelé
le \textbf{mot vide} (ou la \textbf{chaîne [de caractères] vide}).
Étant donné qu'il n'est pas commode de désigner un objet par une
absence de symbole, on introduit un symbole spécial, généralement
$\varepsilon$, pour désigner ce mot vide : on a donc
$|\varepsilon|=0$.  On souligne que le symbole $\varepsilon$
\underline{ne fait pas partie} de l'alphabet $\Sigma$, c'est un
symbole \emph{spécial} qui a été introduit pour désigner le mot vide.
(Lorsque les mots sont délimités par des guillemets, comme il est
usage pour les chaînes de caractères en informatique, le mot vide n'a
pas besoin d'un symbole spécial : il s'écrit juste
\texttt{\char`\"\char`\"} — sans aucun caractère entre les
guillemets.)

{\footnotesize Lorsque l'alphabet $\Sigma$ est \emph{vide},
  c'est-à-dire $\Sigma=\varnothing$, alors le mot vide est le seul mot
  qui existe : on a $\Sigma^*=\{\varepsilon\}$ dans ce cas.  C'est la
  seule situation où l'ensemble $\Sigma^*$ des mots est un ensemble
  fini.  Dans la suite, nous négligerons parfois ce cas particulier,
  qu'on pourra oublier : c'est-à-dire que nous ferons parfois
  l'hypothèse tacite que $\Sigma \neq \varnothing$.\par}

La notation $\Sigma^+$ est parfois utilisée pour désigner l'ensemble
des mots \emph{non vides} sur l'alphabet $\Sigma$ (par opposition à
$\Sigma^*$ qui désigne l'ensemble de tous les mots, y compris le mot
vide).

\thingy\label{convention-on-words-of-length-one} Les mots d'une seule
lettre sont naturellement en correspondance avec les lettres
elles-mêmes : on identifiera souvent tacitement, quoique un peu
abusivement, une lettre $x\in\Sigma$ et le mot de longueur $1$ formé
de la seule lettre $x$.  (En informatique, cette identification entre
\emph{caractères} et \emph{chaînes de caractères de longueur $1$} est
faite par certains langages de programmation, mais pas par tous :
\textit{caveat programmator}.)  Ceci permet d'écrire par exemple
$\Sigma \subseteq \Sigma^*$ ou bien $|x|=1 \liff x\in\Sigma$.

\thingy\label{number-of-words-of-length-n} Si le cardinal de
l'alphabet $\Sigma$ vaut $\#\Sigma = N$, alors, pour chaque $n$, le
nombre de mots de longueur exactement $n$ est égal à $N^n$
(combinatoire classique).  Le nombre de mots de longueur $\leq n$ vaut
donc $1 + N + \cdots + N^n = \frac{N^{n+1}-1}{N-1}$ (somme d'une série
géométrique).


\subsection{Concaténation de mots, préfixes, suffixes, facteurs, sous-mots}

\thingy Si $u := x_1\cdots x_m$ et $v := y_1\cdots y_n$ sont deux
mots, de longueurs respectives $m$ et $n$, sur un même
alphabet $\Sigma$, alors on définit un mot $uv := x_1\cdots x_m
y_1\cdots y_n$ de longueur $m+n$, dont les lettres sont obtenues en
mettant bout à bout celles de $u$ puis celles de $v$ (dans cet ordre),
et on l'appelle \textbf{concaténation} (ou, si cela ne prête pas à
confusion, simplement \textbf{produit}) des mots $u$ et $v$.  (Dans un
contexte informatique, on parle de concaténation de chaînes de
caractères.)

\thingy Parmi les propriétés de la concaténation, signalons les faits
suivants :
\begin{itemize}
\item le mot vide $\varepsilon$ est « \textbf{neutre} » pour la
  concaténation, ce qui signifie par définition : $\varepsilon w = w
  \varepsilon = w$ quel que soit le mot $w \in \Sigma^*$ ;
\item la concaténation est « \textbf{associative} », ce qui signifie
  par définition : $u(vw) = (uv)w$ quels que soient les mots $u,v,w
  \in \Sigma^*$.
\end{itemize}

On peut traduire de façon savante ces deux propriétés en une phrase :
l'ensemble $\Sigma^*$ est un \textbf{monoïde}, d'élément
neutre $\varepsilon$, pour la concaténation (cela signifie exactement
ce qui vient d'être dit).

\thingy On a par ailleurs $|uv| = |u| + |v|$ (la longueur de la
concaténation de deux mots est la somme des concaténations), et on
rappelle par ailleurs que $|\varepsilon| = 0$ ; on peut traduire cela
de manière savante : la longueur est un \textbf{morphisme de monoïdes}
entre le monoïde $\Sigma^*$ des mots (pour la concaténation) et le
monoïde $\mathbb{N}$ des entiers naturels (pour l'addition) (cela
signifie exactement ce qui vient d'être dit).

{\footnotesize\thingy \textbf{Complément :} Le monoïde $\Sigma^*$
  possède la propriété suivante par rapport à l'ensemble $\Sigma$ : si
  $M$ est un monoïde quelconque (c'est-à-dire un ensemble muni d'une
  opération binaire associative $\cdot$ et d'un élément $e$ neutre
  pour cette opération), et si $\psi\colon \Sigma\to M$ est une
  application quelconque, alors il existe un unique morphisme de
  monoïdes $\hat\psi\colon \Sigma^* \to M$ (c'est-à-dire une
  application préservant le neutre et l'opération binaire) tel que
  $\hat\psi(x) = \psi(x)$ si $x\in\Sigma$.  (Démonstration : on a
  nécessairement $\hat\psi(x_1\cdots x_n) = \psi(x_1)\cdots
  \psi(x_n)$, or ceci définit bien un morphisme comme annoncé.)  On
  dit qu'il s'agit là d'une propriété « universelle », et plus
  précisément que $\Sigma^*$ est le \textbf{monoïde libre} sur
  l'ensemble $\Sigma$.  Par exemple, le morphisme « longueur »
  $\ell\colon\Sigma^*\to\mathbb{N}$ est le $\ell = \hat\psi$ obtenu en
  appliquant cette propriété à la fonction $\psi(x) = 1$ pour
  tout $x\in\Sigma$.\par}

\thingy\label{powers-of-a-word} Lorsque $w \in \Sigma^*$ et $r \in
\mathbb{N}$, on définit un mot $w^r$ comme la concaténation de $r$
facteurs tous égaux au mot $w$, autrement dit, comme la répétition $r$
fois du mot $w$.  Formellement, on définit par récurrence :
\begin{itemize}
\item $w^0 = \varepsilon$ (le mot vide),
\item $w^{r+1} = w^r w$.
\end{itemize}
(Ces définitions valent, d'ailleurs, dans n'importe quel monoïde.  On
peut constater que $w^r w^s = w^{r+s}$ quels que soient
$r,s\in\mathbb{N}$.)  On a bien sûr $|w^r| = r|w|$.

Cette définition sert notamment à désigner de façon concise les mots
comportant des répétitions d'une même lettre : par exemple, le mot
$aaaaa$ peut s'écrire tout simplement $a^5$, et le mot $aaabb$ peut
s'écrire $a^3 b^2$.  (De même que pour le mot vide, il faut souligner
que ces exposants ne font pas partie de l'alphabet.)

\thingy Lorsque $u,v,w \in \Sigma^*$ vérifient $w = uv$, autrement dit
lorsque le mot $w$ est la concaténation des deux mots $u$ et $v$, on
dira également :
\begin{itemize}
\item que $u$ est un \textbf{préfixe} de $w$, ou
\item que $v$ est un \textbf{suffixe} de $w$.
\end{itemize}

De façon équivalente, si $w = x_1\cdots x_n$ (où $x_1,\ldots,x_n \in
\Sigma$) est un mot de longueur $n$, et si $0\leq k\leq n$ est un
entier quelconque compris entre $0$ et $n$, on dira que $u :=
x_1\cdots x_k$ (c'est-à-dire, le mot formé des $k$ premières lettres
de $w$, dans le même ordre) est le \textbf{préfixe de longueur $k$}
de $w$, et que $v := x_{k+1}\cdots x_n$ (mot formé des $n-k$ dernières
lettres de $w$, dans le même ordre) est le \textbf{suffixe de
  longueur $n-k$} de $w$.  Il est clair qu'il s'agit bien là de
l'unique façon d'écrire $w = uv$ avec $|u|=k$ et $|v|=n-k$, ce qui
fait le lien avec la définition donnée au paragraphe précédent ;
parfois on dira que $v$ est le suffixe \textbf{correspondant} à $u$ ou
que $u$ est le préfixe correspondant à $v$ (dans le mot $w$).

Le mot vide est préfixe et suffixe de n'importe quel mot.  Le mot $w$
lui-même est aussi un préfixe et un suffixe de lui-même.  Entre les
deux, pour n'importe quelle longueur $k$ donnée, il existe un unique
préfixe et un unique suffixe de longueur $k$.  (Il peut tout à fait se
produire que le préfixe et le suffixe de longueur $k$ soient égaux
pour d'autres $k$ que $0$ et $|w|$, comme le montre l'exemple qui
suit.)

À titre d'exemple, le mot $abbcab$ sur l'alphabet $\Sigma=\{a,b,c,d\}$
a les sept préfixes suivants, rangés par ordre croissant de longueur :
$\varepsilon$ (le mot vide), $a$, $ab$, $abb$, $abbc$, $abbca$ et
$abbcab$ lui-même ; il a les sept suffixes suivants, rangés par ordre
croissant de longueur : $\varepsilon$ (le mot vide), $b$, $ab$, $cab$,
$bcab$, $bbcab$ et $abbcab$ lui-même.  Le suffixe correspondant au
préfixe $abb$ est $bcab$ puisque $abbcab = (abb)(bcab)$.

\thingy Comme généralisation à la fois de la notion de préfixe et de
celle de suffixe, on a la notion de facteur : si $u_0,v,u_1 \in
\Sigma^*$ sont trois mots quelconques sur un même alphabet $\Sigma$,
et si $w = u_0 v u_1$ est leur concaténation, on dira que $v$ est un
\textbf{facteur} de $w$.  Alors qu'un préfixe ou suffixe du mot $w$
est déterminé simplement par sa longueur, un facteur est déterminé par
sa longueur et l'emplacement à partir duquel il commence.

À titre d'exemple, les facteurs du mot $abbcab$ sont : $\varepsilon$
(le mot vide), $a$, $b$, $c$, $ab$, $bb$, $bc$, $ca$, $abb$, $bbc$,
$bca$, $cab$, $abbc$, $bbca$, $bcab$, $abbca$, $bbcab$ et $abbcab$
lui-même.

Dans un contexte informatique, ce que nous appelons ici « facteur »
est souvent appelé « sous-chaîne [de caractères] ».  Il ne faut
cependant pas confondre ce concept avec celui de sous-mot défini
ci-dessous.

\thingy\label{definition-subword} Si $u_0,\ldots,u_r$ et
$v_1,\ldots,v_r$ sont des mots sur un même alphabet $\Sigma$, on dira
que $v := v_1\cdots v_r$ est un \textbf{sous-mot} du mot $w := u_0 v_1
u_1 v_2 \cdots u_{r-1} v_r u_r$.  En plus clair, cela signifie que $v$
est obtenu en ne gardant que certaines lettres du mot $w$ (celles
des $v_i$), dans le même ordre, mais en en effaçant d'autres (celles
des $u_i$) ; à la différence du concept de facteur, celui de sous-mot
n'exige pas que les lettres gardées soient consécutives.

À titre d'exemple, le mot $acb$ est un sous-mot du mot $abbcab$
(obtenu en gardant les lettres soulignées ici :
$\underline{a}bb\underline{c}a\underline{b}$ ; pour se rattacher à la
définition ci-dessus, on pourra prendre $u_0 = \varepsilon$ et $v_1 =
a$ et $u_1 = bb$ et $v_2 = c$ et $u_2 = a$ et $v_3 = b$ et $u_3 =
\varepsilon$).

\thingy\label{definition-mirror-word} Si $w = x_1\cdots x_n$, où
$x_1,\ldots,x_n \in \Sigma$, est un mot de longueur $n$ sur un
alphabet $\Sigma$, alors on définit son mot \textbf{miroir} ou
\textbf{transposé}, parfois noté $w^{\textsf{R}}$ ou $w^{\textsf{T}}$
(parfois les exposants sont écrits à gauche), comme le mot $x_n\cdots
x_1$ dont les lettres sont les mêmes que celles de $w$ mais dans
l'ordre inverse.  À titre d'exemple, $(ababb)^{\textsf{R}} = bbaba$.
On remarquera que $(w_1 w_2)^{\textsf{R}} = w_2^{\textsf{R}}
w_1^{\textsf{R}}$ si $w_1,w_2$ sont deux mots quelconques.

Un mot $w$ est dit \textbf{palindrome} lorsque $w = w^{\textsf{R}}$.


\subsection{Langages et opérations sur les langages}

\thingy Un \textbf{langage} $L$ sur l'alphabet $\Sigma$ est simplement
un ensemble de mots sur $\Sigma$.  Autrement dit, il s'agit d'un
sous-ensemble (=une partie) de l'ensemble $\Sigma^*$ de tous les mots
sur $\Sigma^*$ : en symboles, $L \subseteq \Sigma^*$.  On souligne
qu'on ne demande pas que $L$ soit fini (mais il peut l'être).

\thingy À titre d'exemple, l'ensemble $\{d,dc,dcc,dccc,dcccc,\ldots\}
= \{dc^r \colon r\in\mathbb{N}\}$ des mots formés d'un $d$ suivi d'un
nombre quelconque (éventuellement nul) de $c$ est un langage sur
l'alphabet $\Sigma = \{a,b,c,d\}$.  On verra plus loin que ce langage
est « rationnel » (et pourra être désigné par l'expression rationnelle
$dc{*}$).

Voici quelques autres exemples de langages :
\begin{itemize}
\item Le langage (fini) $\{foo,bar,baz\}$ formé des seuls trois mots
  $foo$, $bar$, $baz$ sur l'alphabet $\Sigma = \{a,b,f,o,r,z\}$.
\item Le langage (fini) formé des mots de longueur exactement $42$ sur
  l'alphabet $\Sigma = \{p,q,r\}$.  Comme on l'a vu
  en \ref{number-of-words-of-length-n}, cet ensemble a pour cardinal
  exactement $3^{42}$.
\item Le langage (fini) formé du seul mot vide (=mot de longueur
  exactement $0$) sur l'alphabet, disons, $\Sigma = \{p,q,r\}$.  Ce
  langage $\{\varepsilon\}$ a pour cardinal $1$ (ou $3^0$ si on veut).
  Il ne faut pas le confondre avec le suivant :
\item Le langage vide, qui ne contient aucun mot (sur un alphabet
  quelconque).  Ce langage a pour cardinal $0$.
\item Le langage formé des mots de une seule lettre sur un alphabet
  $\Sigma$, qu'on peut identifier à $\Sigma$ lui-même (en identifiant
  un mot de une lettre à la lettre en question).
\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui
  commencent par trois $a$ consécutifs : ou, si on préfère, qui ont le
  mot $aaa$ comme préfixe.
\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui
  contiennent trois $a$ consécutifs ; ou, si on préfère, qui ont $aaa$
  comme facteur.
\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui
  contiennent au moins trois $a$, non nécessairement consécutifs ; ou,
  si on préfère, qui ont $aaa$ comme sous-mot.
\item Le langage sur l'alphabet $\Sigma=\{a\}$ formé de tous les mots
  dont la longueur est un nombre premier ($L = \{aa, aaa, a^5, a^7,
  a^{11},\ldots\}$).  Ce langage est infini.
\item Le langage sur l'alphabet $\Sigma=\{0,1\}$ formé de tous les
  mots commençant par un $1$ et qui, interprétés comme un nombre écrit
  en binaire, désignent un nombre premier ($L = \{10, 11, 101, 111,
  1011, \ldots\}$).
\item Le langage sur l'alphabet Unicode formé de tous les mots qui
  constituent un document XML bien-formé d'après la spécification
  XML 1.0.
\end{itemize}

\thingy On pourrait aussi considérer un langage (sur
l'alphabet $\Sigma$) comme une \emph{propriété} des mots (sur
l'alphabet en question).  Précisément, si $P$ est une propriété qu'un
mot $w \in \Sigma^*$ peut ou ne pas avoir, on considère le langage
$L_P = \{w \in \Sigma^* : w \text{~a la propriété~} P\}$, et
inversement, si $L \subseteq \Sigma^*$ est un langage, on considère la
propriété « appartenir à $L$ » : en identifiant la propriété et le
langage qu'on vient d'associer l'un à l'autre (par exemple, le langage
des mots commençant par $a$ et la propriété « commencer par $a$ »), un
langage pourrait être considéré comme une propriété des mots.

{\footnotesize(Ceci n'a rien de spécifique aux langages : une partie
  d'un ensemble $E$ quelconque peut être identifiée à une propriété
  que les éléments de $E$ peuvent ou ne pas avoir, à savoir,
  appartenir à la partie en question.)\par}

On évitera de faire cette identification pour ne pas introduire de
confusion, mais il est utile de la garder à l'esprit : par exemple,
dans un langage de programmation fonctionnel, un « langage » au sens
de ces notes peut être considéré comme une fonction (pure,
c'est-à-dire, déterministe et sans effet de bord) prenant en entrée
une chaîne de caractères et renvoyant un booléen.

\thingy Si $L_1$ et $L_2$ sont deux langages sur un même
alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on
peut former les langages \textbf{union} $L_1\cup L_2$ et
\textbf{intersection} $L_1\cap L_2$ qui sont simplement les opérations
ensemblistes usuelles (entre parties de $\Sigma^*$).

Les opérations correspondantes sur les propriétés de mots sont
respectivement le « ou logique » (=disjonction) et le « et logique »
(=conjonction) : à titre d'exemple, sur $\Sigma = \{a,b\}$ si $L_1$
est le langage des mots commençant par $a$ et $L_2$ le langage des
mots finissant par $b$, alors $L_1 \cup L_2$ est le langage des mots
commençant par $a$ \emph{ou bien} finissant par $b$, tandis que $L_1
\cap L_2$ est le langage des mots commençant par $a$ \emph{et}
finissant par $b$.

\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, autrement dit
$L \subseteq \Sigma^*$, on peut former le langage $\Sigma^*\setminus
L$, parfois noté simplement $\overline L$ si ce n'est pas ambigu, dit
\textbf{complémentaire} de $L$, et qui est simplement l'ensemble des
mots sur $\Sigma$ \emph{n'appartenant pas} à $L$.  L'opération
correspondante sur les propriétés de mots est la négation logique.

À titre d'exemple, sur $\Sigma=\{a,b\}$, si $L$ est le langage des
mots commençant par $a$, alors $\overline{L}$ est le langage des mots
ne commençant pas par $a$, c'est-à-dire, la réunion de
$\{\varepsilon\}$ et du langage des mots commençant par $b$ (car sur
$\Sigma=\{a,b\}$, un mot ne commençant pas par $a$ est vide ou bien
commence par $b$).

\thingy Si $L_1$ et $L_2$ sont deux langages sur un même
alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on
peut former le langage \textbf{concaténation} $L_1 L_2$ : il est
défini comme l'ensemble des mots $w$ qui peuvent s'écrire comme
concaténation d'un mot $w_1$ de $L_1$ et d'un mot $w_2$ de $L_2$, soit
\[
\begin{aligned}
L_1 L_2 &= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\
 &= \{w \in \Sigma^* : \exists w_1 \in L_1\, \exists w_2 \in L_2\,(w = w_1 w_2)\}\\
\end{aligned}
\]

À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L_1
= \{a,bb\}$ et $L_2 = \{bc, cd\}$ alors $L_1 L_2 = \{abc, acd, bbbc,
bbcd\}$.

\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, autrement dit
$L \subseteq \Sigma^*$, et si $r \in \mathbb{N}$, on peut définir un
langage $L^r$, par analogie avec \ref{powers-of-a-word}, comme le
langage $L^r = \{w_1\cdots w_r : w_1,\ldots,w_r \in L\}$ formé des
concaténation de $r$ mots appartenant à $L$, ou si on préfère, par
récurrence :
\begin{itemize}
\item $L^0 = \{\varepsilon\}$,
\item $L^{r+1} = L^r L$.
\end{itemize}

À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L =
\{a,bb\}$, alors $L^2 = \{aa, abb, bba, bbbb\}$ et $L^3 = \{aaa, aabb,
abba, abbbb, \penalty-100 bbaa, bbabb, bbbba, bbbbbb\}$.

\emph{Attention}, $L^r$ n'est pas le langage $\{w^r : w\in L\}$ formé
des répétitions $r$ fois ($w^r$) des mots $w$ de $L$ : c'est le
langage des concaténations de $r$ mots appartenant à $L$ \emph{mais
  ces mots peuvent être différents}.  À titre d'exemple, si $L =
\{a,b\}$ alors $L^r$ est le langage formé des $2^r$ mots de longueur
exactement $r$ sur $\{a,b\}$, ce n'est pas l'ensemble à deux éléments
$\{a^r, b^r\}$ formé des seuls deux mots $a^r = aaa\cdots a$ et $b^r =
bbb\cdots b$.

\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, on définit
enfin l'\textbf{étoile de Kleene} $L^*$ de $L$ comme le langage formé
des concaténations d'un nombre \emph{quelconque} de mots appartenant
à $L$, c'est-à-dire
\[
\begin{aligned}
L^* &= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
&= \{w_1\cdots w_r : r\in\mathbb{N},\, w_1,\ldots,w_r\in L\}\\
\end{aligned}
\]

Comme ci-dessus, il faut souligner que les mots $w_1,\ldots,w_r$
concaténés n'ont pas à être égaux : notamment, $\{a,b\}^*$ est le
langage formé de tous les mots sur l'alphabet $\{a,b\}$, pas le
langage $\{a\}^* \cup \{b\}^*$ formé des mots obtenus en répétant la
lettre $a$ ou en répétant la lettre $b$.

On remarquera que la définition de $L^*$ ci-dessus redonne bien,
lorsqu'on l'applique à l'alphabet $\Sigma$ lui-même (considéré comme
langage des mots de longueur $1$), l'ensemble $\Sigma^*$ de tous les
mots : la notation $\Sigma^*$ est donc justifiée \textit{a
  posteriori}.

Le mot vide appartient toujours à $L^*$ (quel que soit $L$) puisque
$L^0 = \{\varepsilon\}$ et qu'on peut prendre $r=0$ ci-dessus
(autrement dit, le mot vide est la concaténation de zéro mots de $L$).

\thingy\label{kleene-plus} On introduit parfois la notation $L^+ =
\bigcup_{r=1}^{+\infty} L^r = \{w_1\cdots w_r : r>0,\penalty-100\,
w_1,\ldots,w_r\in L\}$ pour l'ensemble des mots formés par
concaténation d'un nombre \emph{non nul} de mots de $L$.  Lorsque le
mot vide $\varepsilon$ n'appartient pas déjà à $L$, ce langage $L^+$
diffère de $L^*$ seulement en ce qu'il ne contient pas $\varepsilon$ ;
tandis que si $\varepsilon$ appartient déjà à $L$, alors $L^+$ est
égal à $L^*$.  En toute généralité, on a $L^+ = LL^*$.

\thingy\label{definition-mirror-language} En rappelant la définition
du mot miroir faite en \ref{definition-mirror-word}, si $L$ est un
langage sur l'alphabet $\Sigma$, on définit le langage miroir
$L^{\mathsf{R}}$ comme l'ensemble des mots miroirs des mots de $L$,
c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$.


\subsection{Langages rationnels et expressions rationnelles}\label{subsection-rational-languages}

\thingy Soit $\Sigma$ un alphabet.  On va considérer les langages
de base triviaux suivants :
\begin{itemize}
\item le langage vide $\varnothing$,
\item le langage formé du seul mot vide, $\{\varepsilon\}$, et
\item les langages formés d'un seul mot lui-même formé d'une seule
  lettre, $\{x\}$ pour chaque $x\in\Sigma$,
\end{itemize}
et on va les combiner par les opérations dites « rationnelles »
suivantes :
\begin{itemize}
\item la réunion $(L_1,L_2) \mapsto L_1 \cup L_2$,
\item la concaténation $(L_1,L_2) \mapsto L_1 L_2$, et
\item l'étoile de Kleene $L \mapsto L^*$.
\end{itemize}

On obtient ainsi une certaine famille de langages (cf. ci-dessous pour
une définition plus précise), qu'on appelle \textbf{langages
  rationnels} : les langages rationnels sont exactement ceux qui
peuvent s'obtenir à partir des langages de base énumérés ci-dessus par
application (un nombre fini de fois) des opérations qu'on vient de
dire.  Autrement dit, la réunion de deux langages rationnels, la
concaténation de deux langages rationnels, et l'étoile de Kleene d'un
langage rationnel, sont rationnels, et les langages rationnels sont
exactement ceux qu'on obtient ainsi à partir des langages de base.

À titre d'exemple, sur l'alphabet $\{a,b,c,d\}$, comme le langage
$\{c\}$ (formé du seul mot $c$) est rationnel, son étoile de Kleene,
c'est-à-dire $\{c\}^* = \{\varepsilon, c, cc, ccc, cccc,\ldots\}$, est
rationnel, et comme $\{d\}$ l'est aussi, la concaténation
$\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$ est encore un langage
rationnel.

\thingy Formellement, la définition des langages rationnelles est la
suivante : un ensemble $\mathscr{C} \subseteq \mathscr{P}(\Sigma^*)$
de langages (où $\mathscr{P}(\Sigma^*)$ est l'ensemble des parties de
$\Sigma^*$, i.e., l'ensemble de tous les langages sur $\Sigma$) est
dit \emph{stable par opérations rationnelles} lorsqu'il est stable par
les opérations de réunion, concaténation et étoile de Kleene, i.e., si
$L_1,L_2 \in \mathscr{C}$ alors $L_1\cup L_2 \in \mathscr{C}$ et $L_1
L_2 \in \mathscr{C}$, et si $L \in \mathscr{C}$ alors $L^* \in
\mathscr{C}$ ; le \emph{plus petit} (pour l'inclusion) ensemble de
langages stable par opérations rationnelles et contenant les langages
$\varnothing$, $\{\varepsilon\}$ et $\{x\}$ pour $x \in \Sigma$
(i.e. $\varnothing\in\mathscr{C}$, $\{\varepsilon\} \in \mathscr{C}$
et si $x\in\Sigma$ alors $\{x\}\in\mathscr{C}$), ou plus exactement,
l'intersection de tous les ensembles $\mathscr{C}$ vérifiant tous ces
propriétés, est la classe $\mathscr{R}$ des langages rationnels.

\emph{Attention !}, le fait que la classe $\mathscr{R}$ des langages
rationnels soit stable par concaténation signifie que si $L_1$ et
$L_2$ sont rationnels alors le langage $L_1 L_2$ (formé de tous les
mots concaténés d'un mot de $L_1$ et d'un mot de $L_2$) est
rationnel ; \emph{cela ne signifie pas} qu'un langage rationnel donné
soit stable par concaténation (un langage stable $L$ par concaténation
est un langage tel que si $w_1,w_2\in L$ alors $w_1 w_2 \in L$).

\thingy Pour décrire la manière dont un langage rationnel est fabriqué
(à partir des langages de base par les opérations rationnelles), comme
il est malcommode d'écrire quelque chose comme $\{d\}(\{c\}^*)$, on
introduit un nouvel objet, les \textbf{expressions rationnelles}
(certains préfèrent le terme d'\textbf{expressions régulières}), qui
sont des expressions servant à désigner un langage rationnel.  Par
exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on parlera du
langage désigné par l'expression rationnelle $dc{*}$.

Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$)
est un mot sur l'alphabet $\Sigma \cup \{\bot,
\underline{\varepsilon}, {(}, {)}, {|}, {*}\}$, où $\bot,
\underline{\varepsilon}, {(}, {)}, {|}, {*}$ sont de nouveaux
caractères \emph{n'appartenant pas} à l'alphabet $\Sigma$, appelés
\textbf{métacaractères}, et qui servent à marquer la manière dont est
formée l'expression rationnelle.  On définit simultanément la notion
d'expression rationnelle $r$ et de \textbf{langage dénoté} (ou
\textbf{désigné}) $L_r$ par l'expression $r$, de la manière suivante :
\begin{itemize}
\item $\bot$ est une expression rationnelle et son langage dénoté
  est $L_\bot := \varnothing$,
\item $\underline{\varepsilon}$ est une expression rationnelle et son
  langage dénoté est $L_{\underline{\varepsilon}} :=
  \{\varepsilon\}$,
\item si $x\in\Sigma$ est une lettre de l'alphabet $\Sigma$, alors le
  mot $x$ est une expression rationnelle et son langage dénoté
  est $L_x := \{x\}$,
\item si $r_1,r_2$ sont deux expressions rationnelles et $L_1 =
  L_{r_1}$ et $L_2 = L_{r_2}$ les langages dénotés correspondants,
  alors $r_1 r_2$ est une expression rationnelle et son langage
  dénoté est $L_{r_1 r_2} := L_1 L_2$,
\item si $r_1,r_2$ sont deux expressions rationnelles et $L_1 =
  L_{r_1}$ et $L_2 = L_{r_2}$ les langages dénotés correspondants,
  alors $(r_1|r_2)$ est une expression rationnelle et son langage
  dénoté est $L_{(r_1|r_2)} := L_1\cup L_2$,
\item si $r$ est une expression rationnelle et $L = L_r$ les langage
  dénoté correspondant, alors $(r){*}$ est une expression rationnelle
  et son langage dénoté est $L_{(r){*}} := L^*$.
\end{itemize}

À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une
expression rationnelle qui dénote le langage $\{c\}$, donc $(c){*}$ en
est une qui dénote le langage $\{c\}^* = \{\varepsilon, c, cc,
ccc,\ldots\}$, et enfin $d(c){*}$ en est une qui dénote le langage $\{d,
dc, dcc, \ldots\}$ des mots formés d'un $d$ et d'une succession
quelconques de $c$.  Voici quelques autres exemples, toujours sur
$\Sigma = \{a,b,c,d\}$ :
\begin{itemize}
\item l'expression rationnelle $(a|b)$ dénote le langage $\{a\} \cup
  \{b\} = \{a,b\}$ formé des deux mots d'une seule lettre $a$ et $b$ ;
\item l'expression rationnelle $(a|b)c$ dénote le langage
  $\{a,b\}\{c\} = \{ac,bc\}$, de même que $(ac|bc)$ ;
\item l'expression rationnelle $(bc){*}$ dénote le langage $\{bc\}^* =
  \{\varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ;
\item l'expression rationnelle $(a|(bc){*})$ dénote le langage $\{a\}
  \cup \{bc\}^* = \{a, \varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ;
\item l'expression rationnelle $(a|(bc){*})d$ dénote le langage $\{a, d,
  bcd, bcbcd, bcbcbcd, \ldots\}$ ;
\item l'expression rationnelle $\bot d$ dénote le langage
  vide $\varnothing$ (car il n'y a pas de mot dans le langage vide,
  donc pas non plus de mot dans sa concaténation avec le
  langage $\{d\}$) ;
\item l'expression rationnelle $\underline{\varepsilon} d$ dénote le
  langage $\{d\}$ ;
\item l'expression rationnelle $(\bot|c)$ dénote le langage $\{c\}$ ;
\item l'expression rationnelle $(\underline{\varepsilon}|c)$ dénote le
  langage $\{\varepsilon, c\}$.
\end{itemize}

Un langage rationnel est par construction la même chose qu'un langage
pour lequel il existe une expression rationnelle qui le dénote.

On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$
lorsque ce mot appartient au langage qu'elle dénote (i.e., $w \in
L_r$).  Par exemple, $dccc$ vérifie l'expression rationnelle $d(c){*}$.

\thingy Deux expressions rationnelles $r_1,r_2$ sont dites
\textbf{équivalentes} lorsqu'elles dénotent le même langage.  À titre
d'exemple, sur l'alphabet $\{a,b\}$, les deux expressions rationnelles
$(ab){*}a$ et $a(ba){*}$ sont équivalentes (toutes les deux dénotent
le langage $\{a, aba, ababa, \ldots\}$ formé des mots commençant et
finissant par un $a$ et dans lesquels chaque paire de $a$ est séparée
par un unique $b$).

\thingy La convention de parenthésage introduite ci-dessus est
inambiguë mais parfois inutilement lourde : on se permettra parfois de
l'alléger, par exemple d'écrire $(r_1|r_2|r_3)$ pour $((r_1|r_2)|r_3)$
(ou pour $(r_1|(r_2|r_3))$, ce qui n'a guère d'importance vu qu'elles
dénotent le même langage), ou encore $x{*}$ pour $(x){*}$ lorsque $x$
est formé d'un seul caractère.  La convention essentielle est que
l'opération d'étoile ${*}$ est la plus prioritaire ($ab{*}$ se lit
comme $a(b){*}$ et non pas comme $(ab){*}$), la concaténation vient
après, et la barre de disjonction $|$ est la moins prioritaire
($ab|cd$ se lit comme $(ab|cd)$ et pas comme $a(b|c)d$).

{\footnotesize Les métacaractères $\bot$ et $\underline{\varepsilon}$
  sont introduits ici par souci de complétude mais font rarement
  utilisés dans les expressions rationnelles (le métacaractère
  $\underline{\varepsilon}$ a été souligné parce qu'il s'agit d'une
  vraie lettre et non pas du mot vide ; on peut ignorer cette
  subtilité qui n'a que très peu d'importance).\par}

La barre de disjonction que nous avons notée ${|}$ est souvent plutôt
notée $+$ par les mathématiciens\footnote{Dans le même contexte
  mathématique, il est alors fréquent de noter $0$ pour ce que nous
  avons noté $\bot$ (c'est un élément neutre pour la disjonction), et
  on en profite souvent pour noter $1$ pour $\varepsilon$ et/ou
  $\underline{\varepsilon}$ (c'est un élément neutre pour la
  concaténation).}.  Il y a ici un risque de confusion lié au fait
que, en informatique, le symbole \texttt{+} est utilisé par de
nombreux moteurs d'expressions régulières (par exemple,
\texttt{egrep}) pour dénoter l'opération évoquée en \ref{kleene-plus},
i.e., « au moins une répétition » alors que l'étoile signifie « un
  nombre quelconque de répétitions » : si on veut, $r{+}$ a le même
sens que $rr{*}$.  Dans le même contexte, le symbole \texttt{?} est
souvent utilisé pour désigner « au plus une répétition » : si on veut,
$r{?}$ a le même sens que $(\underline{\varepsilon}|r)$.


\subsection{Remarques sur les moteurs d'expressions régulières en informatique}

\thingy Dans le monde informatique, il existe de nombreux
\emph{moteurs d'expressions régulières}, c'est-à-dire outils (qu'il
s'agisse de primitives d'un langage, de bibliothèques externes, de
programmes en ligne de commande, ou autres) permettant de savoir si un
mot est reconnu par une expression régulière (=rationnelle), autrement
dit, s'il appartient au langage dénoté par elle.  L'un de ces moteurs
est le programme \texttt{egrep} standard sous Unix/POSIX.

\thingy Les expressions régulières au sens de ces différents moteurs
sont généralement plus puissantes que les expressions rationnelles au
sens mathématique défini ci-dessus : différentes extensions permettent
de désigner des langages qui ne sont pas rationnels au sens
mathématique.  L'extension la plus fréquente est celle des
\emph{références arrière} (ou \emph{backreferences} en anglais) qui
permettent de demander qu'un facteur du mot se retrouve à un autre
emplacement.  Par exemple, pour beaucoup de moteurs (notamment
\texttt{egrep}), l'expression régulière \texttt{(a*)b\char"5C\relax 1}
désigne le langage $\{a^nba^n : a\in\mathbb{N}\} = \{b,aba,
aabaa,\ldots\}$ des mots formés d'un nombre quelconque de $a$ puis
d'un $b$ puis de la \emph{même suite de $a$}, et ce langage
\emph{n'est pas rationnel} au sens mathématique (ce sera une
conséquence du « lemme de pompage »).

\thingy Il existe aussi un certain nombre de constructions qui, sans
dépasser la puissance des expressions rationnelles au sens
mathématique, apportent des commodités d'écriture dans un contexte
informatique.  On a déjà mentionné les symboles \texttt{+} (pour « au
  moins une répétition » : $r{+}$ est équivalent à $rr{*}$) et
\texttt{?} (pour « au plus une répétition » : $r{?}$ est équivalent à
$(\underline{\varepsilon}|r)$).  Parmi d'autres constructions du
genre, mentionnons encore le point \texttt{.} qui désigne un caractère
quelconque de l'alphabet (on peut le voir comme une abréviation pour
$(x_1|x_2|\ldots|x_N)$ où $x_1,x_2,\ldots,x_N$ sont tous les éléments
de $\Sigma$ — ce qui serait très fastidieux à écrire si on devait
énumérer tout Unicode), ou bien \texttt{[$xyz$]} qui désigne un
caractère quelconque parmi ceux listés (c'est donc la même chose que
$(x|y|z)$ mais cela ne fonctionne qu'avec des caractères individuels ;
en contrepartie, on peut écrire des intervalles comme \texttt{[a-z]}
qui désigne un caractère quelconque entre \texttt{a} et \texttt{z}
dans l'ordre ASCII/Unicode, ou bien des négations d'intervalles comme
\texttt{[\char"5Ea-z]} qui désigne un caractère qui \emph{n'est pas}
entre \texttt{a} et \texttt{z}).

Toutes sortes d'autres racourcis ou commodités de notation peuvent
exister, par exemple \texttt{\char"5C<} et \texttt{\char"5C>} pour
désigner un début et une fin de mot (la définition précise de « mot »
pouvant varier), ou encore \texttt{$r$\{$n_1$,$n_2$\}} qui cherche
entre $n_1$ et $n_2$ répétitions de $r$.

\thingy Une autre subtilité est que la plupart des moteurs
d'expressions régulières en informatique vont, par défaut,
\emph{rechercher un facteur} (appelé « sous-chaîne » en informatique)
vérifiant l'expression à l'intérieur de la chaîne donnée, plutôt que
tester si la chaîne elle-même vérifie l'expression.  Pour éviter ce
comportement, on peut utiliser des \emph{ancres}, typiquement
commandées par les caractères \texttt{\char"5E} et \texttt{\char"24}
qui servent à ancrer l'expression au début et à la fin de la chaîne
respectivement : c'est-à-dire que rechercher \texttt{a} recherche un
\texttt{a} quelconque à l'intérieur de la chaîne donnée, rechercher
\texttt{\char"5E\relax a} demande que le \texttt{a} soit au début de
la chaîne donnée rechercher \texttt{a\char"24} demande que le
\texttt{a} soit à la fin de la chaîne donnée, et rechercher
\texttt{\char"5E\relax a\char"24} demande que la chaîne donnée soit
exactement \texttt{a} (cet exemple n'est donc pas très utile, mais de
façon générale, trouver si une chaîne vérifie une expression
rationnelle $r$, revient à y chercher \texttt{\char"5E\relax
  $r$\char"24}).

\thingy Comme les expressions régulières en informatique sont
représentées par des chaînes de caractères qui appartiennent au même
alphabet (ASCII ou Unicode) que les chaînes sur lesquelles on effectue
la recherche, le problème se pose de distinguer les métacaractères
(l'étoile de Kleene \texttt{*}, par exemple) des caractères eux-mêmes
(comment rechercher les chaînes contenant le caractère \texttt{*} si
\texttt{*} est utilisé par l'étoile de Kleene ?).  La solution est
d'introduire un mécanisme d'\emph{échappement} : ainsi,
\texttt{x\char"5C*} recherche un \texttt{x} suivi d'un
astérisque \texttt{*}, tandis que \texttt{x*} recherche un nombre
quelconque de répétitions de la lettre \texttt{x}.

\thingy Il existe malheureusement de nombreuses différences, parfois
très subtiles, entre moteurs, ne serait-ce que dans les notations : un
moteur pourra par exemple noter \texttt{(?)} ce qu'un autre note
\texttt{\char"5C(\char"5C?\char"5C)} et vice versa.  La seule solution
est de consulter attentivement la documentation de chaque moteur
d'expressions régulières pour connaître la syntaxe utilisée.

Signalons tout de même qu'il existe deux principales familles de
syntaxes d'expressions régulières en informatique : les expressions
régulières « POSIX étendues », utilisée notamment par le programme
Unix \texttt{egrep}, et les expressions régulières Perl, qui ont été
réadaptées dans beaucoup de langages, notamment Java, JavaScript,
Python et d'autres.

\thingy Signalons comme complication supplémentaire que dans de
nombreux langages, les expressions régulières sont saisies comme des
chaînes de caractères plutôt que d'avoir une syntaxe spéciale, et ceci
a pour effet d'introduire un niveau supplémentaire d'échappement : par
exemple, en Java, pour rechercher si une chaîne de caractères $s$
contient un astérisque, on utilisera
\texttt{$s$.matches("\char"5C\char"5C*")} puisque l'expression
régulière à utiliser est \texttt{\char"5C*} et que cette chaîne de
caractères s'écrit \texttt{"\char"5C\char"5C*"} en Java.


\section{Automates finis}

\setcounter{comcnt}{0}

\thingy Les automates finis sont un modèle de calcul particulièrement
simple et particulièrement appropriés à l'étude et à l'analyse des
langages rationnels.  Il faut imaginer un automate fini comme une
machine disposant d'une quantité finie (et sous-entendu, très limitée)
de mémoire : la configuration complète de cette mémoire est décrite
par un \emph{état}, qui appartient à un ensemble fini d'états
possibles.  L'automate prendra une décision (passer dans un nouvel
état) en fonction de son état actuel et de la lettre qu'on lui donne à
consommer.

\subsection{Automates finis déterministes (=DFA)}

\thingy\label{definition-dfa} Un \textbf{automate fini déterministe},
ou en abrégé \textbf{DFA} (pour \textit{deterministic finite
  automaton}), sur un alphabet $\Sigma$ est la donnée
\begin{itemize}
\item d'un ensemble fini $Q$ dont les éléments sont appelés
  \textbf{états},
\item d'un état $q_0 \in Q$ appelé \textbf{état initial},
\item d'un ensemble $F \subseteq Q$ d'états appelés états
  \textbf{finaux}\footnote{Le pluriel de « final » est indifféremment
    « finaux » ou « finals ».} ou \textbf{acceptants},
\item d'une fonction $\delta \colon Q\times\Sigma \to Q$ appelée
  \textbf{fonction de transition}.
\end{itemize}

\thingy Graphiquement, on représente un DFA comme un graphe orienté
aux arêtes étiquetées par des éléments de $\Sigma$ : plus exactement,
on trace un nœud pour chaque élément $q \in Q$, et lorsque
$\delta(q,x) = q'$ on introduit une flèche $q \to q'$ étiquetée par la
lettre $x$.  La condition sur $\delta$ (pour être un DFA) est alors
que, pour chaque état $q \in Q$ et chaque lettre $x \in \Sigma$, il
existe une unique arête partant de $q$ et étiquetée par $x$.  En
outre, on introduit une flèche pointant de nulle part vers $q_0$, et
pour chaque $q\in F$ une flèche pointant de $q$ vers nulle
part\footnote{Certains auteurs préfèrent d'autres conventions, par
  exemple celle consistant à entourer deux fois les états finaux.}.

Lorsque plusieurs arêtes étiquetées par des symboles $x,y$ différents
relient les mêmes sommets $q,q'$ (i.e., lorsqu'on a à la fois
$\delta(q,x) = q'$ et $\delta(q,y) = q'$), on pourra écrire « $x,y$ »
ou « $x|y$ » sur l'arête en question (et ne la tracer qu'une seule
fois).  Voir \ref{discussion-example2} ci-dessous pour un exemple.

\thingy\label{discussion-example1} Pour donner un exemple simple,
l'automate sur $\Sigma = \{a,b\}$ représenté ci-dessous a $Q =
\{0,1\}$ et $q_0 = 0$ et $F = \{1\}$ et la fonction de transition
$\delta$ donnée par $\delta(0,a) = 0$ et $\delta(0,b) = 1$ et
$\delta(1,a) = 1$ et $\delta(1,b) = 0$.  On pourra se convaincre (une
fois lues les définitions plus loin) que cet automate accepte les mots
dont le nombre de $b$ est pair.

\begin{center}
%%% begin example1 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (98bp,20.306bp) [draw,circle,state,final] {$1$};
  \node (q0) at (18bp,20.306bp) [draw,circle,state,initial] {$0$};
  \draw [->] (q1) ..controls (75.212bp,3.6347bp) and (64.284bp,-1.3057bp)  .. (54bp,1.3057bp) .. controls (50.042bp,2.3107bp) and (46.047bp,3.8633bp)  .. node[auto] {$b$} (q0);
  \draw [->] (q0) ..controls (46.106bp,20.306bp) and (58.578bp,20.306bp)  .. node[auto] {$b$} (q1);
  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
  \draw [->] (q0) to[loop above] node[auto] {$a$} (q0);
%
\end{tikzpicture}

%%% end example1 %%%
\end{center}

\thingy Il faut comprendre le fonctionnement d'un DFA de la manière
suivante : initialement, l'automate est dans l'état initial $q_0$.  On
va lui présenter un mot $w \in \Sigma^*$, lettre par lettre, de la
gauche vers la droite : i.e., si $w = x_1\cdots x_n$ on va faire
consommer à l'automate les lettres $x_1,x_2,\ldots,x_n$ dans cet
ordre.  Le fait de consommer une lettre $x$ fait passer l'automate de
l'état $q$ à l'état $\delta(q,x)$ (autrement dit, l'automate passe
successivement dans les états $q_0$ puis $q_1 := \delta(q_0,x_1)$ puis
$q_2 := \delta(q_1,x_2)$, et ainsi de suite jusqu'à $q_n :=
\delta(q_{n-1},x_n)$) ; on dit que l'automate effectue les transitions
$q_0\to q_1$ (en consommant $x_1$) puis $q_1\to q_2$ (en
consommant $x_2$) et ainsi de suite.  Si $q_n$ est l'état dans lequel
se trouve l'automate une fois qu'il a consommé le mot $w$, on dira que
l'automate \emph{acepte} ou \emph{rejette} le mot selon que $q_n \in
F$ ou que $q_n \not\in F$.

Graphiquement, on peut présenter la procédure de la manière suivante :
on part de l'état $q_0$ (sommet du graphe représentant l'automate)
indiqué par la flèche entrante (pointant de nulle part), et pour
chaque lettre du mot $w = x_1\cdots x_n$ considéré, on suit l'arête
portant ce symbole (et partant de l'état où on se trouve
actuellement).  Si à la fin l'état $q_n$ est acceptant (représenté par
une flèche pointant vers nulle part), le mot $w$ est accepté, sinon il
est rejeté.

\thingy\label{definition-multiple-transition-function} Formellement :
si $A = (Q,q_0,F,\delta)$ est un DFA sur l'alphabet $\Sigma$, on
définit une fonction $\delta^* \colon Q\times\Sigma^* \to Q$ par
$\delta^*(q,x_1\cdots x_n) =
\delta(\cdots\delta(\delta(q,x_1),x_2)\cdots,x_n)$ ou, ce qui revient
au même (par récurrence sur la longueur du second argument) :
\begin{itemize}
\item $\delta^*(q,\varepsilon) = q$ quel que soit $q\in Q$ (où
  $\varepsilon$ désigne le mot vide),
\item $\delta^*(q,wx) = \delta(\delta^*(q,w),x)$ quels que soient
  $q\in Q$, $w\in\Sigma^*$ et $x\in\Sigma$,
\end{itemize}
(en particulier, $\delta^*(q,x) = \delta(q,x)$ si $x\in\Sigma$, donc
avec la convention faite en \ref{convention-on-words-of-length-one},
on peut dire que $\delta^*$ prolonge $\delta$).

Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$
\textbf{accepte} ou \textbf{reconnaît} un mot $w$ lorsque
$\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il
\textbf{rejette} le mot $w$.

\thingy\label{definition-recognizable-language} L'ensemble $L_A$ des
mots acceptés par l'automate $A$ s'appelle \textbf{langage accepté},
ou \textbf{reconnu}, ou \textbf{défini}, par l'automate $A$.

Un langage $L \subseteq \Sigma^*$ qui peut s'écrire sous la forme du
langage $L_A$ accepté par un DFA $A$ s'appelle \textbf{reconnaissable}
(sous-entendu : par automate déterministe fini).

On dit que deux DFA $A,A'$ sont \textbf{équivalents} lorsqu'ils
reconnaissent le même langage, i.e., $L_A = L_{A'}$.

\thingy\label{discussion-example2} L'automate fini ci-dessous sur
$\Sigma := \{a,b,c\}$ a trois états, $Q = \{0,1,2\}$.  On peut en
faire la description informelle suivante : l'automate commence dans
l'état $0$, où il reste jusqu'à rencontrer un $a$ qui le fait passer
dans l'état $1$, où il reste ensuite jusqu'à rencontrer un $b$ qui le
fait passer dans l'état $2$, où il reste définitivement et qui
constitue un état acceptant.

\begin{center}
%%% begin example2 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (98bp,18bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
  \node (q2) at (178bp,18bp) [draw,circle,state,final] {$2$};
  \draw [->] (q0) ..controls (46.106bp,18bp) and (58.578bp,18bp)  .. node[auto] {$a$} (q1);
  \draw [->] (q1) to[loop above] node[auto] {$a,c$} (q1);
  \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$b$} (q2);
  \draw [->] (q0) to[loop above] node[auto] {$b,c$} (q0);
  \draw [->] (q2) to[loop above] node[auto] {$a,b,c$} (q2);
%
\end{tikzpicture}

%%% end example2 %%%
\end{center}

Cette description rend claire le fait que l'automate en question
accepte exactement les mots contenant un $a$ suivi, pas forcément
immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un
sous-mot (cf. \ref{definition-subword}).  Ce langage est donc
reconnaissable.  (Il est aussi rationnel puisque dénoté par
l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.)

\thingy\label{definition-dfa-accessible-state} Un état $q$ d'un DFA
est dit \textbf{accessible} lorsqu'il existe un mot $w \in \Sigma^*$
tel que $q = \delta(q_0,w)$, autrement dit, graphiquement, lorsqu'il
existe un chemin orienté $q_0,q_1,\ldots,q_n=q$ reliant l'état
initial $q_0$ à l'état $q$ considéré : bref, cela correspond à un état
auquel il est possible que l'automate arrive (en partant de l'état
initial et en consommant un certain mot).  Dans le cas contraire,
l'état est dit \textbf{inaccessible}.  Il est évident qu'ajouter ou
supprimer (ou modifier) les états inaccessibles dans un DFA ne change
rien au langage reconnu au sens où on obtient des langages
équivalents.

Par exemple, dans le DFA qui suit, l'état $2$ est inaccessible
(l'automate est donc équivalent à celui représenté
en \ref{discussion-example1}).  On remarquera qu'il ne change rien que
cet état soit final ou non.

\begin{center}
%%% begin example1b %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (98bp,20.306bp) [draw,circle,state,final] {$1$};
  \node (q0) at (18bp,20.306bp) [draw,circle,state,initial] {$0$};
  \node (q2) at (172bp,20.306bp) [draw,circle,state,final] {$2$};
  \draw [->] (q1) ..controls (75.212bp,3.6347bp) and (64.284bp,-1.3057bp)  .. (54bp,1.3057bp) .. controls (50.042bp,2.3107bp) and (46.047bp,3.8633bp)  .. node[auto] {$b$} (q0);
  \draw [->] (q0) ..controls (46.106bp,20.306bp) and (58.578bp,20.306bp)  .. node[auto] {$b$} (q1);
  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
  \draw [->] (q0) to[loop above] node[auto] {$a$} (q0);
%
\end{tikzpicture}

%%% end example1b %%%
\end{center}

\thingy On va maintenant introduire différentes variations sur le
thème des automates finis, c'est-à-dire différentes généralisations de
la définition faite en \ref{definition-dfa} correspondant à des types
d'automates finis plus puissants que les DFA mais dont on va montrer,
à chaque fois, qu'ils peuvent se ramener à des DFA au sens où pour
chacun de ces automates généralisés on pourra construire
algorithmiquement un DFA qui reconnaît le même langage (si bien que la
classe des langages reconnaissables par n'importe laquelle de ces
sortes d'automates sera toujours la même).  Les plus simples sont les
automates déterministes finis incomplets et on va donc commencer par
eux.


\subsection{Automates finis déterministes à spécification incomplète (=DFAI)}

\thingy Un \textbf{automate fini déterministe à spécification
  incomplète} ou \textbf{...partielle}, ou simplement \textbf{automate
  fini déterministe incomplet}, en abrégé \textbf{DFAI}, sur un
alphabet $\Sigma$ est la donnée
\begin{itemize}
\item d'un ensemble fini $Q$ d'états,
\item d'un état initial $q_0 \in Q$,
\item d'un ensemble $F \subseteq Q$ d'états finaux,
\item d'une fonction de transition \emph{partielle}\footnote{Une
  « fonction partielle » $f\colon X\dasharrow Y$, où $X, Y$ sont deux
  ensembles est, par définition, la même chose qu'une fonction
  $f\colon D\to Y$ où $D\subseteq X$ est un sous-ensemble de $X$
  appelé \textbf{ensemble de définition} de $f$.} $\delta \colon
  Q\times\Sigma \dasharrow Q$,
\end{itemize}
autrement dit, la seule différence avec la définition faite
en \ref{definition-dfa} est que la fonction $\delta$ est partielle, ce
qui signifie qu'elle n'est pas obligatoirement définie sur tout couple
$(q,x) \in Q\times\Sigma$.

(Un DFA est considéré comme un DFAI particulier où la fonction de
transition $\delta$ se trouve être définie partout.)

\thingy Graphiquement, on représente un DFAI comme un DFA, à la
différence près que pour chaque $q\in Q$ et chaque $x\in \Sigma$, il y
a maintenant \emph{au plus une} (et non plus exactement une) arête
partant de $q$ et étiquetée par $x$.

\thingy Le fonctionnement d'un DFAI est le même que celui d'un DFA, à
la modification suivante près : si on donne à consommer à l'automate
un symbole pour lequel la transition n'est pas définie, i.e., s'il
rencontre un $x$ pendant qu'il se trouve dans un état $q$ pour lequel
$\delta(q,x)$ n'est pas défini, alors l'automate cesse de
fonctionner : l'automate n'a plus d'état, n'effectue plus de
transition, et n'acceptera pas le mot quelles que soient les lettres
ultérieures.

\thingy Formellement : si $A = (Q,q_0,F,\delta)$ est un DFAI sur
l'alphabet $\Sigma$, on définit une fonction $\delta^* \colon
Q\times\Sigma^* \dasharrow Q$ par $\delta^*(q,x_1\cdots x_n) =
\delta(\cdots\delta(\delta(q,x_1),x_2)\cdots,x_n)$ avec la convention
que dès qu'une sous-expression n'est pas définie, toute l'expression
n'est pas définie, ou, ce qui revient au même (par récurrence sur la
longueur du second argument) :
\begin{itemize}
\item $\delta^*(q,\varepsilon) = q$ quel que soit $q\in Q$ (où
  $\varepsilon$ désigne le mot vide),
\item $\delta^*(q,wx) = \delta(\delta^*(q,w),x)$ à condition que $q'
  := \delta^*(q,w)$ soit défini et que $\delta(q',x)$ le soit (et si
  ces deux conditions ne sont pas satisfaites, $\delta^*(q,wx)$ n'est
  pas défini).
\end{itemize}

Enfin, l'automate $A$ accepte un mot $w$ lorsque $\delta^*(q_0,w)$
\emph{est défini} et appartient à $F$ ; dans le cas contraire (que ce
soit parce que $\delta^*(q_0,w)$ n'est pas défini ou parce qu'étant
défini il n'appartient pas à $F$), l'automate rejette le mot.

Le langage accepté $L_A$ et l'équivalence de deux automates sont
définis de façon analogue aux DFA
(cf. \ref{definition-recognizable-language}).

\thingy\label{discussion-example2b} Voici un exemple de DFAI sur
l'alphabet $\Sigma = \{a,b,c\}$.  Cet automate reconnaît exactement
les mots formés d'un nombre quelconque de $c$, suivis d'un $a$, suivis
d'un nombre quelconque de $c$, suivis d'un $b$, suivis d'un nombre
quelconque de $c$.

\begin{center}
%%% begin example2b %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (98bp,18bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
  \node (q2) at (178bp,18bp) [draw,circle,state,final] {$2$};
  \draw [->] (q0) ..controls (46.106bp,18bp) and (58.578bp,18bp)  .. node[auto] {$a$} (q1);
  \draw [->] (q1) to[loop above] node[auto] {$c$} (q1);
  \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$b$} (q2);
  \draw [->] (q0) to[loop above] node[auto] {$c$} (q0);
  \draw [->] (q2) to[loop above] node[auto] {$c$} (q2);
%
\end{tikzpicture}

%%% end example2b %%%
\end{center}

(Ce langage est aussi dénoté par l'expression rationnelle
$c{*}ac{*}bc{*}$.)

\begin{prop}\label{completion-of-dfai}
Soit $A = (Q,q_0,F,\delta)$ un DFAI sur un alphabet $\Sigma$.  Alors
il existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même
alphabet $\Sigma$) qui soit équivalent à $A$ au sens où il reconnaît
le même langage $L_{A'} = L_A$.  De plus, $A'$ se déduit
algorithmiquement de $A$ en ajoutant au plus un état \textbf{puits}
à $A$ : on a $\#Q' \leq \#Q + 1$.
\end{prop}
\begin{proof}
On définit $Q' = Q \cup \{q_\bot\}$ où $q_\bot$ est un nouvel état
(n'appartenant pas à $Q$), qu'on appellera « puits ».  On garde l'état
initial $q'_0 = q_0$.  On garde l'ensemble $F' = F$ d'états finaux,
c'est-à-dire notamment que le puits n'est pas acceptant.  Enfin, on
définit $\delta'(q,x)$ pour $q\in Q'$ et $x\in\Sigma$ par
\[
\begin{aligned}
\delta'(q,x) &= \delta(q,x)\text{ si $\delta(q,x)$ est défini}\\
\delta'(q,x) &= q_\bot\text{ sinon}\\
\end{aligned}
\]
(notamment, $\delta'(q_\bot,x) = q_\bot$ quel que soit $x$).

Il est alors facile de voir que $A'$ a le même comportement que $A$ au
sens où $\delta^{\prime*}(q,w) = \delta^*(q,w)$ lorsque le terme de
droite est défini et $\delta^{\prime*}(q,w) = q_\bot$ sinon (le DFA
$A'$ « tombe dans le puits » lorsque le DFAI $A$ cesse de
fonctionner).  En particulier, ils reconnaissent les mêmes langages.
\end{proof}

\thingy On dit que le DFA $A'$ est obtenu en \textbf{complétant} le
DFAI $A$ lorsqu'il est obtenu par la procédure décrite dans la
démonstration de cette proposition, c'est-à-dire par l'addition d'un
état puits, sauf si $A$ est déjà complet, auquel cas on convient qu'il
est son propre complété (i.e., on n'ajoute un puits que quand c'est
réellement nécessaire).

\thingy À titre d'exemple, le DFA suivant représente la complétion du
DFAI représenté en \ref{discussion-example2b} :

\begin{center}
%%% begin example2c %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\begin{scope}
  \pgfsetstrokecolor{black}
  \definecolor{strokecol}{rgb}{1.0,1.0,1.0};
  \pgfsetstrokecolor{strokecol}
  \definecolor{fillcol}{rgb}{1.0,1.0,1.0};
  \pgfsetfillcolor{fillcol}
  \filldraw (0bp,0bp) -- (0bp,182bp) -- (214bp,182bp) -- (214bp,0bp) -- cycle;
\end{scope}
  \node (q1) at (102bp,131bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,85bp) [draw,circle,state,initial] {$0$};
  \node (q2) at (196bp,85bp) [draw,circle,state,final] {$2$};
  \node (qbot) at (102bp,22bp) [draw,circle,state] {$\bot$};
  \draw [->] (q1) to[loop above] node[auto] {$c$} (q1);
  \draw [->] (q2) to[loop above] node[auto] {$c$} (q2);
  \draw [->] (qbot) to[loop below] node[auto] {$a,b,c$} (qbot);
  \draw [->] (q0) ..controls (44.565bp,65.359bp) and (61.506bp,52.343bp)  .. node[auto] {$b$} (qbot);
  \draw [->] (q0) to[loop above] node[auto] {$c$} (q0);
  \draw [->] (q1) ..controls (102bp,96.993bp) and (102bp,73.356bp)  .. node[auto] {$a$} (qbot);
  \draw [->] (q0) ..controls (46.061bp,100.18bp) and (63.141bp,109.76bp)  .. node[auto] {$a$} (q1);
  \draw [->] (q2) ..controls (166.87bp,65.735bp) and (145.76bp,51.281bp)  .. node[auto] {$a,b$} (qbot);
  \draw [->] (q1) ..controls (132.83bp,116.08bp) and (154.08bp,105.46bp)  .. node[auto] {$b$} (q2);
%
\end{tikzpicture}

%%% end example2c %%%
\end{center}

\thingy On définit un état accessible d'un DFAI comme pour un DFA
(cf. \ref{definition-dfa-accessible-state}).

On dira en outre d'un état $q$ d'un DFAI qu'il est
\textbf{co-accessible} lorsqu'il existe un mot $w \in \Sigma^*$ tel
que $\delta(q,w)$ soit défini et soit final, autrement dit,
graphiquement, lorsqu'il existe un chemin orienté reliant l'état $q$
considéré à un état final (remarquer que les états finaux eux-mêmes
sont co-accessibles : prendre $w=\varepsilon$ dans ce qu'on vient de
dire).  Un état non co-accessible est donc un état à partir duquel il
est impossible de faire accepter le mot.  Cette définition pourrait
également être faite pour les DFA, mais pour les DFAI elle présente
l'intérêt qu'on peut supprimer les états non co-accessibles dans un
DFAI (ainsi, bien sûr, que toutes les transitions qui y conduisent).

Un DFAI dont tous les états sont à la fois accessibles et
co-accessibles (on les dit aussi \textbf{utiles}) est parfois appelé
\textbf{émondé}.  On peut émonder un DFAI en ne conservant que ses
états utiles : ainsi, tout DFAI est équivalent à un DFAI émondé.


\subsection{Automates finis non-déterministes (=NFA)}

\thingy Un \textbf{automate fini non-déterministe}, en abrégé
\textbf{NFA}, sur un alphabet $\Sigma$ est la donnée
\begin{itemize}
\item d'un ensemble fini $Q$ d'états,
\item d'un ensemble $I \subseteq Q$ d'états dits initiaux,
\item d'un ensemble $F \subseteq Q$ d'états dits finaux,
\item d'une \emph{relation} de transition $\delta \subseteq Q \times
  \Sigma \times Q$ (c'est-à-dire une partie du produit cartésien $Q
  \times \Sigma \times Q$, i.e., un ensemble de triplets $(q,x,q') \in
  Q \times \Sigma \times Q$).
\end{itemize}
Autrement dit, on autorise maintenant un ensemble quelconque d'états
initiaux, et de même, au lieu qu'un état $q$ et un symbole $x$
déterminent un unique état $q' = \delta(q,x)$, on a maintenant affaire
à un ensemble quelconque de triplets $(q,x,q')$.

\thingy Un DFAI (ou \textit{a fortiori} un DFA) est considéré comme un
NFA particulier en définissant l'ensemble des états initiaux du NFA
comme $I_{\mathrm{NFA}} = \{q_{0,\mathrm{DFAI}}\}$ et en définissant
la relation de transition du NFA comme le graphe de la fonction de
transition du DFAI (c'est-à-dire $(q,x,q') \in \delta_{\mathrm{NFA}}$
lorsque $\delta_{\mathrm{DFAI}}(q,x)$ est défini et vaut $q'$).

\thingy Graphiquement, on représente un NFA comme un DFA comme un
graphe orienté dont les nœuds sont les éléments de $Q$, et où on place
une arête étiquetée $x$ de $q$ vers $q'$ pour chaque triplet $(q,x,q')
\in \delta$ ; comme précédemment, on marque les états initiaux par une
flèche entrante (i.e., pointant de nulle part) et les états finaux par
une flèche sortante (i.e., pointant vers nulle part).

\thingy Il faut comprendre le fonctionnement d'un NFA de la manière
suivante : un mot $w = x_1\cdots x_n$ est accepté par l'automate
lorsqu'\emph{il existe} un chemin conduisant d'\emph{un} état initial
à un état final et dont les arêtes sont étiquetées par les lettres
$x_1,\ldots,x_n$ de $w$ (dans l'ordre) ; autrement dit, $w$ est
accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ tels que $q_0
\in I$ et $q_n\in F$ et $(q_{i-1},x_i,q_i) \in \delta$ pour
chaque $1\leq i\leq n$.

Il existe plusieurs manières de reformuler ce comportement : on peut
par exemple dire que l'automate est dans plusieurs états à la fois,
qu'il commence dans tous les états initiaux à la fois, et qu'à chaque
fois qu'il consomme un symbole $x$, il effectue toutes les transitions
possibles à partir d'un état où et étiquetées par ce symbole, et qu'au
bout du compte l'automate accepte le mot lorsqu'il est dans \emph{au
  moins un} état acceptant (même s'il est, par ailleurs, dans d'autres
états).  C'est cette façon de voir les choses qui conduira à
l'équivalence entre NFA et DFA (cf. \ref{determinization-of-nfa}).

Une autre façon de présenter les choses est que l'automate « devine »
par quel état initial commencer, et à chaque symbole consommé,
« devine » quelle transition effectuer, de manière à accepter le mot
si c'est possible.

En tout état de cause, la définition formelle va être donnée
ci-dessous.

\thingy Si $A = (Q,I,F,\delta)$ est un NFA sur l'alphabet $\Sigma$, on
définit une relation $\delta^* \subseteq Q \times \Sigma^* \times Q$
par $(q,w,q') \in \delta^*$ lorsque $w = x_1\cdots x_n$ et qu'il
existe $(q_0,\ldots,q_n)$ tels que $q_0 = q$ et $q_n = q'$ et
$(q_{i-1},x_i,q_i) \in \delta$ pour chaque $1\leq i\leq n$ ; ou, ce
qui revient au même (par récurrence sur la longueur de $w$) :
\begin{itemize}
\item $(q,\varepsilon,q') \in \delta^*$ si et seulement si $q'=q$,
\item $(q,wx,q') \in \delta^*$ si et seulement si il existe $q^\sharp$
  tel que $(q,w,q^\sharp) \in \delta^*$ et $(q^\sharp,x,q') \in
  \delta$.
\end{itemize}

Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$
et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.  Le
langage accepté $L_A$ et l'équivalence de deux automates sont définis
de façon analogue aux DFA
(cf. \ref{definition-recognizable-language}).

\thingy\label{discussion-example4} Pour illustrer le fonctionnement
des NFA, considérons l'automate à trois états sur $\Sigma=\{a,b\}$
représenté par la figure suivante : on a $Q = \{0,1,2\}$ avec
$I=\{0\}$ et $F=\{2\}$ et $\delta = \{(0,a,0),\penalty0
(0,b,0),\penalty-100 (0,a,1),\penalty-50 (1,a,2),\penalty0 (1,b,2)\}$.

\begin{center}
%%% begin example4 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (98bp,18bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
  \node (q2) at (188bp,18bp) [draw,circle,state,final] {$2$};
  \draw [->] (q0) ..controls (46.106bp,18bp) and (58.578bp,18bp)  .. node[auto] {$a$} (q1);
  \draw [->] (q1) ..controls (128.76bp,18bp) and (145.63bp,18bp)  .. node[auto] {$a,b$} (q2);
  \draw [->] (q0) to[loop above] node[auto] {$a,b$} (q0);
%
\end{tikzpicture}

%%% end example4 %%%
\end{center}

Cet automate n'est pas déterministe car il existe deux transitions
étiquetées $a$ partant de l'état $0$.  En considérant les différents
chemins possibles entre $0$ et $2$ dans ce graphe, on comprend que le
langage qu'il reconnaît est le langage des mots sur $\{a,b\}$ dont
l'avant-dernière lettre est un $a$ (c'est aussi le langage dénoté par
l'expression rationnelle $(a|b){*}a(a|b)$).  Une façon de présenter le
non-déterminisme est que l'automate « devine », quand il est dans
l'état $0$ et qu'on lui fait consommer un $a$, si ce $a$ sera
l'avant-dernière lettre, et, dans ce cas, passe dans l'état $1$ pour
pouvoir accepter le mot.

\begin{prop}\label{determinization-of-nfa}
Soit $A = (Q,I,F,\delta)$ un NFA sur un alphabet $\Sigma$.  Alors il
existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même
alphabet $\Sigma$) qui soit équivalent à $A$ au sens où il reconnaît
le même langage $L_{A'} = L_A$.  De plus, $A'$ se déduit
algorithmiquement de $A$ avec une augmentation au plus exponentielle
du nombre d'états : $\#Q' \leq 2^{\#Q}$.
\end{prop}
\begin{proof}
On définit $Q' = \mathscr{P}(Q) = \{\mathbf{q} \subseteq Q\}$
l'\emph{ensemble des parties} de $Q$ : c'est ce qui servira d'ensemble
d'états du DFA $A'$ qu'on construit (i.e., un état de $A'$ est un
ensemble d'états de $A$ — intuitivement, c'est l'ensemble des états
dans lesquels on se trouve simultanément).  On pose $q'_0 = I$ et $F'
= \{\mathbf{q}\subseteq Q :\penalty-100 \mathbf{q}\cap F
\neq\varnothing\}$ l'ensemble des états de $A'$ qui, vus comme des
ensembles d'états de $A$, contiennent \emph{au moins un} état final.
Enfin, pour $\mathbf{q}\subseteq Q$ et $x \in \Sigma$, on définit
$\delta'(\mathbf{q},x) = \{q_1\in Q : \exists q_0\in\mathbf{q}
((q_0,x,q_1) \in \delta)\}$ comme l'ensemble de tous les états $q_1$
de $A$ auxquels on peut accéder depuis un état $q_0$ dans $\mathbf{q}$
par une transition $(q_0,x,q_1)$ (étiquetée par $x$) de $A$.

Il est alors facile de voir (par récurrence sur $|w|$) que
$\delta^{\prime*}(\mathbf{q},w)$ est l'ensemble de tous les les états
$q_1 \in Q$ tels que $(q_0,w,q_1)\in\delta^*$, i.e., auxquels on peut
accéder depuis un état $q_0$ dans $\mathbf{q}$ par une suite de
transitions de $A$ étiquetées par les lettres de $w$.  En particulier,
$\delta^{\prime*}(I,w)$ est l'ensemble de tous les états de $A$
auxquels on peut accéder depuis un état initial de $A$ par une suite
de transitions de $A$ étiquetées par les lettres de $w$ : le mot $w$
appartient à $L_A$ si et seulement si cet ensemble contient un élément
de $F$, ce qui par définition de $F'$ signifie exactement
$\delta^{\prime*}(I,w) \in F'$.  On a bien prouvé $L_{A'} = L_A$.

Enfin, $\#Q' = \#\mathscr{P}(Q) = 2^{\#Q}$ (car une partie de $Q$ peut
se voir comme sa fonction indicatrice, qui est une fonction $Q \to
\{0,1\}$).
\end{proof}

\thingy On dit que le DFA $A'$ est obtenu en \textbf{déterminisant} le
NFA $A$ lorsqu'il est obtenu par la procédure décrite dans la
démonstration de cette proposition en ne gardant que les états
accessibles.

Algorithmiquement, la déterminisation de $A$ s'obtient par la
procéduire suivante :
\begin{itemize}
\item créer une file (ou une pile) d'ensembles d'états de $A$ ;
  initialiser cette file avec le seul élément $I$ (vu comme un
  sous-ensemble de $Q$) ; et créer l'automate $A'$ avec initialement
  l'unique état $I$, marqué comme état initial, et aussi comme final
  s'il contient un état final de $A$ ;
\item tant que la file/pile n'est pas vide : en extraire un élément
  $\mathbf{q}$, et, pour chaque lettre $x\in\Sigma$,
\begin{itemize}
\item calculer l'ensemble $\mathbf{q}' = \{q_1\in Q : \exists
  q_0\in\mathbf{q} ((q_0,x,q_1) \in \delta)\}$ (en listant tous les
  triplets $(q_0,x,q_1)$ dont le premier élément est dans $\mathbf{q}$
  et le second élément est $x$),
\item si $\mathbf{q}'$ n'existe pas déjà comme état de $A'$, l'y
  ajouter, et dans ce cas, l'ajouter à la file/pile, et de plus, si
  $\mathbf{q}'$ contient un état final de $A$, marquer cet état comme
  final pour $A'$,
\item et ajouter à $A'$ la transition $\delta'(\mathbf{q},x) =
  \mathbf{q}'$.
\end{itemize}
\end{itemize}

La file/pile sert à stocker les états de $A'$ qui ont été créés mais
pour lesquels les transitions sortantes n'ont pas encore été
calculées.  L'algorithme se termine quand la file/pile se vide, ce qui
se produit toujours en au plus $2^{\#Q}$ étapes car chaque $\mathbf{q}
\subseteq Q$ ne peut apparaître qu'une seule fois dans la file/pile.

Il se peut que l'état $\varnothing$ soit créé : cet état servira
effectivement de puits, au sens où on aura $\delta'(\varnothing,x) =
\varnothing$ quel que soit $x$ (et l'état n'est pas acceptant).

Il arrive souvent que l'automate déterminisé soit plus petit que les
$2^{\#Q}$ états qu'il a dans le pire cas.

\thingy À titre d'exemple, déterminisons le NFA $A$ présenté
en \ref{discussion-example4} : on commence par construire un état
$\{0\}$ pour $A'$ car le NFA a $\{0\}$ pour ensemble d'états
initiaux ; on a $\delta'(\{0\},a) = \{0,1\}$ car $0$ et $1$ sont les
deux états auxquels on peut arriver dans $A$ par une transition
partant de $0$ et étiquetée par $a$, tandis que $\delta'(\{0\},b) =
\{0\}$ ; ensuite, $\delta'(\{0,1\},a) = \{0,1,2\}$ car $0,1,2$ sont
les trois états auxquels on peut arriver dans $A$ par une transition
partant de $0$ ou $1$ et étiquetée par $a$ ; et ainsi de suite.  En
procédant ainsi, on constuit l'automate à $4$ états qui suit :

\begin{center}
\footnotesize
%%% begin example4det %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\begin{scope}
  \pgfsetstrokecolor{black}
  \definecolor{strokecol}{rgb}{1.0,1.0,1.0};
  \pgfsetstrokecolor{strokecol}
  \definecolor{fillcol}{rgb}{1.0,1.0,1.0};
  \pgfsetfillcolor{fillcol}
  \filldraw (0bp,0bp) -- (0bp,155bp) -- (212bp,155bp) -- (212bp,0bp) -- cycle;
\end{scope}
  \node (q02) at (188bp,19bp) [draw,circle,state,final] {$\{0,2\}$};
  \node (q0) at (18bp,40bp) [draw,circle,state,initial] {$\{0\}$};
  \node (q01) at (100bp,71bp) [draw,circle,state] {$\{0,1\}$};
  \node (q012) at (188bp,98bp) [draw,circle,state,final] {$\{0,1,2\}$};
  \draw [->] (q01) ..controls (129.79bp,53.593bp) and (147.53bp,42.867bp)  .. node[auto] {$b$} (q02);
  \draw [->] (q0) ..controls (45.781bp,50.378bp) and (59.874bp,55.839bp)  .. node[auto] {$a$} (q01);
  \draw [->] (q0) to[loop above] node[auto] {$b$} (q0);
  \draw [->] (q01) ..controls (129.27bp,79.877bp) and (142.8bp,84.122bp)  .. node[auto] {$a$} (q012);
  \draw [->] (q012) to[loop above] node[auto] {$a$} (q012);
  \draw [->] (q02) ..controls (146.97bp,21.169bp) and (110.83bp,23.684bp)  .. (80bp,28bp) .. controls (68.696bp,29.582bp) and (56.322bp,31.905bp)  .. node[auto] {$a,b$} (q0);
  \draw [->] (q012) ..controls (188bp,65.926bp) and (188bp,56.965bp)  .. node[auto] {$b$} (q02);
%
\end{tikzpicture}

%%% end example4det %%%
\end{center}

On remarquera qu'on a construit moins que les $2^3 = 8$ états qu'on
pouvait craindre.

Il est par ailleurs instructif de regarder comment fonctionne
l'automate $A'$ ci-dessus pour déterminer si l'avant-dernière lettre
d'un mot est un $a$ : intuitivement, l'état $\{0\}$ mémorise
l'information « la dernière lettre n'était pas un $a$, et la
  précédente ne l'était pas », l'état $\{0,1\}$ mémorise « la dernière
  lettre était un $a$, mais la précédente ne l'état pas », l'état
$\{0,1,2\}$ mémorise « les deux dernières lettres étaient des $a$ »,
et l'état $\{0,2\}$ mémorise « la dernière lettre était un $b$, mais
  la précédente était un $a$ ».


\subsection{Automates finis non-déterministes à transitions spontanées (=εNFA)}

\thingy Un \textbf{automate fini non-déterministe à transitions
  spontanées} ou \textbf{...à $\varepsilon$-transitions}, en abrégé
\textbf{εNFA}, sur un alphabet $\Sigma$ est la donnée
\begin{itemize}
\item d'un ensemble fini $Q$ d'états,
\item d'un ensemble $I \subseteq Q$ d'états dits initiaux,
\item d'un ensemble $F \subseteq Q$ d'états dits finaux,
\item d'une relation de transition $\delta \subseteq Q \times
  (\Sigma\cup\{\varepsilon\}) \times Q$.
\end{itemize}
Autrement dit, on autorise maintenant des transitions étiquetées par
le mot vide $\varepsilon$ plutôt que par une lettre $x \in\Sigma$ :
ces transitions sont dites spontanées, ou $\varepsilon$-transitions.

Soulignons qu'on ne définit les $\varepsilon$-transitions \emph{que}
pour les automates non-déterministes : ou, pour dire les choses
autrement, \emph{un automate qui possède des $\varepsilon$-transitions
  est par nature même non-déterministe}.

La représentation graphique des εNFA est évidente (on utilisera le
symbole « $\varepsilon$ » pour étiqueter les transitions spontanées).
Un NFA est considéré comme un εNFA particulier pour lequel il n'y a
pas de ε-transition.

\thingy Un εNFA accepte un mot $w$ lorsqu'il existe un chemin
conduisant d'un état initial à un état final et dont les arêtes sont
étiquetées par les lettres de $w$ ou bien des $\varepsilon$ insérés à
n'importe quel endroit et en n'importe quel nombre.  Autrement dit,
$w$ est accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ et
$t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$ tels que $q_0 \in I$
et $q_n\in F$ et $(q_{i-1},t_i,q_i) \in \delta$ pour chaque $1\leq
i\leq n$ et $w = t_1\cdots t_n$ (\emph{attention} : dans cette
écriture, $t_1,\ldots,t_n$ ne sont pas forcément les lettres de $w$,
certains des $t_i$ peuvent être le symbole $\varepsilon$, les lettres
de $w$ sont obtenues en ignorant ces symboles).

De façon plus intuitive, cela signifie que l'automate a la possibilité
de passer spontanément, c'est-à-dire sans consommer de lettre, d'un
état $q$ à un état $q'$, lorsque ces états sont reliés par une
ε-transition.

\thingy Voici une formalisation possible : si $A = (Q,I,F,\delta)$ est
un εNFA sur l'alphabet $\Sigma$, on définit une relation $\delta^*
\subseteq Q \times \Sigma^* \times Q$ par $(q,w,q') \in \delta^*$
lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $t_1,\ldots,t_n \in
(\Sigma\cup\{\varepsilon\})$ tels que $q_0 = q$ et $q_n = q'$ et
$(q_{i-1},t_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w
= t_1\cdots t_n$.

Si on préfère, on peut définir par récurrence sur $n \geq 0$ une
relation $\delta^{(n)} \subseteq Q \times \Sigma^* \times Q$ de la
manière suivante :
\begin{itemize}
\item $(q,w,q') \in \delta^{(0)}$ si et seulement si $q'=q$ et
  $v=\varepsilon$,
\item $\delta^{(1)} = \delta \subseteq Q \times
  (\Sigma\cup\{\varepsilon\})$ (faisant partie de la donnée de $A$),
\item $(q,v,q') \in \delta^{(n+1)}$ si et seulement si il existe
  $q^\sharp \in Q$ et $t \in \Sigma\cup\{\varepsilon\}$ tels que
  $(q,w,q^\sharp) \in \delta^{(n)}$ et $(q^\sharp,t,q') \in \delta$ et
  $v = wt$ (ce qui signifie que : soit $t=\varepsilon$ et $v=w$, soit
  $t\in\Sigma$ est la dernière lettre de $w$ et $v$ est le préfixe
  correspondant) ;
\end{itemize}
et on définit $\delta^* = \bigcup_{n=1}^{+\infty} \delta^{(n)}$,
autrement dit $(q,w,q') \in \delta^*$ lorsqu'il existe $n$ tel que
$(q,w,q') \in \delta^{(n)}$.

Concrètement, $(q,w,q') \in \delta^{(n)}$ signifie que le εNFA peut
passer de l'état $q$ à l'état $q'$ en effectuant (exactement) $n$
transitions ($q_0\to q_1 \to \cdots \to q_n$ étiquetées par
$t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$) et en consommant le
mot $w$ (soit $w = t_1\cdots t_n$) ; et $(q,w,q') \in \delta^*$
signifie la même chose mais sans contrainte sur le nombre de
transitions.  La différence avec les NFA est que le nombre $n$ de
transitions n'est plus forcément égal à la longueur de $w$.

Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$
et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.  Le
langage accepté $L_A$ et l'équivalence de deux automates sont définis
de façon analogue aux DFA
(cf. \ref{definition-recognizable-language}).

\thingy\label{discussion-example5} Voici un exemple de εNFA
particulièrement simple sur $\Sigma = \{a,b,c\}$:

\begin{center}
%%% begin example5 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (98bp,18bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
  \node (q2) at (178bp,18bp) [draw,circle,state,final] {$2$};
  \draw [->] (q0) ..controls (46.106bp,18bp) and (58.578bp,18bp)  .. node[auto] {$\varepsilon$} (q1);
  \draw [->] (q1) to[loop above] node[auto] {$b$} (q1);
  \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$\varepsilon$} (q2);
  \draw [->] (q0) to[loop above] node[auto] {$a$} (q0);
  \draw [->] (q2) to[loop above] node[auto] {$c$} (q2);
%
\end{tikzpicture}

%%% end example5 %%%
\end{center}

En considérant les différents chemins possibles entre $0$ et $2$ sur
ce graphe, on comprend que le langage qu'il reconnaît est celui des
mots sur $\{a,b,c\}$ formés d'un nombre quelconque de $a$ suivi d'un
nombre quelconque de $b$ suivi d'un nombre quelconque de $c$, ou, si
on préfère, le langage dénoté par l'expression rationnelle
$a{*}b{*}c{*}$.

\thingy Si $q$ est un état d'un εNFA, on appelle \textbf{ε-fermeture}
de $q$ l'ensemble des états $q'$ (y compris $q$ lui-même) accessibles
depuis $q$ par une succession quelconque de ε-transitions,
c'est-à-dire, si on veut, $\{q'\in Q :\penalty0 (q,\varepsilon,q')
\in\delta^*\}$.  On notera temporairement $C(q)$ cet ensemble.  (Par
exemple, dans l'exemple \ref{discussion-example5} ci-dessus, on a
$C(0) = \{0,1,2\}$ et $C(1) = \{1,2\}$ et $C(2) = \{2\}$.  Dans tout
NFA sans ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.)

Il est clair qu'on peut calculer algorithmiquement $C(q)$ (par exemple
par un algorithme de Dijkstra sur le graphe dont l'ensemble des
sommets est $Q$ et l'ensemble des arêtes est l'ensemble des
ε-transitions de $A$ : la ε-fermeture $C(q)$ est simplement l'ensemble
des sommets accessibles depuis $q$ dans ce graphe).

\begin{prop}\label{removal-of-epsilon-transitions}
Soit $A = (Q,I,F,\delta)$ un εNFA sur un alphabet $\Sigma$.  Alors il
existe un NFA $A' = (Q,I',F',\delta')$ (sur le même alphabet $\Sigma$)
ayant le même ensemble d'états $Q$ que $A$ et qui soit équivalent
à $A$ au sens où il reconnaît le même langage $L_{A'} = L_A$.  De
plus, $A'$ se déduit algorithmiquement de $A$.
\end{prop}
\begin{proof}
On pose $I' = I$ (mêmes états initiaux).  L'idée est maintenant de
faire une transition $(q,x,q') \in \delta'$ à chaque fois qu'on peut
atteindre $q'$ à partir de $q$ dans $A$ par une suite quelconque de
ε-transitions suivie d'une unique transition étiquetée par $x$,
autrement dit, $(q,\varepsilon,q^\sharp) \in \delta^*$ (c'est-à-dire
$q^\sharp \in C(q)$) et $(q^\sharp,x,q') \in \delta$.

On définit donc $\delta' \subseteq Q\times\Sigma\times Q'$ par
$(q,x,q') \in \delta'$ lorsqu'il existe $q^\sharp \in C(q)$ tel que
$(q^\sharp,x,q') \in \delta$ : autrement dit, pour créer les
transitions $q\to q'$ dans $A'$, on parcourt tous les $q^\sharp \in
C(q)$, et on crée une transition $q\to q'$ étiquetée par $x$ dans $A'$
lorsqu'il existe une transition $q^\sharp\to q'$ étiquetée par ce $x$
dans $A$.  De même, on définit $F' \subseteq Q$ comme l'ensemble des
$q\in Q$ tels que $C(q) \cap F \neq \varnothing$, c'est-à-dire, qu'on
peut atteindre un état final par une succession de ε-transitions.

Si on a un chemin $q_0 \to q_1 \to \cdots \to q_n$ dans $A$ menant
d'un état initial $q_0 \in I$ à un état final $q_n \in F$ et
étiquetées par $t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$
(c'est-à-dire $(q_{i-1},t_i,q_i) \in \delta$), appelons
$j_1<\ldots<j_m$ les indices tels que $t_j \in\Sigma$, autrement dit,
tels que la transition $q_{j-1} \to q_j$ ne soit pas spontanée, et
posons $j_0 = 0$.  Alors on passe de $q_{j_{i-1}}$ à $q_{j_i}$ par une
succession de ε-transitions (de $q_{j_{i-1}}$ à $q_{(j_i)-1}$) suivie
par une unique transition non spontanée : on a $q_{(j_i)-1} \in
C(q_{j_{i-1}})$ et $(q_{(j_i)-1},t_{j_i},q_{j_i}) \in \delta$,
autrement dit $(q_{j_{i-1}},t_{j_i},q_{j_i}) \in \delta'$ ; et comme
le mot $w = t_1\cdots t_n$ s'écrit aussi $t_{j_1}\cdots t_{j_m}$, on a
un chemin reliant $q_{j_0} = q_0 \in I$ à $q_{j_m} \in F'$ (puisque
$q_n \in C(q_{j_m}) \cap F$).  Le mot $w$ supposé accepté par $A$ est
donc accepté par $A'$.  La réciproque est analogue.
\end{proof}

\thingy On dit que le NFA $A'$ est obtenu en \textbf{supprimant les
  ε-transitions} dans le εNFA $A$ lorsqu'il est obtenu par la
procédure décrite dans la démonstration de cette proposition, et en
supprimant tous les états non-initiaux de $A'$ auxquels n'aboutissent
dans $A$ que des ε-transitions (ces états sont devenus inaccessibles
dans $A'$).  Algorithmiquement, il s'agit donc, pour chaque état $q\in
Q$ et chaque $q^\sharp$ dans la ε-femerture $C(q)$ de $q$, de créer
une transition $q\to q'$ étiquetée par $x$ dans $A'$ pour chaque
transition $q^\sharp\to q'$ étiquetée par $x$ dans $A$.

\thingy À titre d'exemple, supprimons les ε-transitions du εNFA $A$
présenté en \ref{discussion-example5} : comme $C(0) = \{0,1,2\}$, on
fait partir de $0$ toutes les transitions partant d'un des états
$0,1,2$ et étiquetées par une lettre, et de même, comme $C(1) =
\{1,2\}$, on fait pratir de $1$ toutes les transitions partant d'un
des états $1,2$ et étiquetées par une lettre.  On obtient finalement
l'automate suivant :

\begin{center}
%%% begin example5ne %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (97bp,48bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
  \node (q2) at (176bp,18bp) [draw,circle,state,final] {$2$};
  \draw [->] (q0) ..controls (47.643bp,10.917bp) and (64.2bp,7.4655bp)  .. (79bp,6bp) .. controls (94.922bp,4.4234bp) and (99.078bp,4.4234bp)  .. (115bp,6bp) .. controls (125.98bp,7.0877bp) and (137.94bp,9.2693bp)  .. node[auto] {$c$} (q2);
  \draw [->] (q2) to[loop above] node[auto] {$c$} (q2);
  \draw [->] (q0) to[loop above] node[auto] {$a$} (q0);
  \draw [->] (q1) to[loop above] node[auto] {$b$} (q1);
  \draw [->] (q1) ..controls (124.28bp,37.762bp) and (137.94bp,32.438bp)  .. node[auto] {$c$} (q2);
  \draw [->] (q0) ..controls (45.279bp,28.238bp) and (58.943bp,33.562bp)  .. node[auto] {$b$} (q1);
%
\end{tikzpicture}

%%% end example5ne %%%
\end{center}

(Sur cet exemple précis, on obtient un automate déterministe
incomplet, mais ce n'est pas un phénomène général : en général il faut
s'attendre à obtenir un NFA.)


\section{Langages reconnaissables et langages rationnels}

\subsection{Stabilité des langages reconnaissables}

\thingy On rappelle qu'on a défini un langage reconnaissable comme un
langage $L$ pour lequel il existe un DFA $A$ tel que $L = L_A$.
D'après \ref{completion-of-dfai}, \ref{determinization-of-nfa} et
\ref{removal-of-epsilon-transitions}, on peut remplacer « DFA » dans
cette définition par « DFAI », « NFA » ou « εNFA » sans changer la
définition.

Nous allons maintenant montrer que les langages reconnaissables sont
stables par différentes opérations : complémentaire, union,
intersection, concaténation et étoile de Kleene.

\begin{prop}\label{dfa-complement}
Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors
le complémentaire $\Sigma^*\setminus L$ de $L$ est reconnaissable ; de
plus, un DFA reconnaissant l'un se déduit algorithmiquement d'un DFA
reconnaissant l'autre.
\end{prop}
\begin{proof}
Par hypothèse, il existe un DFA $A = (Q,q_0,F,\delta)$ tel que $L =
L_A$.  Considérons le DFA $A'$ défini par l'ensemble d'états $Q' = Q$,
l'état initial $q'_0 = q_0$, la fonction de transition $\delta' =
\delta$ et pour seul changement l'ensemble d'états finaux $F' = Q
\setminus F$ complémentaire de $F$.

Si $w \in \Sigma^*$, on a $w \in L_{A'}$ si et seulement si
$\delta^{\prime*}(q_0,w) \in F'$, c'est-à-dire $\delta^*(q_0,w) \in
F'$ (puisque $\delta' = \delta$), c'est-à-dire $\delta^*(q_0,w)
\not\in F$ (par définition du complémentaire), c'est-à-dire $w \not\in
L_A$.  Ceci montre bien que $L_{A'}$ est le complémentaire de $L_A$.
\end{proof}

\thingy Cette démonstration a utilisé la caractérisation des langages
reconnaissables par les DFA : il était crucial de le faire, et les
autres sortes d'automates définis plus haut n'auraient pas permis
d'arriver (simplement) à la même conclusion.  Pourquoi ?

\begin{prop}\label{dfa-union-and-intersection}
Si $L_1,L_2$ sont des langages reconnaissables (sur un même
alphabet $\Sigma$), alors la réunion $L_1\cup L_2$ et l'intersection
$L_1\cap L_2$ sont reconnaissables ; de plus, un DFA reconnaissant
l'un comme l'autre se déduit algorithmiquement de DFA reconnaissant
$L_1$ et $L_2$.
\end{prop}
\begin{proof}
Par hypothèse, il existe des DFA $A_1 = (Q_1,q_{0,1},F_1,\delta_1)$ et
$A_2 = (Q_2,q_{0,2},F_2,\delta_2)$ tels que $L_1 = L_{A_1}$ et $L_2 =
L_{A_2}$.  Considérons le DFA $A'$ défini par l'ensemble d'états $Q' =
Q_1 \times Q_2$, l'état initial $q'_0 = (q_{0,1},q_{0,2})$, la
fonction de transition $\delta' \colon ((p_1,p_2),x) \mapsto
(\delta_1(p_1,x), \delta_2(p_2,x))$ et pour ensemble d'états finaux
$F' = (F_1\times Q_2) \cup (Q_1 \times F_2)$ (si on cherche à
reconnaître $L_1\cup L_2$) respectivement $F' = F_1\times F_2$ (si on
cherche à reconnaître $L_1\cap L_2$).  Remarquons que $(p_1,p_2) \in
Q'$ appartient à $F' = (F_1\times Q_2) \cup (Q_1 \times F_2)$
respectivement $F' = F_1\times F_2$ si et seulement si $p_1 \in F_1$
ou $p_2 \in F_2$ respectivement $p_1 \in F_1$ et $p_2 \in F_2$.  Par
ailleurs, si $w\in \Sigma^*$, on a $\delta'(q_0',w) =
(\delta_1(q_{0,1},w), \delta_2(q_{0,2},w))$.  On voit donc qu'un mot
$w$ appartient à $L_{A'}$ si et seulement il appartient à $L_1 \cup
L_2$ respectivement $L_1 \cap L_2$, ce qu'il fallait démontrer.
\end{proof}

\thingy On pouvait aussi traiter uniquement l'une des deux opérations
booléennes et déduire l'autre par complémentaire, mais le gain de
place est faible (et la construction est exactement la même).

La construction ci-dessus est un \emph{produit} de DFA (que ce soit
pour prendre la réunion ou l'intersection).  La construction produit
fonctionnerait encore avec les NFA \emph{pour la réunion de langages
  mais pas pour l'intersection} : il est intéressant de réfléchir à
pourquoi (essentiellement, ce qui casse la symétrie est que dans un
NFA, un mot est accepté dès qu'\emph{il existe} un chemin qui
l'accepte, or le quantificateur $\exists$ distribue sur les
disjonctions mais pas sur les conjonctions).

\begin{prop}\label{nfa-mirror}
Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors
le langage miroir (cf. \ref{definition-mirror-language})
$L^{\mathsf{R}}$ de $L$ est reconnaissable ; de plus, un NFA ou εNFA
reconnaissant l'un se déduit algorithmiquement d'un NFA ou εNFA
reconnaissant l'autre.
\end{prop}
\begin{proof}
Par hypothèse, il existe un εNFA ou un NFA $A = (Q,I,F,\delta)$ tel
que $L = L_A$.  Considérons l'automate $A'$ de même type défini par
l'ensemble d'états $Q' = Q$ et inversant toutes les flèches de $A$,
c'est-à-dire $I' = F$ et $F' = I$ et $(q,t,q') \in \delta'$ si et
seulement si $(q',t,q) \in \delta$.  Un chemin existe dans $A'$ si et
seulement si le même chemin inversé existe dans $A$, ce qui montre
qu'un mot appartient à $L_{A'}$ si et seulement si son miroir
appartient à $L_A$.
\end{proof}

\thingy Alors que les constructions du complémentaire et de
l'intersection s'effectuaient naturellement sur les DFA, celle du
langage miroir s'effectue naturellement sur les NFA.  (On peut, bien
sûr, considérer un DFA comme un NFA particulier, et effectuer dessus
l'opération d'inversion des flèches qu'on vient de décrire, mais en
général on n'obtiendra pas un DFA, seulement un NFA ; les NFA dont
l'inversion des flèches est déterministe — c'est-à-dire tels que, pour
chaque état $q$ et chaque lettre $x$, il existe une unique arête
aboutissant à $q$ et étiquetée par $x$ — sont parfois dits
« co-déterministes ».)

\thingy On a vu en \ref{dfa-union-and-intersection} une preuve, à base
de NFA, que $L_1 \cup L_2$ est reconnaissable lorsque $L_1$ et $L_2$
le sont.  Donnons maintenant une autre preuve de ce fait, à base de
εNFA :

\begin{prop}\label{nfa-union}
Si $L_1,L_2$ sont des langages reconnaissables (sur un même
alphabet $\Sigma$), alors la réunion $L_1 \cup L_2$ est
reconnaissable ; de plus, un εNFA (resp. NFA) la reconnaissant se
déduit algorithmiquement de εNFA (resp. NFA) reconnaissant $L_1$
et $L_2$ (c'est simplement, en un sens évident, la réunion disjointe
des automates donnés).
\end{prop}
\begin{proof}
Par hypothèse, il existe des εNFA (resp. NFA) $A_1 =
(Q_1,I_1,F_1,\delta_1)$ et $A_2 = (Q_2,I_2,F_2,\delta_2)$ tels que
$L_1 = L_{A_1}$ et $L_2 = L_{A_2}$.  Considérons l'automate $A'$ dont
l'ensemble d'états est $Q' = Q_1 \uplus Q_2$ où $\uplus$ désigne la
réunion disjointe\footnote{C'est-à-dire que, quitte à renommer les
  états, on remplace $Q_2$ par un ensemble en bijection avec lui de
  façon à être disjoint de $Q_1$.}, l'ensemble d'états initiaux est la
réunion $I' = I_1 \cup I_2$, les états finaux $F' = F_1 \cup F_2$, et
la relation de transition $\delta'$ est $\delta_1 \cup \delta_2$
(l'ensemble des transitions existant déjà dans $A_1$ ou $A_2$).
Symboliquement :

\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (A1) at (0bp,25bp) [draw,dotted,circle,initial,final] {$A_1$};
\node (A2) at (0bp,-25bp) [draw,dotted,circle,initial,final] {$A_2$};
\end{tikzpicture}
\end{center}

%% \begin{center}
%% \begin{tikzpicture}[>=latex,line join=bevel,automaton]
%% \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$};
%% \node (A1) at (50bp,30bp) [draw,dotted,circle] {$A_1$};
%% \node (A2) at (50bp,-30bp) [draw,dotted,circle] {$A_2$};
%%   \draw [->] (q0) to node[auto] {$\varepsilon$} (A1);
%%   \draw [->] (q0) to node[auto] {$\varepsilon$} (A2);
%% \end{tikzpicture}
%% \end{center}

Il est alors clair qu'un chemin de l'état initial à un état final dans
cet automate $A'$ consiste soit en un chemin d'un état initial à un
état final dans $A_1$ soit en un tel chemin dans $A_2$.  On a donc
bien $L_{A'} = L_1 \cup L_2$.
\end{proof}

\begin{prop}\label{nfa-concatenation}
Si $L_1,L_2$ sont des langages reconnaissables (sur un même
alphabet $\Sigma$), alors la concaténation $L_1 L_2$ est
reconnaissable ; de plus, un εNFA la reconnaissant se déduit
algorithmiquement de εNFA reconnaissant $L_1$ et $L_2$.
\end{prop}
\begin{proof}
Par hypothèse, il existe des εNFA $A_1 = (Q_1,I_1,F_1,\delta_1)$ et
$A_2 = (Q_2,I_2,F_2,\delta_2)$ tels que $L_1 = L_{A_1}$ et $L_2 =
L_{A_2}$.  Considérons le εNFA $A'$ dont l'ensemble d'états est $Q' =
Q_1 \uplus Q_2$ où $\uplus$ désigne la réunion disjointe, dont les
états initiaux sont $I_1$, les états finaux sont $F_2$, et la relation
de transition $\delta'$ est $\delta_1 \cup \delta_2$ (l'ensemble des
transitions existant déjà dans $A_1$ ou $A_2$) à quoi on ajoute encore
une ε-transition $(q,\varepsilon,q')$ pour chaque $q\in F_1$ et
chaque $q'\in I_2$.  Symboliquement :

\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (A1) at (0bp,0bp) [draw,dotted,circle,initial] {$A_1$};
\node (A2) at (70bp,0bp) [draw,dotted,circle,final] {$A_2$};
  \draw [->] (A1) to node[auto] {$\varepsilon$} (A2);
\end{tikzpicture}
\end{center}

Il est alors clair qu'un chemin d'un état initial à un état final dans
cet automate $A'$ consiste en un chemin d'un état initial à un état
final dans $A_1$ suivi d'une ε-transition et d'un chemin d'un état
initial à un état final dans $A_2$.  On a donc bien $L_{A'} = L_1
L_2$.
\end{proof}

\begin{prop}\label{nfa-star}
Si $L$ est un langage reconnaissable (sur un alphabet $\Sigma$), alors
l'étoile de Kleene $L^*$ est reconnaissable ; de plus, un εNFA la
reconnaissant se déduit algorithmiquement de εNFA reconnaissant $L$.
\end{prop}
\begin{proof}
Par hypothèse, il existe un εNFA $A = (Q,I,F,\delta)$ tel que $L =
L_A$.  Considérons le εNFA $A'$ dont l'ensemble d'états est $Q' =
\{q_0\} \uplus Q$ (où $q_0$ est un nouvel état) dont les états
initiaux sont $I' = \{q_0\}$, les états finaux sont $F' = \{q_0\}$, et
la relation de transition $\delta'$ est $\delta$ (l'ensemble des
transitions existant déjà dans $A$) à quoi on ajoute encore une
ε-transition $(q_0,\varepsilon,q)$ pour chaque $q\in I$ et une autre
$(q,\varepsilon,q_0)$ pour chaque $q\in F$.  Symboliquement :

\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$q_0$};
\node (A) at (70bp,0bp) [draw,dotted,circle] {$A$};
  \draw [->,out=45,in=135] (q0) to node[auto] {$\varepsilon$} (A);
  \draw [->,out=225,in=315] (A) to node[auto] {$\varepsilon$} (q0);
\end{tikzpicture}
\end{center}

Il est alors clair qu'un chemin de l'état initial $q_0$ à l'état final
$q_0$ dans cet automate $A'$ consiste en un nombre quelconque
(éventuellement nul) de chemins d'un état initial à un état final
dans $A$ chacun précédé d'une ε-transition de $q_0$ vers l'état
initial de $A$ en question et suivi d'une ε-transition de l'état final
de $A$ en question vers $q_0$.  On a donc bien $L_{A'} = L^*$.
\end{proof}

\begin{prop}\label{rational-languages-are-recognizable}
Tout langage rationnel est reconnaissable ; de plus, un εNFA le
reconnaissant se déduit algorithmiquement d'une expression rationnelle
le dénotant.
\end{prop}
\begin{proof}
Cela résulte de façon évidente de la définition des langages
rationnels (cf. §\ref{subsection-rational-languages}), du fait que les
langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour
chaque $x\in\Sigma$) sont reconnaissables par automates finis, et des
propositions \ref{nfa-union}, \ref{nfa-concatenation}
et \ref{nfa-star}.
\end{proof}

\textcolor{red}{TODO: Standardiser la construction des automates.  Par
  exemple, utiliser le NFA « standard » ou « de Glushkov » (ayant un
  seul état initial, éventuellement final, sans aucune transition qui
  y mène).}


\subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)}

\thingy Un \textbf{automate fini (non-déterministe) à transitions
  étiquetées par des expressions rationnelles}, en abrégé
\textbf{RNFA}, sur un alphabet $\Sigma$ est la donnée
\begin{itemize}
\item d'un ensemble fini $Q$ d'états,
\item d'un ensemble $I \subseteq Q$ d'états dits initiaux,
\item d'un ensemble $F \subseteq Q$ d'états dits finaux,
\item d'un ensemble \emph{fini} de transitions $\delta \subseteq Q
  \times (\mathrm{regexp}(\Sigma)) \times Q$ où
  $(\mathrm{regexp}(\Sigma))$ désigne l'ensemble des expressions
  rationnelles sur $\Sigma$.
\end{itemize}
Autrement dit, on autorise maintenant des transitions étiquetées par
des expressions rationnelles quelconques sur $\Sigma$.  Remarquons
qu'on doit maintenant demander explicitement que l'ensemble $\delta$
des transitions permises soit fini car l'ensemble $Q \times
(\mathrm{regexp}(\Sigma)) \times Q$, lui, ne l'est pas.

\thingy Pour un tel automate, on définit une relation $\delta^*
\subseteq Q \times \Sigma^* \times Q$ par $(q,w,q') \in \delta^*$
lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $r_1,\ldots,r_n \in
\mathrm{regexp}(\Sigma)$ tels que $q_0 = q$ et $q_n = q'$ et
$(q_{i-1},r_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w
\in L_{r_1\cdots r_n}$.

Concrètement, $(q,w,q') \in \delta^{(n)}$ signifie que le RNFA peut
passer de l'état $q$ à l'état $q'$ en effectuant des transitions
($q_0\to q_1 \to \cdots \to q_n$ étiquetées par $r_1,\ldots,r_n \in
\mathrm{regexp}(\Sigma)$) et en consommant le mot $w$ au sens où ce
dernier se décompose comme concaténation d'autant de facteurs que de
transitions ($w = v_1\cdots v_n$), chacun vérifiant l'expression
rationnelle qui étiquette la transition (soit $v_i \in L_{r_i}$).

Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$
et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$.  Le
langage accepté $L_A$ et l'équivalence de deux automates sont définis
de façon analogue aux DFA
(cf. \ref{definition-recognizable-language}).

\thingy Un εNFA (ou \textit{a fortiori} un NFA, DFAI ou DFA) est
considéré comme un RNFA particulier dont les transitions sont
étiquetées soit par une unique lettre (considérée comme expression
rationnelle) soit par le symbole $\underline{\varepsilon}$ (dénotant
le langage $\{\varepsilon\}$) dans le cas des transitions spontanées.

Une expression rationnelle $r$ peut aussi être considérée comme un
RNFA particulier comportant un unique état initial, un unique état
final, et une unique transition de l'un vers l'autre, étiquetée par
l'expression $r$ elle-même.  Il est évident que ce RNFA reconnaît
exactement le langage dénoté par $r$.

La représentation graphique des RNFA ne pose pas de problème
particulier.

\thingy\label{give-rnfa-single-transitions} On peut toujours modifier
un RNFA de manière à ce qu'il y ait au plus une, ou même si on le
souhaite, exactement une, transition entre deux états $q$ et $q'$
donnés.  En effet, s'il existe plusieurs transitions
$(q,r_1,q'),\ldots, \penalty0 (q,r_k,q') \in \delta$ possibles entre
$q$ et $q'$, on peut les remplacer par une unique transition
$(q,(r_1|\cdots|r_k),q')$, cela ne change visiblement rien au
fonctionnement de l'automate (et notamment pas le langage reconnu).
S'il n'y a \emph{aucune} transition de $q$ vers $q'$, on peut toujours
choisir d'en ajouter une $(q,\bot,q')$ (qui ne peut pas être
empruntée !) si c'est commode.

Comme les εNFA, les NFA et les DFAI avant eux, les RNFA peuvent se
ramener aux automates précédemment définis :

\begin{prop}
Soit $A = (Q,I,F,\delta)$ un RNFA sur un alphabet $\Sigma$.  Alors il
existe un εNFA $A' = (Q',I',F',\delta')$ (sur le même
alphabet $\Sigma$) et qui soit équivalent à $A$ au sens où il
reconnaît le même langage $L_{A'} = L_A$.  De plus, $A'$ se déduit
algorithmiquement de $A$.
\end{prop}
\begin{proof}
On a vu que pour chaque expression rationnelle $r$ on peut trouver
(algorithmiquement) un εNFA $A_r$ qui reconnaît le langage dénoté
par $r$.  On peut donc construire $A'$ en remplaçant chaque transition
$(q,r,q')$ de $A$ par une copie de l'automate $A_r$ placée entre les
états $q$ et $q'$.  Symboliquement :

\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)]
\node (q1) at (0bp,0bp) [draw,circle,state] {$q$};
\node (q2) at (70bp,0bp) [draw,circle,state] {$q'$};
  \draw [->] (q1) to node[auto] {$r$} (q2);
\end{tikzpicture}
\quad devient\quad
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)]
\node (q1) at (0bp,0bp) [draw,circle,state] {$q$};
\node (q2) at (100bp,0bp) [draw,circle,state] {$q'$};
\node (A) at (50bp,0bp) [draw,dotted,circle] {$A_r$};
  \draw [->] (q1) to node[auto] {$\varepsilon$} (A);
  \draw [->] (A) to node[auto] {$\varepsilon$} (q2);
\end{tikzpicture}
\end{center}

Plus précisément, si $\{(q_j,r_j,q'_j) : 1\leq j\leq M\}$ est une
énumération de $\delta$, on construit $A'$ en lui donnant pour
ensemble d'états $Q \uplus \biguplus_{j=1}^M Q_{r_j}$ où $Q_{r_j}$ est
l'ensemble d'états de l'automate $A_{r_j}$ construit pour
reconnaître $r_j$, les ensembles d'états initiaux et finaux sont
$I'=I$ et $F'=F$ comme dans $A$, et la relation de transition
$\delta'$ est la réunion de chacune $\delta_{r_j}$ de celle des
εNFA $A_{r_j}$ à quoi on ajoute encore des transitions spontanées
$(q_j,\varepsilon,q^\sharp)$ pour tout état initial $q^\sharp \in
I_{r_j}$ de $A_{r_j}$ et des transitions spontanées
$(q^\flat,\varepsilon,q'_j)$ pour tout état final $q^\flat \in
F_{r_j}$ de $A_{r_j}$.  Il est clair que faire un chemin dans $A'$
revient à un faire un chemin dans $A$ où, à chaque fois qu'on fait la
transition $q_j\to q'_j$ étiquetée par $r_j$, on la remplace par un
chemin $q_j \to q^\sharp \to \cdots \to q^\flat \to q'_j$ formé d'une
transition spontanée vers un état initial de $A_{r_j}$ suivi d'un
chemin dans ce dernier, suivi d'une transition spontanée depuis un
état final de $A_{r_j}$.
\end{proof}

Mais la surprise des RNFA est qu'ils peuvent aussi se ramener à des
expressions rationnelles !

\begin{prop}
Soit $A = (Q,I,F,\delta)$ un RNFA sur un alphabet $\Sigma$.  Alors il
existe une expression rationnelle $r$ sur $\Sigma$ qui dénote le
langage reconnu par $A$, soit $L_r = L_A$.  De plus, $r$ se déduit
algorithmiquement de $A$.
\end{prop}
\begin{proof}
On a vu qu'on pouvait considérer une expression rationnelle comme un
RNFA ayant un unique état initial, un unique état final, et une unique
transition de l'un vers l'autre (étiquetée par l'expression
rationnelle en question).  On va construire montrer que $A$ est
équivalent à un RNFA de cette nature, ce qui montrera bien qu'il est
équivalent à une expression rationnelle.

Remarquons tout d'abord qu'on peut supposer que $A$ a un unique état
initial $q_0$ sans aucune transition qui y aboutit (si ce n'est pas le
cas, il suffit de créer un nouvel état $q_0$, d'en faire le seul état
initial, et de le munir de transitions spontanées — c'est-à-dire
étiquetées par $\underline{\varepsilon}$ — vers tous les états
précédemment initiaux).  De même (symétriquement), on peut supposer
que $A$ a un unique état final $q_\infty$ sans aucune transition qui
en part.  On fera l'hypothèse que $A$ a ces propriétés, et on
s'arrangera pour les préserver dans ce qui suit.

Soient maintenant $q$ un état de $A$ qui n'est ni l'état initial ni
l'état final.  On va montrer qu'on peut \emph{éliminer} $q$,
c'est-à-dire, quitte à ajouter des transitions, remplacer $A$ par un
automate équivalent $A'$ qui n'a pas cet état.  Pour cela, soient
$q_1,q_2$ deux états quelconques de $A$, autres que $q$ mais
possiblement égaux entre eux, où $q_1$ peut être l'état initial (mais
pas l'état final) et $q_2$ peut être l'état final (mais pas l'état
initial).  On a vu en \ref{give-rnfa-single-transitions} qu'on pouvait
supposer qu'il existait une unique transition $(q_1,r_{12},q_2)$ et de
même $(q_1,r_1,q)$ et $(q,r_2,q_2)$ et $(q,s,q)$ (transition de $q$
vers lui-même).  En même temps qu'on supprime $q$, on met dans $A'$ la
transition $(r_{12}|r_1(s){*}r_2)$ entre $q_1$ et $q_2$.
Symboliquement :

\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)]
\node (q1) at (0bp,0bp) [draw,circle,state] {$q_1$};
\node (q2) at (70bp,0bp) [draw,circle,state] {$q_2$};
\node (q) at (35bp,50bp) [draw,circle,state] {$q$};
  \draw [->] (q1) to node[auto] {$r_{12}$} (q2);
  \draw [->] (q1) to node[auto] {$r_1$} (q);
  \draw [->] (q) to node[auto] {$r_2$} (q2);
  \draw [->] (q) to[loop above] node[auto] {$s$} (q);
\end{tikzpicture}
\quad devient\quad
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)]
\node (q1) at (0bp,0bp) [draw,circle,state] {$q_1$};
\node (q2) at (100bp,0bp) [draw,circle,state] {$q_2$};
  \draw [->] (q1) to node[auto] {$\scriptstyle (r_{12}|r_1(s){*}r_2)$} (q2);
\end{tikzpicture}
\end{center}

Cette transformation doit être effectuée \emph{simultanément pour
  toute paire} $(q_1,q_2)$ d'états de $A$ pour laquelle
$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$ : pour chaque
telle paire, on remplace l'étiquette de la transition $r_{12}$ entre
eux par $(r_{12}|r_1(s){*}r_2)$.  Ceci ne change pas le fonctionnement
de l'automate, car tout chemin dans $A$ peut être remplacé par un
chemin dans $A'$ en supprimant simplement les $q$ (si on considère
$q_1$ et $q_2$ les états avant un bloc de de $q$ dans le chemin, on
voit que le chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se
transformer en $q_1 \to q_2$ en consommant un mot qui vérifie
l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$).

En supprimant (dans n'importe quel ordre) tous les états autres que
$q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant une unique
transition $(q_0,r,q_\infty)$, qui est donc essentiellement
l'expression rationnelle $r$ (si $q_\infty$ et $q_0$ ne sont pas
distincts, on peut ajouter un nouvel état initial, un nouvel état
final, et éliminer l'état commun :
cf. l'exemple \ref{example-of-state-elimination}).
\end{proof}

\thingy La procédure qu'on a décrite dans la démonstration de cette
proposition s'appelle l'algorithme d'\textbf{élimination des états}.
Il va de soi qu'on peut la simplifier un petit peu : s'il n'y a pas de
transition de de $q_1$ vers $q$ ou qu'il n'y en a pas de $q$
vers $q_2$ (c'est-à-dire que soit $r_1$ soit $r_2$ doit être considéré
comme valant $\bot$), on ne touche simplement pas à $r_{12}$ (et si la
transition de $q_1$ vers $q_2$ n'existait pas non plus, il n'y a pas
besoin de la créer) ; de même, s'il n'y a pas de transition de $q$
vers lui-même, on ignore la partie $s{*}$.  En revanche, il faut bien
penser à créer une transition de $q_1$ vers $q_2$, même si elle
n'existait pas au départ, lorsqu'on peut arriver de l'un vers l'autre
en passant par $q$.  Et il faut se souvenir que le cas $q_2=q_1$ est à
traiter aussi.

En général, l'élimination des états conduit à un expression
extrêmement compliquée.

\thingy\label{example-of-state-elimination} À titre d'exemple,
considérons le DFA suivant sur l'alphabet $\{0,1\}$, qui reconnaît les
suites binaires qui représentent un nombre multiple de $3$ écrit en
binaire (en convenant que le mot vide est une représentation binaire
du nombre $0$, ce qui est logique) :

\begin{center}
%%% begin example6 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$0$};
  \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$};
  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$1$} (q0);
  \draw [->] (q2) to[loop above] node[auto] {$1$} (q2);
  \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp)  .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp)  .. node[auto] {$0$} (q1);
  \draw [->] (q0) to[loop above] node[auto] {$0$} (q0);
  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$1$} (q1);
  \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$0$} (q2);
%
\end{tikzpicture}

%%% end example6 %%%
\end{center}

L'élimination de l'état $2$ conduit à l'automate suivant :

\begin{center}
%%% begin example6b %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$0$};
  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$1$} (q0);
  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$1$} (q1);
  \draw [->] (q1) to[loop right] node[auto] {$01{*}0$} (q1);
  \draw [->] (q0) to[loop above] node[auto] {$0$} (q0);
%
\end{tikzpicture}

%%% end example6b %%%
\end{center}

Et l'élimination de l'état $1$ conduit alors à l'automate ayant un
unique état $0$, à la fois initial et final, avec une transition vers
lui-même étiquetée $0|1(01{*}0){*}1$.  Tel quel, cet automate n'est
pas sous la forme d'une expression rationnelle parce que l'état
initial et l'état final ne sont pas distincts, mais on peut bien sûr
les séparer, et on obtient l'expression rationnelle
$(0|1(01{*}0){*}1){*}$.

On pouvait aussi choisir d'éliminer l'état $1$ en premier, ce qui
conduit à l'automate suivant :

\begin{center}
%%% begin example6c %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q0) at (18bp,20.114bp) [draw,circle,state,initial,final,accepting below] {$0$};
  \node (q2) at (104bp,20.114bp) [draw,circle,state] {$2$};
  \draw [->] (q2) ..controls (82.598bp,6.6202bp) and (75.237bp,2.9515bp)  .. (68bp,1.1137bp) .. controls (59.228bp,-1.1137bp) and (49.898bp,1.2372bp)  .. node[auto] {$01$} (q0);
  \draw [->] (q0) ..controls (47.743bp,20.114bp) and (62.773bp,20.114bp)  .. node[auto] {$10$} (q2);
  \draw [->] (q0) to[loop above] node[auto] {$0|11$} (q0);
  \draw [->] (q2) to[loop above] node[auto] {$1|00$} (q2);
%
\end{tikzpicture}

%%% end example6c %%%
\end{center}

\noindent et finalement à l'expression rationnelle
$(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente.


%
%
%
\end{document}