\chapterimage{gabuzo}
\chaptertext{Nous  essaierons  dans  ce  chapitre de  découvrir  comment
parler à une machine...Quand nous  parlons entre nous, nous utilisons un
\textit{langage naturel} dont les ambiguïtés  en font un moyen à la fois
riche et  difficile de communication.  Une machine n'a pas  notre humour
et notre  goût pour la  poésie: elle utilise un  \textit{langage formel}
qui doit la  renseigner de manière précise. Tout  doit être correctement
spé-ci-fié.

Notre but sera donc de jeter  les bases des langages entre l'homme et la
machine ou même entre machines.

Pour citer Jacques \textsc{Sakarovitch}, grand spécialiste de la théorie
des automates:

\og  \textit{Les automates  finis, c'est  l'infini mis  à la  portée des
informaticiens}\fg{}

reprenant à son  compte cette sentence de L.F.  \textsc{Céline} dans \og
Voyage au bout de la nuit\fg{}:

\og \textit{L'amour, c'est l'infini mis à la portée des caniches}\fg{}...

}




\chapter{Langages et automates}
% Mais trêve  de philosophie, retournons à l'école  maternelle et révisons
% notre alphabet...


\section{Langages}

\subsection{Un exemple pour découvrir}

Reconnaître des mots est une tâche très importante en informatique qu'on
retrouve dans des domaines aussi divers que:
\begin{itemize}
\item  les   compilateurs  qui  transforment  un  code   de  haut  niveau,
  compréhensible  par   un  humain,  en  un   code  machine  directement
  utilisable par l'ordinateur;
\item les éditeurs de texte et les traitements de texte;
\item les bases de données, les moteurs de recherche;
\item les motifs de pixels sur un écran,...
\end{itemize}


Nous nous occuperons donc aussi bien de reconnaître un A dans ce code:



\begin{Verbatim}
oooxooo
ooxxxoo
ooxoxoo
oxxoxxo
oxxxxxo
xxoooxx
xooooox  
\end{Verbatim}



que de l'exemple suivant:
nous  avons   déjà  découvert   que  les  machines   de  \textsc{Turing}
utilisaient  un   \textit{alphabet}  assez  sommaire   pour  former  des
\textit{mots};  nous  avons  donné  des  définitions  générales  de  ces
notions.

Voyons  à  présent  un  exemple  plus complexe  correspondant  plutôt  à
l'action d'un compilateur (votre maîtresse d'école vous
a peut-être présenté les  choses ainsi). Nous voudrions que l'ordinateur
puisse  produire  la  phrase  suivante  (ou  vérifier  qu'elle  est  \og
correcte\fg{}):

\begin{center}
  \textit{LA JEUNE FILLE ÉTUDIE LE BEAU COURS.}
\end{center}

L'\textit{alphabet des symboles} est:

$$A=\bigl\{\text{LA, JEUNE, FILLE, ÉTUDIE, LE, BEAU, COURS, .}\bigr\}$$


Vous avez noté que le mot  \og alphabet\fg{} n'est pas à prendre au sens
usuel  du  terme.  Par  exemple, \verb+def+,  \verb+return+,  \verb+if+,
\verb+for+ sont des éléments de l'alphabet de symboles de Python.


Maintenant,  ces  symboles  ne  peuvent  pas  être  assemblés  n'importe
comment; il  faut suivre les règles d'une  \textit{grammaire} dont voici
un exemple:

\begin{enumerate}
\item <phrase> $\to$ <sujet><verbe><complément><ponctuation>
\item <sujet> $\to$ <groupe nominal>
\item <complément> $\to$ <groupe nominal>
\item <groupe nominal> $\to$ <article féminin><adjectif féminin><nom féminin>
\item <groupe nominal> $\to$ <article féminin><nom féminin><adjectif féminin>
\item <groupe nominal> $\to$ <article féminin><nom féminin>
\item <groupe nominal> $\to$ <article masculin><adjectif masculin><nom masculin>
\item <groupe nominal> $\to$ <article masculin><nom masculin><adjectif masculin>
\item <groupe nominal> $\to$ <article masculin><nom masculin>
\item <article masculin> $\to$ LE
\item <article féminin> $\to$ LA
\item <adjectif féminin> $\to$ JEUNE
\item <adjectif masculin> $\to$ JEUNE
\item <adjectif masculin> $\to$ BEAU
\item <nom féminin> $\to$ FILLE
\item <nom masculin> $\to$ COURS
\item <verbe> $\to$ ÉTUDIE
\item <ponctuation> $\to$ .
\end{enumerate}

Ici, <phrase> est l'\textit{axiome}: c'est notre point de départ.

Les \textit{variables} sont les termes entre <>.

Les règles 1 à 9 sont les \textit{règles syntaxiques}, la première étant
toujours l'axiome.

Les règles 10 à 18 sot les \textit{règles lexicales}.


Le \textit{langage  engendré} par la grammaire est  l'ensemble de toutes
les  phrases  que l'on  peut  former  en  respectant les  règles.  Voici
quelques exemples  de phrases \og  grammaticalement correctes\fg{} comme
disait votre maîtresse:


\begin{center}
LE JEUNE COURS ÉTUDIE LA FILLE.

LA FILLE ÉTUDIE LE JEUNE COURS.

LA FILLE ÉTUDIE LE COURS.
\end{center}

La grammaire ne suffit pas: certaines phrases heurtent notre sens commun
mais ceci est une autre histoire...

\begin{remarque}
Pour éviter le caractère ambigu des termes \og mot\fg{}, \og lettre\fg{}
employés dans de nombreux ouvrages et même un peu plus tôt dans ce cours, nous préférerons dans le cours qui
suit utiliser les  termes \og symbole\fg{} et \og  chaînes\fg{} car nous
venons de voir qu'une \og  lettre\fg{} au sens mathématique peut être un
\og mot\fg{}  au sens courant...De plus, les  termes \og caractères\fg{}
et \og chaînes\fg{} désignent habituellement, dans
les langages informatiques, des types de variables qui
correspondent aux notions que nous allons introduire.
\end{remarque}

Le domaine  que nous allons étudier  a été défriché  par des linguistes,
des  mathématiciens,  des  informaticiens,  des philosophes.  Voici  par
exemple   des   portraits  du   linguiste   Noam  \textsc{Chomski},   du
mathématicien  Stephen \textsc{Kleene}  et  de l'informaticienne  Sheila
\textsc{Greibach} qui  ont donné  leur nom à  de nombreuses  notions que
nous croiserons dans notre cours:



%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{chomski}\hfill
\includegraphics[height=5cm]{kleene}\hfill
\includegraphics[height=5cm]{greibach}
\end{center}
%\end{figure}

Noam \textsc{Chomski}, né en 1928 et professeur de linguistique au MIT, est également
connu pour son engagement politique 
(une   recherche  sur  le   nombre  d'occurrences   de  la   chaîne  \og
Chomski\fg{} dans  n'importe quel numéro  du \textit{Monde diplomatique}
est un exercice de mise en  pratique de notre cours et renverra toujours
un résultat non nul...)


Stephen \textsc{Kleene} (1909 - 1994) est un mathématicien américain dont nous avons
déjà  parlé car  il  a fondé  la  théorie de  la  récursion avec  Alonzo
\textsc{Church},  Kurt \textsc{Gödel}  et Alan  \textsc{Turing}.  Il est
l'inventeur du concept d'expression  rationnelle et de langage rationnel
que nous retrouverons tout au long de ce cours.

Sheila \textsc{Greibach},  née en 1939  et professeur à UCLA  a effectué
d'importantes  recherches  dans le  domaine  des  langages formels,  des
automates et des compilateurs.
\subsection{Définitions et notations}


\begin{definition}
  Un \textit{alphabet} est un ensemble  fini non vide. Les éléments sont
  appelés des \textit{symboles} ou des \textit{caractères}.
\end{definition}


Nous avons rencontré l'alphabet $\bigl\{\varepsilon,1,0\bigr\}$ du ruban
des machines de \textsc{Turing}, mais aussi l'ensemble $\bigl\{\text{LA, JEUNE, FILLE, ÉTUDIE,
  LE,  BEAU, COURS,  .}\bigr\}$ dans  l'exemple d'introduction.  On peut
aussi penser à $\bigl\{0,1,2,3,4,5,6,7,8,9,+,\times,-,/,(,)\bigr\}$ pour
écrire   des  expressions  arithmétiques   dans  $\bbn$,   à  l'alphabet
\textsc{Morse} $\bigl\{\cdot,  -, \_\bigr\}$.  On  peut également penser
au \textit{Petit Robert} comme un alphabet, une phrase étant une chaîne,
un symbole étant un mot...Plus informatiquement, considérons des fichiers texte:
l'alphabet peut  être constitué  des lignes se  terminant par  un retour
chariot, une chaîne étant un fichier.

\medskip

 Une  \textit{chaîne} est  une  juxtaposition de  symboles. On  appelle
  cette juxtaposition la \textit{concaténation}.



Plus rigoureusement:



\begin{definition}
 Soit A un alphabet.  Soit $ \vide_A$ la \textit{chaîne vide} (ne comportant aucun
symbole). 

L'ensemble $ A^\star{}$ des chaînes construites avec l'alphabet A est
défini par:
\begin{enumerate}
\item $ \vide_A \in A^\star{}$;
\item si $ a\in A$ et $ c\in A^\star{}$, alors la chaîne construite à partir de
  $c$ en concaténant $a$ à droite est une chaîne de $ A^\star{}$;
\item $\mu$  est un élément de  $A^\star{}$ seulement s'il peut  être obtenu à
  partir de $\vide_A$ par application de l'étape 2 un nombre fini de fois.
\end{enumerate}
La
  \textit{longueur}  d'une  chaîne est  le  nombre  de  symboles qui  la
  composent.
On note souvent $|\mu|$ la longueur de la chaîne $\mu$. En particulier $|\vide_A|=0$.


On note $|\mu|_a$ le nombre d'occurrences du symbole $a$ dans la chaîne $\mu$.
On note $A^n$ l'ensemble de toutes les chaînes de longueur $n$.

Par convention, $A^0=\bigl\{\vide_A\bigr\}$ qui n'est donc pas vide.

$A^\star{}  = \displaystyle\bigcup_{n  \geqslant 0}A^n$:  c'est  l'ensemble de
toutes les chaînes, éventuellement vides.

$A^+= \displaystyle\bigcup_{n  > 0}A^n$:  c'est  l'ensemble de
toutes les chaînes non vides.

La concaténation des chaînes $\mu$ et $\nu$ sera notée $\mu\nu$.

\end{definition}

Par  exemple, si $A=\bigl\{0,1,2,3,4,5,6,7,8,9,+,\times,-,/,(,)\bigr\}$,
alors $3*(4-2)+8$ et $)32+-7$  sont des chaînes de longueurs respectives
9 et 6.


Vous  aurez noté  que les  notations rappellent  la notion  de fermeture
transitive et transitive réflexive...

Vous aurez noté que $A^1=A$.

Vous aurez noté que A a beau être fini, $A^\star{}$ est infini.

\begin{notation}
Par convention, nous noterons en général les symboles avec les premières
lettres  de l'alphabet  latin ($a$,  $b$, $c$,  $d$,...), les  chaînes  avec des
lettres grecques ($\mu$, $\nu$, $\xi$,...) et les alphabets avec des majuscules.
\end{notation}




\begin{remarque}
La concaténation  est une \textit{loi de composition  interne} sur $A^\star{}$
car en concaténant deux éléments  de $A^\star{}$, on obtient encore un élément
de $A^\star{}$.

Cette  loi  est  également  associative et  possède  un  \textit{élément
  neutre}   $\vide$.   Cela   confère   à  $A^\star{}$   la   structure   de
\textit{monoïde   libre},  selon   les   standards  informatiques.   Les
mathématiciens  parlent   de  \textit{magma  associatif   unitaire}.  En
anglais, on utilise le terme \textit{lattice}.
\end{remarque}


L'associativit\'{e} nous permet d'utiliser la notation \textit{puissance}: 

$$
a^{n}=\underset{n\text{ fois}}{\underbrace{aa\ldots a}}\text{ ; }a^{n}b^{k}=%
\underset{n\text{ fois}}{\underbrace{aa\ldots a}}\underset{k\text{ fois}}{%
\underbrace{bb\ldots b}}\text{ ; }\left( ab\right) ^{n}=\underset{n\text{
fois }ab}{\underbrace{ababab\ldots ab}}
$$


Par convention on pose $a^{0}=%
\vide $ pour tout $a$ \'{e}l\'{e}ment de $A.$



\begin{definition}
\begin{itemize}
\item   On dit que $\mu\in A^\star{}$ est un \textit{préfixe} de $\nu\in A^\star{}$ si, et
  seulement si, il existe $\xi\in A^\star{}$ telle que $\nu = \mu\xi$.  Si
  $\xi\neq\vide$, on dit que $\mu$ est un \textit{préfixe propre} de $\nu$.
\item On dit que $\mu\in A^\star{}$ est un \textit{suffixe} de $\nu\in A^\star{}$ si, et
  seulement si, il existe $\xi\in A^\star{}$ telle que $\nu = \xi\mu$.  Si
  $\xi\neq\vide$, on dit que $\mu$ est un \textit{suffixe propre} de $\nu$.
\item On dit que $\mu\in A^\star{}$ est un \textit{facteur} de $\nu\in A^\star{}$ si, et
  seulement si, il existe $\xi\in A^\star{}$ et $xi'\in A^\star{}$ telles que $\nu = \xi\mu\xi'$.  Si
  $(\xi,\xi')\neq(\vide,\vide)$,   on   dit   que   $\mu$   est   un
  \textit{facteur propre} de $\nu$.
\item Pour toutes chaînes $\mu$ et $\nu$ de $A^{\ast },$ le quotient \`{a} gauche de $\nu$
par $\mu$ est not\'{e} $\mu^{-1}\nu$ et d\'{e}fini par: 
$$
\mu^{-1}\nu=\left\{ 
\begin{array}{l}
\xi\text{ si }\nu=\mu\xi \\ 
\text{n'a pas de sens si }\mu\text{ n'est pas un pr\'{e}fixe de }\nu%
\end{array}%
\right.
$$%
On d\'{e}finit de m\^{e}me le quotient \`{a} droite.

\end{itemize}
\end{definition}


Si $\mu=aababc,$ le quotient \`{a} gauche de $\mu$ par $aab$ est $abc.$



\begin{definition}
Une chaîne $\mu$ \'{e}tant une suite (finie) de symboles, on appelle \textit{sous-chaîne} de $\mu$
toute sous-suite de la suite $\mu.$ Tout facteur de $\mu$ est une sous-chaîne de $\mu$
mais la r\'{e}ciproque est fausse, un sous mot de $\mu$ contient des lettres
de $\mu$ dans le bon ordre mais pas forc\'{e}ment de fa\c{c}on cons\'{e}cutive.

\end{definition}

Si $\mu=aabbaabc,$ $abba$ est une sous-chaîne qui est aussi un facteur, $bbb$ est
une sous-chaîne qui n'est pas un facteur.



\begin{definition}
  Si $\mu=a_{i_{1}}a_{i_{2}}\ldots a_{i_{n}}$ est une chaîne de $A^{\ast },$ sa
\textit{transpos\'{e}e} (ou son image miroir) est la chaîne 
$$
\transp{\mu}=a_{i_{n}}a_{i_{n-1}}\ldots a_{i_{1}}
$$

Un mot qui est \'{e}gal \`{a} son transpos\'{e} est appel\'{e} \textit{palindrome}.

\end{definition}


On notera la propri\'{e}t\'{e} : 


$$
\transp{\left( \mu\nu\right)}=\transp{\nu}\transp{\mu}
$$






\subsection{Langages}


\begin{definition}
  Un \textit{langage} sur A est un sous-ensemble de $A^\star{}$.
\end{definition}



Par exemple, sur l'alphabet $A=\bigl\{\text{LA, JEUNE, FILLE, ÉTUDIE,
  LE, BEAU, COURS, .}\bigr\}$, les ensembles suivants sont des langages:

\begin{itemize}
\item $\bigl\{\text{LA LA LE, LE FILLE BEAU, ÉTUDIE COURS FILLE LA}\bigr\}$;
\item l'ensemble de toutes les chaînes contenant \og FILLE\fg{};
\item l'ensemble de toutes les chaînes de longueur multiple de 37.
\end{itemize}


Si  nous   travaillons  sur  l'alphabet  $B=\bigl\{0,1\bigr\}$,  alors
l'ensemble $B^8$ des chaînes de longueur 8 est l'ensemble bien connu des octets.



Un langage \'{e}tant d\'{e}fini comme un ensemble, il est alors naturel de
s'int\'{e}resser aux op\'{e}rations ensemblistes sur les langages. L'union,
l'intersection, la compl\'{e}mentation et la diff\'{e}rence s'introduisent
naturellement : 


\begin{theoreme}

Si $L$ et $L^{\prime }$ sont deux langages sur l'alphabet $A$
(rappel, $L$ et $L^{\prime }$ sont deux parties de $A^{\ast }$) alors $L\cup
L^{\prime },$ $L\cap L^{\prime },$ $L-L^{\prime }$ et $\complement _{A^{\ast
}}L=\overline{L}$ sont des langages sur $A.$



\end{theoreme}







\begin{notation}
  La r\'{e}union ou l'union $L\cup L^{\prime }$ est aussi not\'{e}e $%
L|L^{\prime }$ et on l'appelle le plus souvent la somme des langages $L$ et $%
L^{\prime }.$
\end{notation}


Nous allons maintenant introduire deux autres op\'{e}rations fondamentales
qui vont nous permettre de d\'{e}crire des langages int\'{e}ressants. Ces op%
\'{e}rations sont le \textbf{produit} ou la \textbf{concat\'{e}nation }de
deux langages et l'\textbf{\'{e}toile} ou la \textbf{fermeture it\'{e}rative 
}(appel\'{e}e aussi \textbf{étoile de Kleene}) d'un langage. Commen\c{c}ons par le 
\textbf{produit} :


\begin{definition}
Si $L$ et $L^{\prime }$ sont deux langages sur $A,$ on d\'{e}finit le
produit du langage $L$ par le langage $L^{\prime }$ (attention \`{a}
l'ordre) le langage not\'{e} $L.L^{\prime }$ ou $LL^{\prime }$d\'{e}fini par 
$$
LL^{\prime }=\left\{ \mu.\mu^{\prime }\mid \mu\in L\text{ et }\mu^{\prime }\in
L^{\prime }\right\} 
$$
\end{definition}

$LL^{\prime }$ est le langage obtenu en faisant le produit
(concat\'{e}nation) de toutes les chaînes de $L$ avec toutes les chaînes de $L^{\prime
}.$



$LL^{\prime }$ est bien un langage et cette op\'{e}ration est manifestement
associative (l'int\'{e}r\^{e}t est de pouvoir se passer de parenth\`{e}%
ses). Alors:

\begin{definition}
On définit récursivement le langage $L^{n}$ : 
$$
\left\{ 
\begin{array}{l}
L^{0}=\left\{ \vide\right\} \text{ par convention (m\^{e}me si }%
L=\varnothing \text{)} \\ 
L^{n+1}=L^{n}L%
\end{array}%
\right.
$$
\end{definition}

Pratiquement $L^{n}$ n'est autre que l'ensemble des chaînes de longueur $n$
construites avec l'\og alphabet\fg{} $L.$ (on accepte cette vision m\^{e}me si $L$
est infini).


Par exemple, soient $L_{1}=\left\{ ab,ba\right\} ,$ $L_{2}=\left\{ c,cc\right\} $ et $%
L_{3}=\left\{ ac\right\} .$ Nous avons 
$$
L_{1}L_{2} =\left\{ abc,abcc,bac,bacc\right\}$$

$$L_{1}L_{2}L_{3} =\left\{ abcac,abccac,bacac,baccac\right\} $$

$$
L_{1}^{2} =\left\{ abab,abba,baab,baba\right\}
$$



\begin{definition}
  Si $n\in \mathbb{N}^{\ast },$ $L^{<n}$ d\'{e}signe le langage 
$$
L^{<n}=\bigcup_{i=0}^{n-1}L^{i}=L^{0}\cup L^{1}\cup \cdots \cup
L^{n-1}
$$
\end{definition}


Pratiquement $L^{<n}$ est l'ensemble des mots de longueur $<n$ que l'on peut
construire avec l'alphabet $L.$


Par exemple, si $L=\left\{ a,ab\right\} $ alors $L^{<3}=\left\{ \vide%
,a,ab,aa,aab,abab,aba\right\} .$





\begin{definition}

On appelle \textbf{\'{e}toile de \textsc{Kleene}} ou \textbf{it\'{e}ration} du langage $L$ le
langage 
$$
L^{\ast }=\bigcup_{k=0}^{+\infty }L^{k}=\bigcup\limits_{k\in \mathbb{N%
}}L^{k}
$$%
L'union de toutes les puissances strictement positives de $L$ \'{e}tant not%
\'{e}e $L^{+}$ : 
$$
L^{+}=\bigcup_{k\in \mathbb{N}^{\ast }}L^{k}\text{ et }L^{\ast
}=L^{+}\cup \left\{ \vide\right\}
$$%
\end{definition}




\begin{remarque}
  
\begin{enumerate}
\item $L^{\ast }$ d\'{e}signe l'ensemble de tous les produits possibles
(penser concat\'{e}nation) d'\'{e}l\'{e}ments de $L$ y compris la chaîne vide,
pratiquement $L^{\ast }$ est le langage d%
\'{e}fini sur l'alphabet $L$ y compris la chaîne vide.

\item Si $L=\left\{ \mu\right\} $ o\`{u} $\mu$ est une chaîne de $A^{\ast }$ on a $%
L^{\ast }=\left\{ \mu^{n}\mid n\in \mathbb{N}\right\} .$ Le plus souvent $%
L^{\ast }$ est not\'{e} simplement $\mu^{\ast },$ en cons\'{e}quence le
langage not\'{e} $a^{\ast }b^{\ast }$ est le langage $L^{\ast }L^{\prime
\ast }$ avec $L=\left\{ a\right\} $ et $L^{\prime }=\left\{ b\right\} .$
Nous utiliserons ces abus\ de notations par la suite lors de la pr\'{e}%
sentation des expressions rationnelles.

\item Si $L=\left\{ \vide\right\} $ alors $L^{\ast }=\left\{ \vide%
\right\} .$ Si $L=\varnothing $ alors $L^{\ast }=\left\{ \vide\right\} $
puisque nous avons d\'{e}cid\'{e} (par convention) que, pour tout langage $%
L, $ nous avions $L^{0}=\left\{ \vide\right\} .$

\item $L^{+}=LL^{\ast }=L^{\ast }L$

\item $L^{\star }=L^{+}\cup \left\{ \vide\right\} =L^{+}|\left\{ \vide\right\} ,$ n'oublions pas que l'union ou la r\'{e}union de deux
langages est aussi not\'{e}e \og$|$\fg{}.
\item  Nous  conviendrons qu'en  l'absence  de  parenthèses, l'étoile  a
  priorité sur la concaténation qui a elle-même priorité sur la réunion.
\end{enumerate}
\end{remarque}






\subsection{Langages et expressions rationnels (ou réguliers)}


Comme souvent en mathématiques, il n'existe pas UNE SEULE définition d'une
notion  mais plusieurs  définitions  équivalentes. C'est  à l'auteur  du
cours de  choisir UNE PARMI  les différentes définitions  possibles: les
autres deviendront des propriétés.


\subsubsection{Langage rationnel}


\begin{definition}[Langage rationnel (ou régulier)]
Soit L un langage sur l'alphabet  A. Il est dit rationnel s'il peut être
obtenu récursivement uniquement à l'aide des opérations:
\begin{itemize}
\item réunion (somme),
\item concaténation (produit),
\item étoile de \textsc{Kleene}
\end{itemize}
en partant:
\begin{itemize}
\item du langage vide $\emptyset$,
\item des langages du type $\bigl\{a\bigr\}$ avec $a\in A \cup \bigl\{\vide_A\bigr\}$.
\end{itemize}
\end{definition}

Voici un exemple pour illustrer cette notion.

Considérons  l'alphabet  $A=\bigl\{b,o,x\bigr\}$  et  L  l'ensemble  des
chaînes finissant par $x$.

Par exemple,  $box$, $bobox$, $xxbobbxoxbbxxoxxxx$,  $x$ appartiennent à
ce langage.

On peut le décrire ainsi:

$$L=            \left(\bigl\{b\bigr\}\cup            \bigl\{o\bigr\}\cup
  \bigl\{x\bigr\}\right)^{\star}\cdot \bigl\{x\bigr\}$$

C'est  donc un langage  rationnel car  obtenu à  partir de  singletons et
d'opérations rationnelles.


Par abus de notation, on se contentera souvent de l'écrire ainsi:

$$L=  (b|o|x)^\star  x  \quad\text{  ou }\quad\left(b^\star  o^\star  x^\star
\right)^\star x \quad\text{ ou }\quad\bigl\{b,o,x\bigr\}^\star x$$




Il est ensuite assez évident de montrer les propriétés suivantes:

\begin{proprietes}
  \begin{itemize}
  \item Tout langage \textbf{fini} est rationnel.
\item Si L est rationnel, alors $L^\star$ est rationnel.
\item Si $L_1$ et $L_2$ sont rationnels, alors $L_1|L_2$ et $L_1L_2$ sont rationnels.
  \end{itemize}
\end{proprietes}

\subsubsection{Expression rationnelle}

Ouvrons  un  shell bash  dans  le répertoire  où  se  trouve un  fichier
contenant un dictionnaire français où les mots sont écrits un par ligne
et suivis éventuellement d'une oblique puis d'un code d'utilisation:

\begin{Verbatim}
a
à/L'D'Q'Qj
a/||--
ab
abaca/S*()
abacule/S*()
abaissable/S*()
abaissante/F*()
abaissée/F*()
abaissée/S*()
abaisse-langue/L'D'Q'
abaissement/S*()
abaisser/a4a+()
abaisseur/S*()
abajoue/S*()
abalober
abalone/S*()
\end{Verbatim}


et lançons la commande suivante:

\shell
\begin{lstlisting}
$ egrep a[^/]*e[^/]*i[^/]*o[^/]*u ./Dictionnaire.txt 
\end{lstlisting}


On obtient:

\begin{lstlisting}[caption={}]
garde-chiourme
gardes-chiourme
quatre-vingt-douze
\end{lstlisting}

On obtient alors toutes les lignes où apparaît une chaîne contenant dans
cet ordre les symboles a, e, i, o et u.

Le code \verb+[^/]+ signifie: \og tous les caractères ASCII sauf /\fg{}, le
caractère \verb+*+ correspondant à l'étoile de \textsc{Kleene}.


La commande \verb+egrep+ permet  en effet d'effectuer une recherche
d'\textit{expression rationnelle} dans un fichier.
Définissons cette notion:

\begin{definition}[Expression rationnelle]
Soit A un alphabet. Une expression rationnelle définie sur A est:
\begin{itemize}
\item $\emptyset$,
\item $\vide_A$,
\item un élément quelconque de A,
\item des \og formules  \textit{bien formées}\fg{} à partir des éléments
  de A en utilisant les opérateurs rationnels. Ainsi, si $R_1$ et $R_2$
  sont des  expressions rationnelles, alors  $(R_1|R_2)$, $R_1\cdot R_2$
  et $R_1^\star$ le sont aussi.
\end{itemize}
\end{definition}


 Disons  qu'intuitivement, il s'agit  de formules
obéissant aux règles de \og syntaxe\fg{} usuelles.

Par exemple, les formules suivantes ne sont pas \textit{bien formées}:

$$ a|\qquad )a|\star b(\qquad |\star a$$

Définissons à présent l'ensemble des chaînes associées à une expression
rationnelle de manière récursive:

\begin{propriete}[Langage décrit par une expression régulière]
\`{A} chaque expression rationnelle $E$ on fait correspondre le langage $%
\mathcal{L}\left( E\right)$  de $A^{\star }$ d\'{e}fini par :

\begin{itemize}
\item $\mathcal{L}\left( \varnothing \right) =\varnothing $

\item $\mathcal{L}\left( \vide_A\right) =\left\{ \func{\vide_A}\right\} $

\item $a\in A,$ $\mathcal{L}\left( a\right) =\left\{ a\right\} $

\item $\mathcal{L}\left( E|E^{\prime }\right) =\mathcal{L}\left( E\right)
\cup \mathcal{L}\left( E^{\prime }\right) =\mathcal{L}\left( E\right) |%
\mathcal{L}\left( E^{\prime }\right) $

\item       $\mathcal{L}\left(      E\cdot       E^{\prime      }\right)
  =\mathcal{L}\left( E\right) \cdot \mathcal{L}\left( E^{\prime }\right) =\mathcal{L}\left( E\right) \mathcal{L}%
\left( E^{\prime }\right) $

\item $\mathcal{L}\left( E^{\star }\right) =\mathcal{L}\left( E\right) ^{\star
}$
\end{itemize}

\end{propriete}


Consid\'{e}rons $E=\left( a|b\right) ^{\ast }\cdot c=\left( a|b\right)
^{\ast  }c,$ et d\'{e}terminons  le langage  $\mathcal{L}\left( E\right)
$ :
\begin{eqnarray*} 
\mathcal{L}\left(  \left( a|b\right) ^{\ast }\cdot c\right)
&=&\mathcal{L}\left(      \left(     a|b\right)      ^{\ast     }\right)
\mathcal{L}\left( c\right) \\
\mathcal{L}\left(   \left(  a|b\right)^{\ast }\cdot c\right) 
&=&\mathcal{L}\left(        a|b\right)
^{\ast             }\mathcal{L}\left(             c\right)            \\
\mathcal{L}\left(      \left(      a|b\right)     ^{\ast      }\cdot c\right)
&=&\left(  \mathcal{L}   \left(  a\right)  |\mathcal{L}\left(  b\right)
\right)      ^{\ast      }\mathcal{L}      \left(      c\right)      \\
\mathcal{L}\left(      \left(      a|b\right)     ^{\ast      }\cdot c\right)
&=&\left(   \left\{    a\right\}   \cup   \left\{    b\right\}   \right)
^{\ast  }\left\{   c\right\}  \\  \mathcal{L}\left(   \left(  a|b\right)
^{\ast }\cdot c\right) &=&\left\{ a,b\right\} ^{\ast }\left\{ c\right\}
 \\  \mathcal{L}\left(   \left(  a|b\right)
^{\ast }\cdot c\right) &=& \bigl\{c,ac,bc,aac,aabbaabaac,bbabababc,...\bigr\}
\end{eqnarray*} 

Le langage $\mathcal{L}\left( E\right) $ est l'ensemble
des chaînes de la forme $\mu c$ o\`{u} $\mu$ est une chaîne quelconque du
langage 
$\left\{ a,b\right\} ^{\ast  }$ ou, si l'on pr\'{e}f\`{e}re,  $\mu$ est la
chaîne vide ou une chaîne  de longueur quelconque form\'{e} \`{a} l'aide
des 
symboles $a$ et $b$ dans n'importe quel ordre. 


Examinons de plus pr\`{e}s
l'expression rationnelle $E=\left( a|b\right) ^{\ast }\cdot c$ pour
appr\'{e}hender  rapidement   le  langage  $\mathcal{L}\left(  E\right)$
qu'elle d\'{e}crit.  Cette 
expression nous donne en fait  une r\`{e}gle de construction des chaînes du
langage $\mathcal{L}\left( E\right)$:

\begin{itemize}
\item on la lit de la gauche vers la droite;
\item  le  signe $|$
correspond au \textbf{ou} inclusif. On l'appelle parfois l'\textit{alternative};
 \item le signe $\cdot $ de la concaténation correspond au
\textbf{et} logique;
\item le  symbole $\mathbf{\star }$ correspond \`{a}
une boucle que  l'on peut ne pas faire ou faire  un nombre quelconque de
fois.
\end{itemize}

 Les chaînes de $\mathcal{L}\left( E\right)$ vont toutes se terminer par $c,$
 les symboles qui 
vont pr\'{e}c\'{e}der $c$ sont d\'{e}crits par $\left( a|b\right)
^{\star }$. Soit on ne rentre pas dans la boucle et le r\'{e}sultat est
$\vide$, soit on rentre dans la boucle autant de fois que l'on veut
et, \`{a} chaque boucle, on choisit $a$ ou bien $b.$

\medskip

Inversement, on peut trouver une expression rationnelle qui correspond à
un langage. Par exemple, nous pouvons décrire le langage sur $A=\bigl\{a,b,c,d\bigr\}$ constitué des
chaînes qui commencent  par $c$ et qui contiennent au  moins un $a$ mais
pas de $d$:



 $$E=c  \left(a^\star b^\star c^\star  \right)^\star a \left(a^\star
    b^\star c^\star \right)^\star$$
 ou bien 
$$E=c(a|b|c)^\star a(a|b|c)^\star$$

 Dans ce qui suit $R,$ $S$ et $T$ sont des expressions
rationnelles et l'\'{e}galit\'{e} d'expressions rationnelles signifie
qu'elles d\'{e}notent le m\^{e}me langage.


\begin{proprietes}

\begin{itemize}
\item $R|S=S|R,R|R=R$
\item  $R|\emptyset =R$
\item $\left( R|S\right) |T=R|\left(
S|T\right)$

\item $R\left( ST\right) =\left( RS\right) T$
\item $R\vide=\vide
R=R$

\item $R\emptyset =\emptyset R=\emptyset$

\item $R\left( S|T\right) =RS|RT, \quad \left( S|T\right) R=SR|TR$.

\item $R^{\star }=R^{\star }R^{\star }=\left( R^{\star }\right) ^{\star }=\left( 
\vide|R\right) ^{\star }$

\item $\left( R|S\right) ^{\star }=\left( R^{\star }S^{\star }\right) ^{\star
}=\left( R^{\star }|S^{\star }\right) ^{\star }=\left( R^{\star }S\right) ^{\star
}R^{\star }$
\item $R^+=R R^\star = R^\star R$
\end{itemize}
\end{proprietes}


Le théorème suivant relie langage et expressions rationnelles:

\begin{theoreme}
Un langage de $A^{\star }$ est rationnel si, et seulement si, il est d\'{e}not%
\'{e} par une expression rationnelle.
\end{theoreme}

En effet, la famille des langages d\'{e}not\'{e}s par une
expression rationnelle contient $\emptyset ,$ $\left\{ \vide\right\} $
et tous les singletons $\left\{ a \right\} $ avec $a \in A$
puisqu'il a bien \'{e}t\'{e} pr\'{e}cis\'{e} que tout langage fini \'{e}tait
rationnel. 

Cette famille est ferm\'{e}e pour l'union, le produit et l'\'{e}%
toile,  elle contient donc  l'ensemble de  tous les  langages rationnels
définis sur $ A$. 


R\'{e}%
ciproquement tout langage d\'{e}not\'{e} par une expression rationnelle est
obtenue \`{a} partir des symboles et de la chaîne vide par une suite
finie d'unions, de produits ou d'\'{e}toiles, il est donc rationnel.



\section{Automates}


\subsection{Définitions}

Nous  avons  déjà abordé  la  notion  d'automates  lors de  l'étude  des
machines de \textsc{Turing} (cf section \vref{autoturing}).

Nous allons généraliser cette notion grâce à la définition suivante:

\begin{definition}[Automate fini]
Un automate $\AR$ est caractérisé par un quintuplet $<A,Q,I,T,\tau$:
\begin{itemize}
\item un alphabet A appelé l'\textit{alphabet d'entrée};
\item un alphabet Q appelé l'\textit{alphabet d'état} (Q est donc \textbf{fini});
\item  une partie  I non  vide de  Q appelée  \textit{ensemble  des états
    initiaux};
\item  une partie T  non vide  de Q  appelée \textit{ensemble  des états
    terminaux};
\item une relation  $\tau$ de $Q\times A$ vers Q  ou de $Q\times \left(A
    \cup \{\vide\}\right)$ vers Q, appelée \textit{relation de transition}.
\end{itemize}
\end{definition}

Par  exemple $\tau(q_1,a)=q_2$  signifie que  quand l'automate  est dans
l'état $q_1$ et qu'il rencontre le symbole a, alors il passe dans l'état
$q_2$.


On a l'habitude  de représenter à l'aide d'un  graphe comme nous l'avons
déjà vu lors de l'étude des machines de \textsc{Turing}.

Cette  fois, les  arcs  vont porter  les  symboles de  l'alphabet A  (ce
symbole sera nommé \textit{étiquette de la transition}).






\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)  {$q_0$};
 \node[state] (B) [ right of=A] {$q_1$};
 \node[state,accepting] (C) [ right of=B] {$q_2$};
 
 \path (A) edge node {a} (B)
       (B) edge [loop above] node {b} (B)
           edge node {c} (C)
      (C)  edge [loop above] node {d} (C);
\end{tikzpicture}
\end{center}

Ici, par  exemple, on dit que $(q_0,a,q_1)$  est une \textit{transition}
de l'automate, que $a$ est l'\textit{étiquette} de cette transition dont
l'\textit{origine}  est  $q_0$  et  l'\textit{extrémité  terminale}  est
$q_1$.

On      pourra      aussi      noter     cette      transition      $q_0
\overset{a}{\longrightarrow } q_1$.


On   peut  aussi   représenter  l'automate   par  sa   \textit{table  de
  transition}:

\begin{center}
             \begin{tabularx}{0.4\linewidth}{Y{2}}
	     \whline
             $\mu$&$q_0$&$q_1$&$q_2$\\
             \whline
             $a$  &$q_1$&&\\
             \hline
             $b$ &&$q_1$&\\
             \hline
             $c$ &&$q_2$&\\
             \hline
             $d$&&&$q_2$\\
             \whline
             \end{tabularx}
             \end{center}

\subsection{Langage reconnaissable}


Reprenons     l'automate     précédent     défini     sur     l'alphabet
$A=\bigl\{a,b,c,d\bigr\}$.  

Les  chaînes $ac$,  $abbbbbc$, $abbbbbcddddd$  semblent  calculables par
l'automate  mais pas  les  chaînes $ad$,  $ddddaa$, $aaabc$.  L'automate
étant  simple, c'est assez  facile à  \og voir\fg{}.  Dans des  cas plus
compliqués,   les    mathématiques   prendront   le    relais   de   nos
yeux. Fabriquons donc nos \og lunettes\fg{}.

\medskip

Un \textbf{calcul }$\mathbf{c}$\textbf{\ }de l'automate $\mathcal{A}$ (ou
une ex\'{e}cution ou une trace de l'automate $\mathcal{A}$) est une suite de
transitions (des relations de $Q\times A$ dans $ Q$) telles que
l'origine de chacune (sauf la premi\`{e}re) co\"{\i}ncide avec l'extr\'{e}mit%
\'{e} terminale de la pr\'{e}c\'{e}dente : 
$$
\mathbf{c}=q_{i_{0}}\xrightarrow{\alpha _{1}}q_{i_{1}}
\xrightarrow{\alpha _{2}}q_{i_{2}}\xrightarrow{\alpha _{3}}
\cdots \xrightarrow{\alpha _{n}}q_{i_{n}}
$$
que l'on note aussi 
$$
\mathbf{c}=q_{i_{0}}\xrightarrow{\alpha _{1}\alpha _{2}\cdots \alpha _{n}}q_{i_{n}}
$$
la longueur de ce calcul \'{e}tant $n$\textbf{\ }(il y a $n$ transitions) et%
\textbf{\ }$\alpha _{1}\alpha _{2}\cdots \alpha _{n}$ est l'\'{e}tiquette du
calcul $\mathbf{c,}$ c'est une chaîne de $A^{\star }$. Il faut remarquer qu'un
calcul a une seule \'{e}tiquette mais qu'une m\^{e}me chaîne peut \^{e}tre l'%
\'{e}tiquette de plusieurs calculs distincts.

Un calcul de $\mathcal{A}$ est \textbf{r\'{e}ussi} si son origine est un 
\'{e}tat initial et son extr\'{e}mit\'{e} terminale un \'{e}tat final. 

Une   chaîne  de  $A^{\star   }$  est   donc  reconnue   par  l'automate
$\mathcal{A}$ si, et 
seulement   si,  c'est   l'\'{e}tiquette  d'un   calcul   r\'{e}ussi  de
$\mathcal{A}.$ 



Ici,  $  q_0  \xrightarrow{abbbbbcdd}q_2$  donc la  chaîne  $abbbbbcdd$  est
reconnue par $\AR$.

\begin{NB}
Si l'automate se bloque pendant la lecture de la chaîne ou n'atteint pas
l'état final, cette chaîne n'est pas reconnue par l'automate.
\end{NB}


\begin{definition}[Langage reconnaissable par un automate]
On note $\mathcal{L}\left( \mathcal{A}\right) $ l'ensemble des chaînes reconnues
par l'automate : 
$$
\mathcal{L}\left( \mathcal{A}\right) =\left\{ \mu\in A^{\star }\mid \exists
q_{i}\in I,\exists q_{t}\in T,q_{i}\xrightarrow{\mu}q_{t}\right\}
$$
et on dit qu'un langage $L$ \textbf{est reconnaissable par l'automate} $%
\mathcal{A}$ ou que l'automate $\AR$ \textbf{reconnaît} le langage L si, et seulement si, $\mathcal{L}\left( \mathcal{A}\right) =L.$

Un langage est \textbf{reconnaissable}  si, et seulement si,il existe AU
MOINS un
automate FINI qui le 
reconnaît.

 L'ensemble des langages reconnaissables sur l'alphabet $A$ est
not\'{e} $\func{Rec}\left( A^{\star }\right) .$


\end{definition}


\subsection{Langage reconnu par un automate fini}


Une  première question  qui vient  à l'esprit  en ayant  le  graphe d'un
automate sous les yeux: quel est le langage reconnu par cet automate?
\subsubsection{Méthode \og manuelle\fg{}}

On essaie de  déterminer pas à pas la  succession de langages permettant
de passer des états initiaux aux états terminaux.

En  utilisant toujours notre  exemple, on  voit qu'avec  $a$ on  passe à
l'état $q_1$.  On peut  y rester en  bouclant avec  des $b$ ou  passer à
l'état terminal $q_2$ avec $c$ en bouclant éventuellement avec des $d$.

Le  langage  reconnu  peut   donc  s'écrire  à  l'aide  de  l'expression
rationnelle $ab^\star cd^\star$.

\subsubsection{Technique d'élimination d'états}


On tente cette fois d'éliminer  les états intermédiaires pour obtenir un
automate à deux états étiqueté par une expression déterminant le langage
reconnu. On généralise ainsi les automates étiquetés par des symboles ou
des chaînes.

Cette technique est dérivée  de l'algorithme de \textsc{Mac Naughton} et
\textsc{Yamada}.

\begin{itemize}
\item On  commence par créer  deux nouveaux  états $q_d$ et  $q_t$ qui
  seront les uniques états initiaux et terminaux. 

On relie $q_d$  à tous les états initiaux  par une transition étiquetée
par $\vide$ et  on relie tous les états terminaux à  $q_t$ par le même
type de transitions.

\item   Notons   Q   l'ensemble   tel  que   l'alphabet   d'états   soit
  $\bigl\{q_d\bigr\}\cup Q \cup \bigl\{q_t\bigr\}$. Tant que Q n'est pas
  vide,  on  applique l'opération  suivante:  pour  tout couple  $(p,r)$
  d'états tels  qu'il existe une transition  directe de $p$ à  $q$ et de
  $q$ à $r$  étiquetée respectivement par $L_{pq}$ et  $L_{qr}$, on crée
  une     transition     $(p,L_{pqr},r)$    avec     $L_{pqr}=L_{pr}\cup
  L_{pq}L_{qq}^\star L_{qr}$.
\end{itemize}


Reprenons notre automate de départ.

\begin{itemize}
\item on ajoute $q_d$ et $q_f$:



\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A) {$q_d$};
 \node[state] (B) [ right of=A] {$q_0$};
 \node[state] (C) [ right of=B] {$q_1$};
 \node[state] (D) [ right of=C] {$q_2$};
 \node[state,accepting] (E) [ right of=D] {$q_t$};
 
 \path (A) edge node {$\vide$} (B)
       (B) edge node {$a$} (C)
       (C) edge [loop above] node {$b$} (C)
           edge node {$c$} (D)
       (D) edge [loop above] node {d} (D)
       (D) edge node {$\vide$} (E);
\end{tikzpicture}
\end{center}

\item      on     élimine     l'état      $q_0$:     $L_{d01}=L_{d1}\cup
  L_{d0}L_{00}^\star L_{01}=\emptyset \cup {\vide}\vide^\star a=a$


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A) {$q_d$};
% \node[state] (B) [ right of=A] {$q_0$};
 \node[state] (C) [ right of=B] {$q_1$};
 \node[state] (D) [ right of=C] {$q_2$};
 \node[state,accepting] (E) [ right of=D] {$q_t$};
 
 \path %(A) edge node {$\vide$} (B)
       (A) edge node {$a$} (C)
       (C) edge [loop above] node {$b$} (C)
           edge node {$c$} (D)
       (D) edge [loop above] node {d} (D)
       (D) edge node {$\vide$} (E);
\end{tikzpicture}
\end{center}

\item   on     élimine     l'état      $q_1$:     $L_{d12}=L_{d2}\cup
  L_{d1}L_{11}^\star L_{12}=\emptyset \cup ab^\star c=ab^\star c$



\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A) {$q_d$};
% \node[state] (B) [ right of=A] {$q_0$};
% \node[state] (C) [ right of=B] {$q_1$};
 \node[state] (D) [ right of=C] {$q_2$};
 \node[state,accepting] (E) [ right of=D] {$q_t$};
 
 \path %(A) edge node {$\vide$} (B)
       (A) edge node {$ab^\star c$} (D)
 %      (C) edge [loop above] node {$b$} (C)
 %          edge node {$c$} (D)
       (D) edge [loop above] node {d} (D)
       (D) edge node {$\vide$} (E);
\end{tikzpicture}
\end{center}


\item   on     élimine     l'état      $q_2$:     $L_{d2t}=L_{dt}\cup
  L_{d2}L_{22}^\star L_{2t}=\emptyset \cup ab^\star cd^\star\vide=ab^\star cd^\star$



\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A) {$q_d$};
% \node[state] (B) [ right of=A] {$q_0$};
% \node[state] (C) [ right of=B] {$q_1$};
% \node[state] (D) [ right of=C] {$q_2$};
 \node[state,accepting] (E) [ right of=D] {$q_t$};
 
 \path %(A) edge node {$\vide$} (B)
       (A) edge node {$ab^\star cd^\star$} (E);
 %      (C) edge [loop above] node {$b$} (C)
 %          edge node {$c$} (D)
 %      (D) edge [loop above] node {d} (D)
 %      (D) edge node {$\vide$} (E);
\end{tikzpicture}
\end{center}





\end{itemize}



%\subsection{Automate reconnaissant un langage}

\subsection{Automates équivalents}

\begin{theoreme}[Automates équivalents]
On définit une relation $\equiv$ sur l'ensemble des automates finis.

Deux automates $\AR$ et $\AR'$ sont en relation si, et seulement si, ils
reconnaissent le même langage.

Cette relation est une relation d'équivalence. On note $\AR \equiv \AR'$
pour signifier que deux automates sont équivalents.
\end{theoreme}


Il est assez évident de démontrer que la relation $\equiv$ est une relation
d'équivalence. Cette notion est très importante en mathématiques et très
utilisée en informatique. Au lieu de considérer les automates finis dans
leur  ensemble,  nous  allons   nous  contenter  de  parler  des  \textbf{classes
d'équivalence}  qui  sont  les  éléments  de  l'ensemble  des  automates
quotienté par $\equiv$. 


\begin{idee}
 Pensez   justement    aux   fractions   rationnelles    qui   renvoient
 naturellement à la notion de quotient:
$\frac{1}{2}$,   $\frac{2}{4}$,  $\frac{3}{6}$,   etc.   sont  des   \og
représentants\fg{} de la classe d'équivalence de $(1,2)$ pour la relation
définie par $(a,b)\RR (x,y) \Leftrightarrow ay = bx$ sur
$\bbz\times  \bbz$. L'ensemble quotient  $\ofr{\bbz\times\bbz}{\RR}$ est
justement l'ensemble...$\bbq$!

La classe de $(1,2)$ est $\bigl\{...,\frac{-2}{-4},\frac{-1}{-2},\frac{1}{2},\frac{2}{4},\frac{3}{6},...\bigr\}$.
\end{idee}

Deux  automates  pourront  donc  \og avoir  l'air\fg{}  différents  mais
représenteront  le  même  langage.  Comme  on  préfère  travailler  avec
$\frac{1}{2}$  plutôt   qu'avec  $\frac{2134}{4268}$,  on   essaiera  de
simplifier  au maximum  un automate  pour débusquer  plus  facilement le
langage qu'il reconnaît.



\subsection{Automates standards}

\begin{definition}[Automate standard]
  Un automate $<A,Q,D,T,\tau>$ est standard si, et seulement si, $D$ est
  réduit à un singleton $\{d\}$ et aucune transition n'aboutit en $d$.
\end{definition}

L'algorithme suivant va nous  permettre de rendre standard tout automate
fini.  Notons   $\AR'$  l'automate  standardisé,   alors  $\AR'=<A,Q\cup
\{d\},\{d\},T',\tau'>$ avec:

\begin{itemize}
\item $d\not\in Q$;
\item si $D\cap T=\emptyset$ alors $T'=T$ sinon $T'=T\cup \{d\}$;
\item $\GR_{\tau'}=\GR_{\tau} \cup  \bigl\{(d,a,q)\mid \exists q_d\in D,\,
  (q_d,a,q)\in \GR_\tau\bigr\}$
\end{itemize}

Cela nous permet d'énoncer le théorème suivant:

\begin{theoreme}
  Tout automate fini est équivalent à un automate standard.
\end{theoreme}

Ou bien \og  toute classe d'équivalence pour $\equiv$  contient un automate
standard\fg{}.


\begin{recherche}
Standardisez l'automate défini sur l'alphabet $ \bigl\{a,b\bigr\}$ par la table de transition suivante:

\begin{center}
             \begin{tabularx}{0.3\linewidth}{Y{1}}
	     \whline
             $\tau$&$a$&$b$\\
             \whline
             $q_0$&$q_1$&\\
             \hline
             $q_1$&$q_1$&$q_0$, $q_2$\\
             \hline
             $q_2$&$q_0$&$q_2$\\
             \whline
             \end{tabularx}
             \end{center}

avec $D=Q$ et $T=\bigl\{q_0\bigr\}$.

\end{recherche}

\subsection{Automates déterministes}

\begin{definition}
Un automate \textit{déterministe}:
\begin{itemize}
\item a un unique état initial;
\item  la relation  de transition  $\tau$ est  une fonction:  il y  a, à
  partir de chaque état, au plus une transition d'étiquette donnée.
\end{itemize}
\end{definition}

Si un automate n'est pas déterministe, il est...non-déterministe.


\begin{definition}
Un automate \textit{déterministe} \textit{complet}:
\begin{itemize}
\item est un automate déterministe;
\item la relation  de transition  $\tau$ est  une application:  il y  a, à
  partir de chaque état, une et une seule transition d'étiquette donnée.
\end{itemize}
\end{definition}




Par exemple:







\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)  {$q_0$};
 \node[state] (B) [ right of=A] {$q_1$};
 \node[state,accepting] (C) [ right of=B] {$q_2$};
 
 \path (A) edge node {a} (B)
       (B) edge [loop above] node {b} (B)
           edge node {b} (C)
      (C)  edge [loop above] node {c} (C);
\end{tikzpicture}
\end{center}

n'est pas  déterministe car $(q_1,b)$  admet deux images par  $\tau$ qui
sont $q_1$ et $q_2$.

Il est possible de rendre cet automate déterministe en regroupant toutes
les images d'un couple donné en un seul état:




\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)  {$q_0$};
 \node[state] (B) [ right of=A] {$q_1$};
 \node[state,accepting] (C) [ right of=B] {${\small\{q_1,q_2\}}$};
 \node[state,accepting] (D)[right of= C] {$q_2$};
 
 \path (A) edge node {a} (B)
       (B) edge node {b} (C)
      (C) edge [loop above] node {b} (C)
       (C) edge node {c} (D)
       (D) edge [loop above] node{c} (D);
\end{tikzpicture}
\end{center}




\begin{theoreme}
Tout automate fini est équivalent à un automate déterministe.
\end{theoreme}

ou bien,  \og toute classe d'équivalence pour  $\equiv$\fg{} contient un
automate déterministe.


Le  problème  d'un  automate   non  déterministe  est  qu'il  est  moins
efficace.  Dans le cas d'un automate déterministe, pour chaque chaîne
reconnue, il existe un unique calcul dont cette chaîne est l'étiquette.


Voici un algorithme qui permet  de manière assez économique d'obtenir un
automate déterministe équivalent à un automate donné.

Considérons un  automate non déterministe  $\AR=<A,Q,\{d\},T,\tau>$ mais
standard et
notons  $\AR^D=<A,Q^D,\{d\},T^D,\tau^D>$   l'automate  construit  de  la
manière suivante:

\begin{itemize}
\item au départ, $Q^D\leftarrow \bigl\{d\bigr\}$;
\item on  détermine les  images non vides  de chaque  couple $(\{d\},a)$
  pour chaque $a$ dans A. On obtient de nouveaux états $q^D_i$ que l'on met
  dans $Q^D$;
\item on  recommence ainsi avec  les images des $(q_i^D,a)$  pour chaque
  $a$ dans A;
\item on s'arrête quand on ne crée plus de nouveaux états;
\item $T^D$ est l'ensemble des $q_i^D$ qui contienne un état terminal de $\AR$.
\end{itemize}


\begin{recherche}
  Vérifiez que  l'algorithme précédent permet de  montrer que l'automate
  défini par:

\begin{center}
             \begin{tabularx}{0.5\linewidth}{Y{1}}
	     \whline
             $\tau$&$a$&$b$\\
             \whline
             $q_1$&$q_1$, $q_2$&$q_1$\\
             \hline
             $q_2$&&$q_3$\\
             \hline
             $q_3$&$q_3$&$q_3$\\
             \whline
             \end{tabularx}
             \end{center}

avec $I=\{q_1\}$ et $T=\{q_3\}$ est équivalent à:


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=3.2cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 6em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)  {$q_1$};
 \node[state] (B) [ right of=A] {${\small\{q_1,q_2\}}$};
 \node[state,accepting] (C) [ right of=B] {${\small\{q_1,q_3\}}$};
 \node[state,accepting] (D) [ right of=C] {${\small\{q_1,q_2,q_3\}}$};
 
 \path (A) edge [loop above] node {b} (A)
       (A) edge node {a} (B)
       (B) edge [loop above] node {a} (B)
       (B) edge node {b} (C)
       (C) edge [loop above] node {b} (C)
       (C) edge [bend left] node {a} (D)
       (D) edge [bend left] node {b} (C)
       (D) edge [loop above] node {a} (D);
\end{tikzpicture}
\end{center}


\end{recherche}








\subsection{Automates émondés}

Ouvrons le dictionnaire:

\begin{quote}
  \textbf{ÉMONDER} v.  tr. (lat. \textit{emundare},  de \textit{mundus},
  propre; v,  1200, \og  purifier\fg{}). \textbf{1.} (1354).  Couper les
  branches    inutiles    :    \textit{Émonder   un    peuplier}.    ---
  \textbf{2}.  Débarrasser  du superflu:  \textit{Émonder  un récit  des
    détails inutiles}.
\end{quote}

Tout est dit...Enfin, pour avoir quelque chose de plus rigoureux afin de
l'utiliser     informatiquement,     donnons    quelques     définitions
intermédiaires.

\begin{definition}[États accessibles et co-accessibles]

Soit $\AR=<A,Q,D,T,\tau>$ un automate fini.

\begin{itemize}
\item On dit que l'\'{e}tat $q_{j}$ $\left( q_{j}\in Q\right) $ est \textbf{%
accessible \`{a} partir d'un \'{e}tat} $q_{i}$ $\left( q_{i}\in Q\right) $
s'il existe  (au moins) un  calcul $\mathbf{c}$ dans  $\mathcal{A}$ dont
l'origine est $q_{i}$ et l'extr\'{e}mit\'{e} est $q_{j}$.
On dit que l'\'{e}tat $q_{j}$ est \textbf{accessible} s'il est accessible 
\`{a} partir d'un \'{e}tat initial.

\item Un \'{e}tat $q_{i}$ est \textbf{co-accessible \`{a} un \'{e}tat} $%
q_{j}  $ s'il  existe  un calcul  $\mathbf{c}$  dans $\mathcal{A}$  dont
l'origine est $q_{i}$ et l'extr\'{e}mit\'{e} est $q_{j}.$
On dit que l'\'{e}tat $e_{i}$ est \textbf{co-accessible} s'il est
co-accessible d'un \'{e}tat final.

\item On dit qu'un \'{e}tat $q_{i}$ est \textbf{utile} s'il est \`{a} la
fois accessible et co-accessible.
\end{itemize}
\end{definition}

Ceci nous permet de définir un automate émondé:

\begin{definition}[Automate émondé]
Un automate émondé est un automate dont tous les états sont utiles.
\end{definition}

On peut définir deux algorithmes servant à émonder un automate donné. Il
s'agit de supprimer  les états non accessibles ou  non co-accessibles et
les transitions qui en dépendent.

On considère toujours notre automate fini $\AR=<A,Q,D,T,\tau>$.


\begin{algo}
\FUNC{émondage aller}{%
\pfarg{$\AR$}{automate fini}}{automate fini}
\BEGIN
\STATE{$E$ \recoit{} D}
\STATE{$E'$ \recoit{} $\emptyset$}
\WHILE{$E'\neq E$}
\STATE{$E'$\recoit{} $E$}
\STATE{$E$ \recoit{} $E\cup \bigl\{q\in  Q\mid \exists e \in E, \exists
  a \in A: (e,a,q)\in \GR_\tau\bigr\}$}
\ENDWHILE
\RETURN{$<A,E,D,T,\tau'>$}
\END
\end{algo}


\begin{algo}
\FUNC{émondage retour}{%
\pfarg{$\AR$}{automate fini}}{automate fini}
\BEGIN
\STATE{$C$ \recoit{} $T\cap E$}
\STATE{$C'$\recoit{} $\emptyset$}
\WHILE{$C'\neq C$}
\STATE{$C'$\recoit{} $C$}
\STATE{$C$ \recoit{} $C\cup \bigl\{q\in  Q\mid \exists c \in C, \exists
  a \in A: (q,a,c)\in \GR_\tau\bigr\}$}
\ENDWHILE
\RETURN{$<A,C,D,T,\tau''>$}
\END
\end{algo}

\begin{recherche}
Standardisez    et   émondez    l'automate    défini   sur    l'alphabet
$\bigl\{a,b\bigr\}$ à l'aide de la table de transition suivante:

\begin{center}
             \begin{tabularx}{0.5\linewidth}{Y{1}}
	     \whline
             $\tau$&$a$&$b$\\
             \whline
             $q_1$&$q_1,q_2$&\\
             \hline
             $q_2$&&$q_3$\\
             \hline
             $q_3$&$q_3$&$q_3$\\
             \hline
             $q_4$&$q_3$&$q_2$\\
             \whline
             \end{tabularx}
             \end{center}

avec $D=\bigl\{q_1,q_3\bigr\}$ et $T=\bigl\{q_1,q_2\bigr\}$

\end{recherche}

On peut montrer  qu'éliminer les états qui ne sont  pas utiles ne change
pas le langage reconnu par un automate et donc:

\begin{theoreme}
Tout automate fini est équivalent à un automate émondé
\end{theoreme}

ou  bien  \og  toute  classe  d'équivalence pour  $\equiv$  contient  un
automate émondé\fg{}.


En  fait,  émonder  un  automate  déterministe,  c'est  tous  les  états
inaccessibles à partir de l'état  initial et tous ceux à partir desquels
on ne peut pas atteindre un état terminal. C'est assez logique...



\subsection{Automate minimal}

\subsubsection{Théorème de \textsc{Myhill-Nerode}}

Minimiser un automate consiste à regrouper  deux états $q$ et $q'$ si ce
sont  les  mêmes  chaînes qui  permettent  d'aller  de  $q$ et  de  $q'$
respectivement vers un état final. Il faudrait être sûr que cet automate
(qui est équivalent  à l'automate d'origine de manière évidente)
est  celui qui  possède  le plus  petit  nombre d'états  parmi tous  les
éléments de sa classe d'équivalence.

% Nous  allons prouver  cette idée  intuitive en  introduisant  de nouvelles
% classes d'équivalence\footnote{Comme  quoi cette notion  vue en première
%   période est fondamentale en informatique...}

Dans  toute la  suite  on considère  un  alphabet A,  un  langage L  sur
$A^\star$     et    un     automate     \textit{déterministe}
$\AR=\bigl<A,Q,\{d\},T,\tau\bigr>$ qui reconnaît L.



% $$a\RR_L b \Leftrightarrow (\forall c,\, ac\in L \Leftrightarrow bc \in L)$$


% Deux chaînes sont équivalentes selon cette relation si, et seulement si, elles sont le
% préfixe de deux chaînes de L de même suffixe. 

% On peut également définir une relation d'équivalence correspondante pour
% l'automate:

% $$ a \RR_{\AR} b \Leftrightarrow \tau(d,a)=\tau(d,b)$$
% Deux chaînes sont équivalentes selon cette relation si, et seulement si,
% elles sont l'étiquette d'un même calcul d'origine $d$.

% La  relation  $\RR_{\AR}$   est  d'indice  fini\footnote{L'indice  d'une
%   relation d'équivalence est le cardinal de l'ensemble des classes d'équivalence.}
%  car il y a une classe par état de l'automate qui est à états fini.

% Alors on peut montrer que $\RR_L$ est aussi d'indice fini.

% On peut donc construire un automate  à états finis à partir 
% de $\RR_L$: ses états sont les classes d'équivalence de $\RR_L$.

% Soit $\alpha_i\in  L$ et $\dot{\alpha_i}$ une classe  de $\RR_L$. Alors,
% pour          tout          $a\in          A$,          on          pose
% $\tau_L(\dot{\alpha_i},a)=\dot{(\alpha_ia)}$. On montre que cet automate
% reconnaît L.


% Ceci nous permet d'énoncer le théorème suivant:


\begin{definition}[États distinguables]
Deux états  $q_i$ et  $q_j$ dans $Q$  sont distinguables par  la chaînes
$\mu\in A^\star$ si:
\begin{itemize}
\item $\tau(q_i,\mu)\in T$ et $\tau(q_j,\mu)\not\in T$
\item $\tau(q_i,\mu)\not\in T$ et $\tau(q_j,\mu)\in T$
\end{itemize}

Deux  états  sont \textbf{indistinguables}  s'ils  ne  sont distinguables  par
aucune chaîne.
\end{definition}


Par exemple, $q_0$ et $q_1$ sont-ils distinguables par $a$? Par $b$?

Par quelle chaîne $q_1$ et $q_2$ sont-ils distinguables?


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)  {$q_0$};
 \node[state] (B) [ right of=A] {$q_1$};
 \node[state,accepting] (C) [ right of=B] {$q_2$};
 
 \path (A) edge[loop above] node {a} (A)
       (A) edge[bend left] node {b} (B)
       (B) edge [bend left] node {a} (A)
       (B) edge node {b} (C);
\end{tikzpicture}
\end{center}




\begin{theoreme}[Équivalence de \textsc{Nerode}]
On définit la relation:

 $$ q_i  \equiv_N q_j  \Leftrightarrow q_i \text{  et } q_j  \text{ sont
   indistinguables}$$

C'est une classe d'équivalence. 
\end{theoreme}






Les  classes  d'équivalence de  cette  relation  sur  $Q$ réalisent  une
partition  de $Q$.  Les différentes  classes d'équivalence  permettent de
définir   un  nouvel   ensemble  d'états   $Q'$  d'un   nouvel  automate
$\AR'=\bigl<A,Q',\{d\},T',\tau'\bigr>$ avec:

\begin{itemize}
\item $\forall q\in  Q,\ \tau(q,a)=q_i \Longrightarrow \tau'(q',a)=q'_i$
  avec $q'$ et $q_i'$ les classes d'équivalences de $q$ et $q_i$;
\item $d'$ est la classe de $d$;
\item $T'$ est l'ensemble des classes des éléments de T.
\end{itemize}



\begin{theoreme}[Théorème de \textsc{Myhill-Nerode} (1958)]
Soit L un langage reconnaissable. Parmi tous les automates déterministes
 finis  qui reconnaissent L,  il en  existe un  et un  seul (au  nom des
 états près)  qui a un nombre minimum  d'états. C'est \textit{l'automate
   minimal} de L.
\end{theoreme}

On pourrait démontrer  que l'algorithme minimal est celui  défini par la
relation d'équivalence de \textsc{Nerode}.


Nous allons  plutôt proposer un \textbf{algorithme  de minimisation} qui
va  nous  permettre  de  construire  l'automate  minimal  d'un  automate
déterministe fini donné.


\subsubsection{Algorithme de minimisation de \textsc{Moore}}



Considérons l'exemple suivant:

%
%

\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial,accepting left, double] (A) {$q_0$};
 \node[state] (C) [ right of=A] {$q_2$};
 \node[state] (B) [ below of=C] {$q_1$};
 \node[state,accepting below, double,fill=blue!20] (D) [ right of=C] {$q_3$};
 \node[state] (F) [ right of=D] {$q_5$};
 \node[state,accepting below, double,fill=blue!20] (E) [ below of=F] {$q_4$};
 \node[state,accepting right, double,fill=blue!20] (G) [ right of=F] {$q_6$};
 \node[state,accepting below, double,fill=blue!20] (H) [ below of=G] {$q_7$};


 
 \path (A) edge node {a} (C)
       (A) edge node {b} (B)
       (B) edge[loop below] node {b} (B)
       (C) edge node {a} (D)
       (C) edge[loop above] node {b} (C)
       (B) edge node {a} (C)
       (D) edge node {a} (F)
       (D) edge node {b} (E)
       (E) edge[loop right] node {b} (E)
       (E) edge node {a} (F)
       (F) edge[loop above] node {b} (F)
       (F) edge[bend left] node {a} (G)
       (G) edge [bend left] node {a} (F)
       (G) edge node {b} (H)
       (H) edge node {a} (F)
       (H) edge[loop right] node {b} (H)
       ;
\end{tikzpicture}
\end{center}

\begin{center}
\begin{tabular}[h]{c|*{8}{c}}
  &$q_0$&$q_1$&$q_2$&$q_3$&$q_4$&$q_5$&$q_6$&$q_7$\\
\hline
\rowcolor{gray!50}
$\vide$&1&2&2&1&1&2&1&1\\
\end{tabular}
\end{center}
La classe  1 regroupe  en fait les  états terminaux  et la classe  2 les
autres.


On  regarde maintenant  pour  chaque  état vers  quelle  classe mène  la
transition par un caractère de A, à raison d'une ligne par caractère:

\begin{center}
\begin{tabular}[h]{c|*{8}{c}}
  &$q_0$&$q_1$&$q_2$&$q_3$&$q_4$&$q_5$&$q_6$&$q_7$\\
\hline
\rowcolor{gray!50}
$\vide$&1&2&2&1&1&2&1&1\\
$a$&2&2&1&2&2&1&2&2\\
$b$&2&2&2&1&1&2&1&1\\
%\hline
%& 1&2&3&4&4&3&4&4\\
\end{tabular}
\end{center}
On regarde maintenant colonne par colonne et on crée une nouvelle classe
dès qu'on rencontre une colonne différente:


\begin{center}
\begin{tabular}[h]{c|*{8}{c}}
  &$q_0$&$q_1$&$q_2$&$q_3$&$q_4$&$q_5$&$q_6$&$q_7$\\
\hline
\rowcolor{gray!50}
$\vide$&1&2&2&1&1&2&1&1\\
$a$&2&2&1&2&2&1&2&2\\
$b$&2&2&2&1&1&2&1&1\\
\hline
\rowcolor{gray!50}
& 1&2&3&4&4&3&4&4\\
\end{tabular}
\end{center}

On  réitère   l'opération  tant  qu'on  obtient  des   lignes  de  bilan
différentes:



\begin{center}
\begin{tabular}[h]{c|*{8}{c}}
  &$q_0$&$q_1$&$q_2$&$q_3$&$q_4$&$q_5$&$q_6$&$q_7$\\
\hline
$\vide$&1&2&2&1&1&2&1&1\\
$a$&2&2&1&2&2&1&2&2\\
$b$&2&2&2&1&1&2&1&1\\
\hline
\rowcolor{gray!50}
& 1&2&3&4&4&3&4&4\\
$a$&3&3&4&3&3&4&3&3\\
$b$&2&2&3&4&4&3&4&4\\
\hline
\rowcolor{gray!50}
&1&2&3&4&4&3&4&4
\end{tabular}
\end{center}


On  s'arrête. Les  transitions sont  même données  par la  pénultième et
l'antépénultième ligne.


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial,accepting left, double] (A) {$1$};
 \node[state] (C) [ right of=A] {$3$};
 \node[state] (B) [ below of=C] {$2$};
 \node[state,accepting below, double,fill=blue!20] (D) [ right of=C] {$4$};



 
 \path (A) edge node {a} (C)
       (A) edge node {b} (B)
       (B) edge[loop below] node {b} (B)
       (C) edge[loop above] node {b} (C)
       (B) edge node {a} (C)
       (C) edge[bend left] node {a} (D)
       (D) edge [bend left] node {a} (C)
       (D) edge[loop above] node {b} (D)
       ;
\end{tikzpicture}
\end{center}



\begin{remarques}
  \begin{itemize}
  \item  Si l'automate n'est  pas complet,  on marquera  les transitions
    manquantes par $\emptyset$.
\item l'unicité de l'automate minimal permet de comparer deux automates:
  s'ils ont le même automate minimal, ils sont équivalents.
\item  on peut  appliquer l'algorithme  de \textsc{Moore}  pour vérifier
  qu'un automate est minimal.
  \end{itemize}
\end{remarques}


\subsection{Opérations rationnelles sur les automates}

\subsubsection{Union}

Soit $\AR_1=<A,Q_1,D_1,T_1,\tau_1>$ et $\AR_1=<A,Q_2,D_2,T_2,\tau_2>$ deux
automates  finis reconnaissant  deux langages  $L_1$ et  $L_2$.  On peut
supposer  que $Q_1\cap  Q_2=\emptyset$  quitte à  renuméroter les  états
(en effet les noms des  états n'ont aucune importance). Alors on définit
un nouvel automate $$\AR_1|\AR_2=<A,Q_1\cup Q_2,D_1\cup D_2,T_1\cup
T_2,\tau_1\cup \tau_2>$$

en notant abusivement $\tau_1\cup\tau_2$ la relation de graphe $\GR_{\tau_1}\cup\GR_{\tau_2}$.

\begin{theoreme}
  L'automate $\AR_1|\AR_2$ reconnaît le langage $L_1|L_2$.
\end{theoreme}


En général, il est ensuite nécessaire de rendre cet automate standard et
émondé.

\subsubsection{Produit}

Soit $\AR_1=<A,Q_1,D_1,T_1,\tau_1>$ et $\AR_2=<A,Q_2,D_2,T_2,\tau_2>$ deux
automates finis reconnaissant deux langages $L_1$ et $L_2$.  On peut
supposer que $Q_1\cap Q_2=\emptyset$.  Quitte à standardiser $\AR_2$, on
peut supposer que $D_2=\bigl\{d_2\bigr\}$.

On définit alors un nouvel automate:

$$\AR_1\cdot\AR_2=<A,(Q_1\cup                               Q_2)\setminus
\left\{d_2\right\},D_1,T',\tau_1\cup \tau'_2\cup\tau''_2>$$ avec:

\begin{itemize}
\item $T'=(T_1\cup T_2)\setminus \{d_2\}$ si $d_2\in T_2$ et $T_1\cup T_2$
  sinon;
\item    $\GR_{\tau_2'}=\bigl\{(q,a,q')    \in    GR_{\tau_2}\mid    q\neq
  d_2\bigr\}$ ;
\item $\GR_{\tau_2''}=\bigl\{(q_{t_1},a,q')\mid q_{t_1}\in T_1, (d_2,a,q')\in\GR_{\tau_2}\bigr\}$.
\end{itemize}


\begin{recherche}
Comment décrire concrètement la construction de $\AR_1\cdot\AR_2$?
\end{recherche}

\begin{theoreme}
  L'automate $\AR_1\cdot\AR_2$ reconnaît le langage $L_1\cdot L_2$.
\end{theoreme}

\subsubsection{Étoile}

Soit   $\AR=<A,Q,\{d\},T,\tau>$  un   automate   fini  \textit{standard}
reconnaissant un langage L.

On définit alors un nouvel automate $$\AR^\star=<A,Q,\{d\},T\cup\{d\},\tau'>$$

avec $\GR_{\tau'}=\GR_\tau\cup \bigl\{(q_t,a,q)\mid q_t\in T,(d,a,q)\in \GR_\tau\bigr\}$



\begin{recherche}
Comment décrire concrètement la construction de $\AR^\star$?
\end{recherche}



\begin{theoreme}
  L'automate $\AR^\star$ reconnaît le langage $L^\star$.
\end{theoreme}

\subsection{Théorème de \textsc{Kleene}}

Nous pouvons  déduire de ce qui  précède que tout  langage rationnel est
reconnaissable par un automate.

En  fait,  la  réciproque  est  vraie  aussi  mais  assez  compliquée  à
démontrer.   Ces    deux   résultats   constituent    le   théorème   de
\textsc{Kleene}:

\begin{theoreme}[Théorème de \textsc{Kleene} (1956)]
Pour tout alphabet A, ${Rat(A^\star)=Rec(A^\star)}$.
\end{theoreme}

Ainsi, si  un langage peut  être décrit par une  expression rationnelle,
alors il existe un automate fini qui le reconnaît.

Réciproquement, si  un langage est  reconnaissable, alors il  existe une
expression rationnelle qui le décrit.

Notez bien que certains langages  ne sont pas reconnaissables, comme par
exemple  l'ensemble  des  chaînes  sur  $\bigl\{A,B\bigr\}$  constituées
d'autant de $a$ que de $b$.  En raisonnant par l'absurde, n peut montrer
qu'aucun automate \textit{fini} ne peut reconnaître ce langage.

\subsection{Automate  associé à  un  langage défini  par une  expression  rationnelle}

\subsubsection{Méthode \og manuelle\fg{}}

Une  expression rationnelle  correspond à  une construction  récursive à
partir   d'opérations   simples  sur   des   langages   réduits  à   des
singletons  et  les constructions  précédentes  vont  nous permettre  de
construire petit à petit un automate fini correspondant.


\subsubsection{Algorithme de \textsc{Gloushkov}}

La méthode  suivante est  attribuée à l'informaticien  soviétique Viktor
\textsc{Gloushkov}  qui l'a proposée  en 1961.  Il construit  un automate
ayant un  état de plus que  le nombre de symboles  qui apparaissent dans
l'expression rationnelle.

On \textit{linéarise}  l'expression rationnelle, i.e.,  on remplace tous
les caractères par des symboles distincts, numérotés à partir de 1 de la
gauche vers la droite.

Par exemple, $ab^\star|a^2b^+$ devient $x_1x_2^\star|x_3x_4x_5^+$.

On  crée  ensuite  un état  par  variable  ainsi  qu'un état  $q_0$  qui
représente l'état initial.

On  crée l'ensemble  posliedny (dernier  en  russe) qui  contient tous  les
caractères pouvant terminer une chaîne plus éventuellement l'état $q_0$
si $\vide$ appartient  au langage : il constitue  l'ensemble des états
terminaux de l'automate.

On  crée l'ensemble  piervy (premier  en russe)  des  caractères pouvant
commencer un mot:  on relie l'état $q_0$ à chaque  $q_i$ de cet ensemble
en l'étiquetant par $x_i$.

On crée une  transition étiquetée par $x_j$ de  l'état $q_i$ vers l'état
$q_j$ si le facteur $x_ix_j$ peut apparaître dans au moins une chaîne du
langage.


Finalement,   on  remplace   les   $x_i$  par   les  caractères   qu'ils
remplaçaient. 

Il ne reste plus qu'à s'occuper d'une vingtaine d'exemples...

\subsection{Automates séquentiels}

Pour  modéliser  de  nouvelles  situations,  il  faut  sortir  du  cadre
restreint des  automates à états  finis sans sortie. Voici  une première
catégorie qui diffère peu de la  précédente, à un petit détail près: ils
produisent des chaînes de sortie.

\begin{definition}
Un automate à états finis  avec sorties est caractérisé par un sextuplet
$<Q,q_0,A_I,A_S,f_t,f_s>$ où:
\begin{itemize}
\item $Q$ est un ensemble fini d'états;
\item $q_0$ est l'état initial;
\item $A_I$ est l'alphabet d'entrée;
\item $A_S$ est l'alphabet de sortie;
\item $f_t$ est la fonction de transition de $Q\times A_I$ vers $Q$;
\item $f_s$ est la fonction de sortie de $Q\times A_I$ vers $A_S$.
\end{itemize}
\end{definition}


Vous aurez bien noté que  l'automate ne contient qu'un seul état initial
et que les fonctions de transition et de sortie sont des...fonctions, if
you see what I mean...

\begin{remarque}
  On  peut  également définir  un  automate  séquentiel  avec des  états
  terminaux: une chaîne ne sera produite que si l'on atteint un état terminal.
\end{remarque}



Pour  représenter  l'automate  par  un diagramme,  on  étiquette  chaque
transition  par  un caractère  d'entrée  suivi  du  caractère de  sortie
correspondant.



\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=3.2cm,semithick, bend angle=20]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 3em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)  {$q_0$};
 \node[state] (B) [ right of=A] {$q_1$};
\node[state] (D) [ above right of=B] {$q_3$};
 \node[state] (C) [ below right of=D] {$q_2$};
 
 
 \path (A) edge [loop above] node {b|0}
       (A) edge [bend left] node {a|1} (B)
       (B) edge [bend left] node {b|1} (A)
       (B) edge [bend left] node {a|1} (C)
       (C) edge [bend left] node {b|0} (B)
       (D) edge [loop above] node {b|1} (D)
       (D) edge node[above left] {a|0} (B)
       (C) edge node[above right] {a|0} (D);
\end{tikzpicture}
\end{center}

Par exemple, la chaîne d'entrée babaaaaaabbba donne en sortie 0111100101110.

\subsection{Automates à pile}


On a  déjà évoqué le cas du  langage $\bigl\{0^n1^n\mid n\in\bbn\bigr\}$
qui  ne  peut  être reconnu  par  aucun  automate  fini. Il  existe  des
automates plus généraux qui reconnaissent ce genre de langages.



Pour d\'{e}finir un automate \`{a} pile nous avons besoin :

\begin{enumerate}
\item d'un alphabet $A=\left\{ ..,\alpha_{z},...\right\} ,$ rappelons que $%
A $ est forc\'{e}ment fini et non vide ; c'est sur cet alphabet que nous
allons construire des mots ;

\item de savoir ce qu'est une pile, bien que cette pile soit rechargeable,
elle ne peut en aucun cas \^{e}tre utilis\'{e}e pour remplacer la pile de
votre calculatrice le jour d'un examen. Pour simplifier une pile est une
liste ordonn\'{e}e d'\'{e}l\'{e}ments - cette liste peut \^{e}tre vide - sur
laquelle deux op\'{e}rations \'{e}l\'{e}mentaires peuvent \^{e}tre r\'{e}alis%
\'{e}es :

\begin{itemize}
\item insertion d'un \'{e}l\'{e}ment au sommet de la pile (empiler)

\item suppression de l'\'{e}l\'{e}ment au sommet de la pile (d\'{e}piler)%




il est alors clair que le premier \'{e}l\'{e}ment empil\'{e} sera le dernier 
\`{a}  \^{e}tre d\'{e}pil\'{e}  ; C'est  pourquoi \og  pile\fg{}  est un
synonyme de FILO (First In Last Out) ou de LIFO (Last In First Out).
\end{itemize}

\item d'un alphabet de pile $P=\left\{ p_{1},p_{2},p_{3},...\right\} ,$
c'est tout simplement un ensemble fini de symboles sp\'{e}cifiques \`{a} la
pile ; la pile va nous servir \`{a} m\'{e}moriser des \'{e}tapes et, pour
savoir o\`{u} on en est ou ce qui a \'{e}t\'{e} fait avant, on va
regarder l'\'{e}tat de la pile pour continuer ;

\item d'un ensemble d'\'{e}tats $E=\left\{ e_{1},e_{2},...\right\} ,$ $s\in
E $ est l'unique \'{e}tat initial de l'automate ; on note $T$ la partie de $%
E $ constitu\'{e}e des \'{e}tats terminaux, on dit aussi acceptants ;

\item $\mu $ est la relation de transition, c'est une relation: 
\[
\left( E\times \left( P\cup \left\{ \vide \right\} \right)
\right) \times \left( A\cup \left\{ \vide \right\} \right) \longrightarrow E\times \left( P\cup \left\{ \vide \right\} \right) 
\]%
une transition est alors assimil\'{e}e \`{a} un triplet (comme pour les
automates \`{a} \'{e}tats finis). Si $\left( e_{k},p_{h}\right) $ est une
image de $\left( \left( e_{i},p_{j}\right) ,\alpha _{z}\right) $ par $\mu $
on note%
\[
\left( \left( e_{i},p_{j}\right) ,\alpha _{z},\left( e_{k},p_{h}\right)
\right) 
\]%
qui se lit : \og si l'automate est dans l'\'{e}tat $e_{i}$ et que le sommet de
la pile est $p_{j}$ et que l'automate lit $\alpha _{z}$ alors l'automate
passe dans l'\'{e}tat $e_{k},$ d\'{e}pile $p_{j}$ de la pile et empile $%
p_{h}$\fg{}. Si $p_{j}=\vide $ on ne s'occupe pas de savoir ce qu'il y a
au sommet de la pile et on ne d\'{e}pile rien, si $p_{h}=\vide $ cela
indique que l'on n'empile rien. La possibilit\'{e} de pouvoir avoir $\alpha
_{z}=\vide $ nous permet, en cas de besoin, de modifier l'\'{e}tat de
l'automate et du sommet de pile.
\end{enumerate}



On le remarque imm\'{e}diatement, un \'{e}tat d'un automate 
\`{a} pile n'est jamais isol\'{e} dans une transition, il doit \^{e}tre
associ\'{e} \`{a} un symbole de pile (ou $\vide )$, les \'{e}tats de
notre automate sont alors des couples.




Comme pour les automates \`{a} \'{e}tats finis, $\alpha _{z}$ est l'\'{e}%
tiquette de la transition:


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=3.2cm,semithick, bend angle=20]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 3em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state] (A)  {$e_i$};
 \node[state] (B) [ right of=A] {$e_j$};
 
 
 \path (A) edge  node {$p_j,\alpha_z,p_h$} (B);
\end{tikzpicture}
\end{center}




On g\'{e}n\'{e}ralise cette d\'{e}finition en autorisant dans les
transitions l'empilement d'une cha\^{\i}ne de plusieurs symboles de la pile :%
\[
\left( \left( e_{i},p_{j}\right) ,\alpha _{z},\left( e_{k},M\right) \right) 
\]%
ici on va empiler tous les symboles de $M$ qui est un mot sur $P$ l'alphabet
de pile.

On peut, au lieu de pr\'{e}senter les transitions sous la forme $\left(
\left( e_{i},p_{j}\right) ,\alpha _{z},\left( e_{k},p_{h}\right) \right) ,$
utliser lorsque $\mu $ est une fonction%
\[
\mu \left( e_{i},p_{j},\alpha _{z}\right) \text{ ou }\mu \left( \left(
e_{i},p_{j}\right) ,\alpha _{z}\right) =\left( e_{k},p_{h}\right) 
\]%
qui se lit \'{e}videmment encore : si l'automate est dans l'\'{e}tat $e_{i}$
et qu'il y a $p_{j}$ en sommet de pile (si $p_{j}=\vide $ on ne
s'occupe pas du sommet de pile et on ne d\'{e}pilera rien) et que l'automate
lit $\alpha _{z}$ alors il passe dans l'\'{e}tat $e_{k},$ on d\'{e}pile $%
p_{j}$ et on empile $p_{h}$.

On dit qu'un mot $m$ de $A^{\ast }$ est reconnu par l'automate s'il existe
une suite de transitions partant de l'\textbf{\'{e}tat initial} et \textbf{%
pile vide} dont la suite des \'{e}tiquettes est $m$ et aboutissant \`{a} un 
\textbf{\'{e}tat final }ou acceptant et \textbf{pile vide}. L'ensemble des
mots reconnus par l'automate \`{a} pile est le langage engendr\'{e} ou
reconnu par cet automate.

\vspace{0.5cm}

Consid\'{e}rons l'automate d\'{e}fini par 
\[
A=\left\{ a,b\right\} ,E=\left\{ s,1,2\right\} ,T=\left\{ 2\right\}
,P=\left\{ u\right\} 
\]%
et les transitions%
\begin{eqnarray*}
T_{1} &:&\left( \left( s,\vide \right) ,a,\left( 1,u\right) \right) \\
T_{2} &:&\left( \left( 1,\vide \right) ,a,\left( 1,u\right) \right) \\
T_{3} &:&\left( \left( 1,u\right) ,b,\left( 2,\vide \right) \right) \\
T_{4} &:&\left( \left( 2,u\right) ,b,\left( 2,\vide \right) \right)
\end{eqnarray*}

$T_{1}:$ pour d\'{e}marrer, l'automate doit \^{e}tre dans l'\'{e}tat
initial $s$ (c'est le seul \'{e}tat initial) et la pile doit \^{e}tre vide,
si c'est le cas et qu'il lit $a$ alors il passe dans l'\'{e}tat 1, on ne d%
\'{e}pile rien ($\vide $) et on empile $u.$

$T_{2}:$ si l'automate est dans l'\'{e}tat 1 et qu'il lit $a$ alors il reste
dans l'\'{e}tat 1, on ne d\'{e}pile rien ($\vide )$ et on empile $u.$

$T_{3}$ : si l'automate est dans l'\'{e}tat 1 et que le sommet de la pile
est $u$ et qu'il lit $b$ alors il passe dans l'\'{e}tat 2, on d\'{e}pile $u$
(le sommet de la pile) et on n'empile rien ($\vide ).$

$T_{4}:$ si l'automate est dans l'\'{e}tat 2 et que le sommet de la pile est 
$u$ et qu'il lit $b$ alors il passe (il reste) dans l'\'{e}tat 2, on d\'{e}%
pile $u$ (le sommet de la pile) et on n'empile rien ($\vide ).$

Vous aurez remarqu\'{e} que la relation $\mu $ est une fonction, on dit dans
ce cas que l'automate \`{a} pile est d\'{e}terministe.

L'\'{e}tat de sortie de l'automate est ici l'\'{e}tat 2 ($T=\left\{
2\right\} $) mais on ne peut utiliser cette sortie qu'au moment o\`{u} la
pile est vide.




\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=3.2cm,semithick, bend angle=20]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 3em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)  {$s$};
 \node[state] (B) [ right of=A] {$1$};
\node[state,accepting] (C) [ right of=B] {$2$};
 
 
 \path (A) edge node {$\vide,a,u$} (B)
       (B) edge[loop above] node {$\vide,a,u$} (B)
       (B) edge node {$u,b,\vide$} (C)
       (C) edge[loop above] node {$u,b,\vide$} (C);
\end{tikzpicture}
\end{center}



On remarque assez facilement qu'\`{a} chaque fois que l'automate lit un $a,$
on empile un $u,$ il y aura alors dans la pile autant de $u$ que de $a$ lus
; \`{a} chaque fois que l'automate lit un $b$ on d\'{e}pile un $u$ (si ce
n'est pas possible, l'automate ne peut lire $b),$ en cons\'{e}quence
l'automate sera dans l'\'{e}tat 2 avec la pile vide lorsqu'il aura lu autant
de $b$ que de $a.$ Le langage reconnu par cet automate est $\left\{
a^{n}b^{n}\mid n\in \mathbb{N}^{\ast }\right\} ,$ la pile nous permet de m%
\'{e}moriser le nombre de $a$ lus ce que ne permet pas un automate \`{a} 
\'{e}tats finis.

Si nous d\'{e}cidons que $s$ est aussi un \'{e}tat final et comme au d\'{e}%
part la pile est vide, on conclut, comme pour les automates \`{a} \'{e}tats
finis, que $\vide $ fait partie du langage reconnu par l'automate.

Si on veut que la pile soit vide \`{a} un certain \'{e}tat $e_{i}$, pour
vider la pile il suffit de rajouter les transition $\left( \left(
e_{i},p\right) ,\vide ,\left( e_{i},\vide \right) \right) $
avec $p$ un symbole de pile quelconque.












\subsection{Machines de \textsc{Turing}: le retour}

On peut  montrer qu'un  automate à pile  ne peut reconnaître  le langage
$\bigl\{0^n1^n2^n\mid n\in\bbn\bigr\}$:  il faut imaginer  quelque chose
de plus puissant comme...les  machines de \textsc{Turing}. La boucle est
bouclé,  les machines  de  \textsc{Turing} sont  l'alpha  et l'oméga  de
l'informatique théorique...

%\section{Grammaires}

\vfill 
\eject




\section{Grammaires}



\subsection{Syntaxe et sémantique}

Pour commencer dans la joie, chantons gaiement:

\bigskip



\begin{minipage}[t]{0.5\linewidth}
  \begin{quote}
{\itshape \large Mon père est marinier\\
Dans cette péniche\\
Ma mère dit : « La paix niche\\
Dans ce mari niais »\\
Ma mère est habile\\
Mais ma bile est amère\\
Car mon père et ses verres\\
Ont les pieds fragiles}
\end{quote}
\end{minipage}\hspace{1.23cm}
\begin{minipage}[t]{0.45\linewidth}\vspace{-1cm}
  \hspace{7cm} 
  \begin{flushright}
%\begin{figure}
\begin{center}
  \includegraphics[width=1.2\linewidth]{boby}
\end{center}
%\end{figure}
  \end{flushright}
\end{minipage}



\begin{flushright}
Boby \textsc{Lapointe} (1969)
\end{flushright}



Boby \textsc{Lapointe},  ingénieur de Sup'Aero et chanteur  à succès des
années 1960, a  su jouer entre syntaxe et sémantique  comme dans la célèbre
chanson
\href{http://www.musicme.com/Boby-Lapointe/titres/Mon-Pere-Et-Ses-Verres-t132012.html?play=0602498378908-02_21#}{mon
  père et ses verres}. 

L'ambiguïté  n'est ici  qu'orale. Elle  peut être  aussi écrite:  \og le
vendredi matin, l'étudiant sent la rose\fg{}.

D'autres, selon  le contexte,  peuvent être non  ambiguës: \og  Tous les
matins, je mange un avocat\fg{}.


Il y a d'autres phrases non ambiguës mais au sens douteux: \og Tous les
avocats, je mange la Pologne\fg{}. 


Encore un type d'ambiguïté:  \og Je regarde cette jolie fille qui se promène avec des jumelles\fg{}.

Cependant, toutes ces phrases sont correctes \textit{syntaxiquement}.

Ces problèmes  peuvent être  également informatiques. Sur  Python, la
\og phrase \fg{} \verb|3 + 1.2| est correcte syntaxiquement:

\begin{lstlisting}[caption={}]
>>> 3 + 1.2
4.2
\end{lstlisting}

mais pas sur CAML:

\caml

\begin{lstlisting}[caption={}]
# 3 + 1.2 ;;
"Error: This expression has type float but an expression was expected of type int"
# 3. +. 1.2 ;;
- : float = 4.2
# 3 + 1 ;;
- : int = 4
\end{lstlisting}



Le dictionnaire propose les définitions suivantes: 

\begin{itemize}
\item \textbf{syntaxe}:
n.  f. (bas  latin  syntaxis, du  grec  suntaksis, ordre)  Partie de  la
grammaire qui décrit les  règles par lesquelles les unités linguistiques
se combinent en phrases. 

\item \textbf{sémantique}:
n. f. (bas latin semanticus, du grec sêmantikos, qui signifie)
\textbf{1.} Étude du sens des unités linguistiques et de leurs combinaisons.
\textbf{2.} Étude  des propositions d'une théorie déductive  du point de
vue de leur vérité ou de leur fausseté. 

\end{itemize}
  



Nous allons dans cette section survoler un moyen d'analyser syntaxiquement des \og
phrases\fg{} qui pourront être de toute nature.




\subsection{Grammaires algébriques (ou hors contexte)}

\subsubsection{Définitions}

\begin{definition}
Une grammaire algébrique est définie par la donnée de:

\begin{itemize}
\item $\Sigma$: un ensemble fini de \textit{symboles terminaux};
\item $V$: un ensemble fini de \textit{variables} (symboles non terminaux);
\item $S\in V$:  une variable particulière appelée axiome  (pensez à \og
  Start\fg{});
\item  P: un  ensemble  fini  de \textit{règles  de  production} (ou  de
  réécriture) qui  sont de  la forme $A  \to w$  avec $A\in V$  et $w\in
  (\Sigma \cup V)^\star$.
\end{itemize}

\end{definition}

Dans la  suite du cours, on  désignera par une  majuscule les variables,
par une minuscule  du début de l'alphabet romain  les symboles terminaux, par  une minuscule de  la fin de  l'alphabet des chaînes  de $(\Sigma
\cup V)^\star$, par une minuscule grecque les chaînes de $\Sigma^\star$.


\begin{definition}
Une chaîne $\mu$ \textit{dérive}  d'une chaîne $\nu$, si, à partir
de $\nu$, on peut arriver à  $\mu$ par un nombre fini d'applications des
règles de G. 

On note  $\nu \Rightarrow \mu$  ou on peut  même préciser le  nombre $n$
d'applications avec $\nu \overset{n}{\Rightarrow} \mu$

\medskip

Le  \textit{langage engendré}  par  une grammaire  G  est l'ensemble  de
toutes les  chaînes terminales  (appartenant donc à  $\Sigma^\star$) qui
dérivent de l'axiome S. On le note $\LR(G)$.
\end{definition}

\begin{definition}


Une \textit{dérivation à gauche} est  une dérivation qui s'applique à la
première variable rencontrée dans la chaîne (à gauche, donc...)

\end{definition}


\subsubsection{Arbre de dérivation}

Pour toute règle de la forme $X\to ABCD...$, on construit un arbre de ne
n\oe ud X et de feuilles A, B, C, D,...

Pour toute règle du type $X\to A|B|C|...$, on construit un des arbres de
n\oe ud X et n'ayant qu'une seule feuille, celle-ci étant A ou B ou C ou...


On applique récursivement cette  règle tant que les feuilles provisoires
sont des symboles non terminaux.

\begin{definition}
  Une grammaire est  ambiguë si pour au moins une  chaîne du langage, il
  existe au moins deux arbres de dérivation.
\end{definition}


\subsection{Grammaire régulière}

\begin{definition}
Une grammaire algébrique est  \textit{régulière} si ses règles sont d'un
des types suivant:

\begin{itemize}
\item $A\to aB$;
\item $A\to a$;
\item $A\to \vide$, avec $A,\,B\in V$ et $a\in\Sigma$.
\end{itemize}

\end{definition}


Dans  chaque chaîne dérivant  de l'axiome,  il n'y  a donc  qu'une seule
chaîne qui  est en suffixe. Les  arbres de dérivation  associés sont des
peignes.

On admettra le théorème suivant:


\begin{theoreme}
Si G est une grammaire régulière, alors $\LR(G)$ est régulier.

Tout langage régulier \textbf{peut} être engendré par une grammaire régulière.
\end{theoreme}


\subsection{Lemme de la pompe}

%\begin{figure}
\begin{center}
  \includegraphics[height=6cm]{shadock_pompe}
\end{center}
%\end{figure}



Remarquons tout  d'abord que  si une chaîne  a une  longueur strictement
supérieure au nombre de variables de la grammaire, alors il y a au moins
une variable qui figure deux fois dans l'arbre de dérivation.


\begin{theoreme}
  Soit  L un langage  régulier. Il  existe une  constante $k$  telle que
  toute chaîne $\mu$ de L  dont la longueur est strictement supérieure à
  $k$  peut s'écrire  sous la  forme  $\mu=\nu \xi\rho$  avec $\xi$  une
  chaîne non vide,  la longueur de $\nu\xi$ étant  inférieure ou égale à
  $k$ et la chaîne $\nu\xi^n\rho$ appartient à L pour tout entier $n$.
\end{theoreme}


\subsection{Analyse syntaxique (\og parsing\fg{})}


Étant  donné une  grammaire  algébrique  G, on  voudrait  savoir si  une
chaîne $\mu\in \Sigma^\star$ appartient à $\LR(G)$.


\begin{definition}
Le \textit{préfixe terminal} d'une chaîne $u$ de $(\Sigma \cup V)^\star$
est  la sous-chaîne  des symboles  terminaux qui  précèdent  la première
variable de $u$.
\end{definition}


Lors des dérivations successives, le préfixe terminal est soit inchangé,
soit prolongé.
Ainsi, si  le préfixe terminal d'une  chaîne $u$ n'est  pas identique au
début de la chaîne $\mu$ à  analyser, alors $\mu$ ne peut pas dériver de
$u$.

\subsubsection{Analyse syntaxique descendante en largeur}


On utilise une file (premier entré, premier sortie: FIFO).

\begin{algo}
\PROC{largeur}{
\pfarg{G}{grammaire};
\pfarg{$\mu$}{chaîne à analyser}
}
\VAR
\DECLVAR[file]{Q}{liste}
\DECLVAR{c}{chaîne}
\ENDVAR
\BEGIN
\STATE{Q \recoit [S]}
\STATE{c\recoit{} S}
\WHILE{ $c\neq\mu$ ou $Q\neq\emptyset$}
\STATE{Défiler Q}
\STATE{Appliquer successivement chacune des règles possibles à la
  première variable de $c$ }
\FORGEN{chaque chaîne obtenue}
\IF{le  préfixe terminal  de la  chaîne est  un préfixe  de $\mu$  et la
  chaîne est non terminale }
\STATE{l'enfiler dans Q}
\ELSEIF{La chaîne est égale à $\mu$}
\STATE{C'est fini}
\ENDIF
\STATE{$c$ \recoit{} la tête de Q}
\ENDFOR
\ENDWHILE
\RETURN{Ce n'est pas un mot du langage}
\END
\end{algo}





\subsubsection{Analyse syntaxique descendante en profondeur}


On utilise cette fois une pile.


\subsubsection{Analyse ascendante}

On part  de la chaîne et  on essaie de  remonter à S: on  s'occupe cette
fois des suffixes.


\begin{remarque}
Dans tous les  cas, des grammaires mal formées  peuvent rendre l'analyse
syntaxique inopérante.  Cependant, on peut réécrire  les grammaires pour
les rendre valables.
\end{remarque}


\section{Correspondance automate fini / grammaire régulière}


On  s'arrange pour que  la grammaire  régulière ait  des règles  du type
$A\to aB$ ou $A\to \vide$.

À chaque variable de la grammaire on associe un état de l'automate.

L'axiome est l'unique état initial.


Les règles $A\to aB$ donnent les transitions $A\overset{a}{\to}B$.

Une règle $A\to \vide$ donne un état terminal.















%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\modeexercice % entre en mode exercice
\section{EXERCICES}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\small
\begin{listeexercices}







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Langages}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\begin{exercice}
$A$\ est un alphabet :

\begin{enumerate}
\item Qu'est-ce qu'une chaîne sur $A$?

\item Que d\'{e}signe $A^{\star }$?

\item Qu'est-ce qu'un langage sur $A$?

\item $A$\ est-il un langage sur $A$?

\item $A^{\star }$\ est-il un langage sur $A$?

\item Toute partie de $A$\ est-elle un langage sur $A$?

\item Qu'est-ce qu'un langage de $A^{\star }$?

\item $\varnothing $\ est-il un langage sur $A$?

\item $\left\{ \vide\right\} $\ est-il un langage sur $A$?

% \item Qu'appelle-t-on op\'{e}rations rationnelles sur les langages de $%
% A^{\star }$?
\end{enumerate}
\end{exercice}





\begin{exercice}
$A=\left\{ a,b,c,d,e\right\} $ est un alphabet.

\item Expliciter les langages :

\begin{enumerate}
\item $L_{1}=\left\{ \mu\in A^{\star }\mid \left\vert \mu\right\vert
_{c}=0\right\} $

\item $L_{2}=\left\{ \mu\in A^{\star }\mid \mu=a\xi e\text{ avec }\xi\in L_{1}\right\} 
$

\item $L_{3}=\left\{ a,bc\right\} \cdot\left\{ ad\right\} $

\item $L_{4}=\left( \left\{ a,bc\right\} \cdot\left\{ ad\right\} \right) |\left(
\left\{ a,b,e\right\} \cdot\left\{ cd,be\right\} \right) $

\item $L_{5}=L_{4}^{0}$

\item $L_{6}=L_{3}^{2}$

\item $L_{7}=\left\{ a^{n}b^{p}\mid \left( n,p\right) \in \mathbb{N}^{\ast
}\times \mathbb{N}\right\} $

\item $\left\{ a\right\} ^{+}$

\item $\left\{ e,d\right\} ^{\star }$

\item $\left\{ e\cdot d \right\} ^{\star }=\left\{ ed\right\} ^{\star }$
\end{enumerate}

\end{exercice}



\begin{exercice}
  Soit un alphabet $A=\bigl\{a_1,a_2,...,a_n\bigr\}$ avec $n\in\bbn^\star{}$.

On rappelle qu'un ensemble E est un sous-monoïde de $A^\star$ si:
\begin{itemize} 
\item $E \subseteq A$;
\item E est \textit{stable} par concaténation, c'est-à-dire que la concaténation de deux éléments de E est encore dans E.
\end{itemize}

Ce sous-monoide est dit \textit{libre} s'il contient la chaîne vide $\vide_A$.

Les ensembles suivants sont-ils des sous-monoïdes de $A^\star$? Si oui, sont-ils libres? (En d'autres termes, sont-ce des langages?...) 

\begin{enumerate}
\item L'ensemble $E_1$ des chaînes de A de longueur paire.
\item  L'ensemble $E_2$ des chaînes de A de longueur impaire.
\item $E_3=\bigl\{(a_1a_2)^p, p\in\bbn\bigr\}$.
\item $E_4=\bigl\{a_1^pa_2^p, p\in\bbn\bigr\}$.
\item L'ensemble $E_5$ des mots où le nombre d'occurrences de $a_1$ est égal au nombre d'occurrences de $a_2$. 
\end{enumerate}

\end{exercice}


\begin{exercice}
  
$L=\left\{ a,ab,abab\right\} $ est un langage sur $A=\left\{ a,b,c\right\} $

\begin{enumerate}
\item Expliciter $L^{2}$.


\item D\'{e}crire en fran\c{c}ais le langage $L^{\star }.$
\end{enumerate}

\end{exercice}











\begin{exercice}
$A$ est un alphabet, $L$ est un langage sur $A$ et $\mu$ est une chaîne de $%
A^{\star }$. On appelle \textit{r\'{e}siduel} de $L$ par rapport \`{a} $\mu$ le langage%
\[
\mu^{-1}L=\left\{ \xi\in A^{\star }\mid \mu\cdot\xi\in L\right\} 
\]


\begin{enumerate}

\item Vérifier que $\mu^{-1}L$ est bien un langage.

\item D\'{e}montrer que $\vide\in \mu^{-1}L\Leftrightarrow \mu\in L.$

\item D\'{e}terminer $\vide^{-1}L.$

\item D\'{e}montrer que $\nu^{-1}\left( \mu^{-1}L\right) =\left( \mu\nu\right)
^{-1}L $

\item Si $L=\left\{ ab^{k}\mid k\in \mathbb{N}^{\ast }\right\} ,$ d\'{e}%
terminer $a^{-1}L.$

\item Si $L=\left\{ b^{k}a\mid k\in \mathbb{N}^{\ast }\right\} ,$ d\'{e}%
terminer $a^{-1}L.$
\end{enumerate}
\end{exercice}




\begin{exercice}
On travaille avec l'alphabet $A=\left\{ 0,1\right\} $\ et $L$\ est le
langage sur $A$\ form\'{e} des \'{e}critures normalis\'{e}es des entiers
naturels \'{e}crits en base 2, i.e. que $0$\ s'\'{e}crit avec $0$\ et si $%
n\neq 0,$\ son \'{e}criture en base 2 commence par un 1 ; on interdit les 
\'{e}critures du type 0000001010111. Exprimer $L$\ \`{a} l'aide de langages
de $A^{\ast }$\ et d'op\'{e}rations rationnelles.
\end{exercice}




\begin{exercice}
$A=\left\{    a,b,c,d\right\}    $     et  
$L=\left\{a^{n}cb^{p}\mid\left(n,p\right)\in\mathbb{N}^{2}\right\}$. 
Exprimer $L$
 \`{a} l'aide de parties de $A$\ et d'op\'{e}rations rationnelles.
\end{exercice}

\begin{exercice}
$A=\left\{ a,b,c,d\right\}  $ et $L_{1}$ est l'ensemble  des chaînes qui
s'\'{e}crivent uniquement avec des $a$ ou/et des $c$. Exprimer $L_{1}$ \`{a}
l'aide de parties de $A$ et d'op\'{e}rations rationnelles.
\end{exercice}

\begin{exercice}
$A=\left\{  a,b,c,d\right\} $  et $L_{2}$  est l'ensemble  des  chaînes qui
s'\'{e}crivent uniquement avec des $a$  ou/et des $c$ et qui contiennent
une seule fois  la lettre $b$. Exprimer $L_{2}$  \`{a} l'aide de parties
de $A$ et d'op\'{e}rations rationnelles.
\end{exercice}


\begin{exercice}
Soient $a$ et $b$ deux symboles d'un alphabet $A$ et $\mu\in A^\star$.

Montrer par récurrence (sur ?) que si $\mu a= b\mu$ alors $a=b$ et $\mu\in \bigl\{a\bigr\}^\star$. 
\end{exercice}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Langages et expressions rationnels}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exercice}\label{exo::regexp1}
  Expliciter les langages associ\'{e}s aux expressions rationnelles suivantes:
\begin{enumerate}
\item $a\left( a|b\right) ^{\star }a$

\item $\left( aa|bb\right) ^{\star }\left( ab|ba\right) \left( aa|bb\right)
^{\star }$

\item $a^{\star }ba^{\star }ba^{\star }ba^{\star }$

\item $\left( abc\right) ^{\star }$

\item $\left( abc^{\star }\right) ^{\star }$
\end{enumerate}

\end{exercice}



\begin{exercice}[Vrai ou faux?]
\begin{enumerate}
\item $\left( a^{\star }\right) ^{\star }=a^{\star }$

\item $aa^{\star }=a^{\star }a$

\item $aa^{\star }|\vide=a^{\star }$

\item $a\left( b|c\right) =ab|ac$

\item $\left( a|b\right) ^{\star }=\left( a^{\star }|b^{\star }\right) ^{\star }$

\item $a\left( ba\right) ^{\star }=\left( ab\right) ^{\star }a$

\item $\left( a|b\right) ^{\star }=\left( a^{\star }b^{\star }\right) ^{\star }$

\item $\left( a|b\right) ^{\star }=a^{\star }\left( ba^{\star }\right) ^{\star }$

\item $\left( \left( a|b\right) ^{\star }|c\right) ^{\star }=\left(
a|b|c\right) ^{\star }$
\end{enumerate}

\end{exercice}


\begin{exercice}\label{exo::sans}
  Déterminez  des expressions  régulières correspondant  aux définitions
  suivantes:
  \begin{enumerate}
  \item les  chaînes formées de caractères de  l'alphabet non accentués,
    où  les  caractères  sont  dans l'ordre  alphabétique  croissant  et
    inférieurs à $f$;
\item les chaînes de bits sans  \og $0$\fg{};
\item les chaînes de bits sans  \og $01$\fg{};
\item les chaînes de bits sans \og $010$\fg{};
\item  les commentaires dans  un langage  de programmation  formés d'une
  chaîne encadrée par \og \verb+[#+\fg{} et \og \verb+#]+\fg{}, sans \og
  \verb+#]+\fg{} à l'intérieur si ce n'est à l'intérieur d'une chaîne en
  étant encadré par \og "\fg{} et \og "\fg{};
\item les chaînes de bits constituées d'un nombre pair de 1.
  \end{enumerate}
\end{exercice}




\begin{exercice}[Expressions rationnelles et \texttt{grep}]
  Nous allons  étudier quelques aspects de  l'utilitaire \verb+grep+ des
  systèmes UNIX  en rapport avec la notion  d'expression rationnelle vue
  en cours.

Nous  utiliserons les  opérateurs  \og\verb+*+\fg{} et  \og \verb+\|+\fg{}  qui
correspondent à l'étoile de \textsc{Kleene} et à la réunion des chaînes.

Il  existe  également  l'opérateur  \og  \verb|\+|\fg{}  qui  correspond  à  la
concaténation  de la  chaîne avec  son étoile  (\verb|a\+|  correspond à
$a\cdot a^\star=a^+$).

Les   parenthèses    seront   précédées   d'une    contre-oblique:   \og
\verb+\(+\fg{} et \og \verb+\)+\fg{}.

Nous travaillerons  sur un fichier \verb+.txt+ contenant  une chaîne par
ligne.
Pour  signifier   à  \verb+grep+   que  nous  recherchons   des  chaînes
correspondant  en  totalité  à  l'expression  rationnelle  donnée,  nous
l'encadrerons entre les symboles  \og \verb+^+\fg{} et \og \verb+$+\fg{}
qui marquent le début et la fin d'une chaîne.

Par exemple, considérons le fichier expressions.txt suivant:


{\itshape
a

b

aab

aaabbbb

abbbbbba

aaaaabaaaababababbaaaaaaaaabb

ababababababbabaaaaaaa

bbbbbbbbbbba

abbbbbbbbbbbbbba

aaaaaaabaaaaaaaaaaaaaaaaa
}

Considérons      la     première      expression      rationnelle     de
l'exercice~\vref{exo::regexp1}, à savoir $a(a|b)^\star a$.  Sous
\verb+grep+ cela donne:

\shell
\begin{lstlisting}[caption={}]
?\verb+$ egrep ^a\(a\|b\)*a$ ./expression.txt+! 
\end{lstlisting}

On obtient:

\begin{Verbatim}
abbbbbba
ababababababbabaaaaaaa
abbbbbbbbbbbbbba
aaaaaaabaaaaaaaaaaaaaaaaa
\end{Verbatim}

Donnez un  exemple de commande  permettant de n'obtenir que  la dernière
chaîne, que la cinquième, que la première, que la troisième.

Que renverra \verb+^a*b*a*$+? \verb|^a*b*a\+$|+?

Que fait le script Bash suivant:

\begin{lstlisting}[caption={}]
#!/bin/sh
# -*- coding: utf-8 -*-

read -p "Entrez une expression rationnelle  " rat

read -p "Entrez une chaîne  " chaine

> ./chaine_test.txt

echo ?\verb+$+!chaine >> chaine_test.txt

resultat=?\verb+$+!(egrep '?\verb+^+!'?\verb+$+!rat'?\verb+$+!' ./chaine?\verb+_+!test.txt)

if [ ?\verb+$+!{?\verb+#+!resultat} -gt 0 ] ; then
    echo Reconnu ;
else
    echo Non?\verb+_+!reconnu ;
fi
\end{lstlisting}


\end{exercice}

\subsection{Généralités sur les automates}


\begin{exercice}[Diagramme d'un automate]\label{exo::gen1}
  
Considérons l'automate suivant:
\begin{itemize}
\item l'alphabet est $A=\bigl\{0,1\bigr\}$;
\item $Q=\bigl\{q_0,q_1,q_2,q_3,q_4\bigr\}$;
\item $I=\bigl\{q_0\bigr\}$;
\item $T=\bigl\{q_3\bigr\}$;
\item la fonction de transition est définie par:
\begin{center}
             \begin{tabularx}{0.5\linewidth}{Y{1}}
	     \whline
             $\tau$&0&1\\
             \whline
             $q_0$&$q_1$&$q_3$\\ 
             \hline
             $q_1$&$q_4$&$q_2$\\
             \hline
             $q_2$&$q_0$&$q_2$\\
             \hline
             $q_3$&$q_2$&$q_4$\\
             \hline
             $q_4$&$q_4$&$q_4$\\
             \whline
             \end{tabularx}
             \end{center}
\end{itemize}

Dessinez le diagramme correspondant.


Donnez des chaînes reconnues par l'automate.

Donnez des chaînes non reconnues par l'automate.

Que peut-on dire à propos de l'état $q_4$?
\end{exercice}










\begin{exercice}\label{exo::gen2}

Pour chacun des automates suivants $I$ (ou $T$) indique que l'\'{e}tat est
initial (ou terminal), l'alphabet  est $A~=~\bigl\{a,b\bigr\}$ et les états
sont nommés à l'aide d'entiers. 

Donnez une repr\'{e}sentation graphique
et des chaînes qui appartiennent  au langage engendr\'{e} ou reconnu par
chacun des automates suivants:
\begin{enumerate}
\item 
\[
\begin{tabularx}{0.5\linewidth}{Y{1}}
	     \whline
$ \tau$ & $a$ & $b$ \\ \hline
1$\left( I\right) $ & 1,\,2 & 1 \\ \hline
2 & 3 & 3 \\ \hline
3 & 4 & 4 \\ \hline
4$\left( T\right) $ &  &  \\ \whline
\end{tabularx}%
\ 
\]

\item 
\[
\begin{tabularx}{0.5\linewidth}{Y{1}}
	     \whline
$ \tau$ & $a$ & $b$ \\ \whline
1$\left( I\right) $ & 2,\,3 & 2 \\ \hline
2$\left( T\right) $ & 3 &  \\ \hline
3$\left( I,T\right) $ &  & 1,\,2 \\ \whline
\end{tabularx}%
\ 
\]

\item 
\[
\begin{tabularx}{0.5\linewidth}{Y{1}}
	     \whline
$ \tau$ & $a$ & $b$ \\ \whline
1$\left( I\right) $ & 2,\,3 & 1 \\ \hline
2$\left( T\right) $ & 1,\,2 &  \\ \hline
3$\left( I\right) $ & 1,\,3 & 2 \\ \whline
\end{tabularx}%
\ 
\]
\end{enumerate}

\end{exercice}


\subsection{Expression rationnelle associée à un automate}

\begin{exercice}

On consid\`{e}re l'automate $A$\ sur l'alphabet $A=\left\{ a,b\right\} $\
qui a pour ensemble d'\'{e}tats $Q=\left\{ e_{1},e_{2}\right\} ,$\ $e_{1}$\ 
\'{e}tant simultan\'{e}ment \'{e}tat initial et \'{e}tat final. Les
transitions de $A$\ sont donn\'{e}es par le tableau : 
\[
\begin{tabularx}{0.5\linewidth}{Y{1}}
\whline
$\tau$ & $a$ & $b$ \\ \whline
$e_{1}$ & $e_{1}$ & $e_{2}$ \\ \hline
$e_{2}$ & $e_{2}$ & $e_{1}$ \\ \whline
\end{tabularx}%
\ 
\]%
ce tableau traduit, par exemple, que si l'automate est dans l'\'{e}tat $%
e_{2} $\ et qu'il lit $b$, alors il passe \`{a} l'\'{e}tat $e_{1}.$


\begin{enumerate}
\item Cet automate est-il d\'{e}terministe ? Justifier votre r\'{e}ponse.

\item Cet automate est-il complet ? Justifier votre r\'{e}ponse.

\item Donner une repr\'{e}sentation graphique de cet automate.


\item D\'{e}terminer une expression rationnelle $R$
qui d\'{e}crit L.


\item On note $L$\ le langage engendr\'{e} ou reconnu par cet automate, $L=%
\mathcal{L}\left( \mathcal{A}\right)$. Ce langage est-il rationnel ?

\item  $\vide$\   d\'{e}signe  la  chaîne   vide.  Expliquez  pourquoi
  $\vide$ appartient à L.


\end{enumerate}

\end{exercice}






\begin{exercice}

On note L le langage reconnu par cet automate:


%{\footnotesize
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)                    {$q_0$};
 \node[state] (B) [above left of=A] {$q_1$};
 \node[state,accepting] (C) [ above right of=A] {$q_2$};

 
  \path (A) edge node {$b$} (B)
        (A) edge [below right] node {$a$} (C)
        (B) edge [loop left] node {$b$} (B)
            edge [bend left ] node {$a$} (C)
        (C) edge [bend left ] node {$a$} (B)
            edge [loop above] node {$b$} (C);
\end{tikzpicture}
\end{center}
%}

Déterminez une expression régulière R qui décrit L.

\end{exercice}


\subsection{Automates standards et émondés}



\begin{exercice}
  Standardisez et  émondez les automates  de l'~\ref{exo::gen1}
  et de l'~\ref{exo::gen2}.
\end{exercice}


\begin{exercice}
  Standardisez l'automate défini sur $A=\bigl\{a,b\bigr\}$ par:

\begin{center}
             \begin{tabularx}{0.5\linewidth}{Y{1}}
	     \whline
             $\tau$&$a$&$b$\\
             \whline
             $q_0$&$q_1$&$q_0$\\
             \hline
             $q_1$&$q_0$&$q_1$\\
             \hline
             $q_2$&$q_2$&$q_3$\\
             \hline
             $q_3$&$q_3$&$q_2$\\
             \whline
             \end{tabularx}
             \end{center}
sachant que $I=\bigl\{q_0,q_2\bigr\}$ et $T=\bigl\{q_1,q_2\bigr\}$.

\end{exercice}


\begin{exercice}
  Standardisez  et émondez  l'automate défini  sur $A=\bigl\{a,b\bigr\}$
  par:
\begin{center}
             \begin{tabularx}{0.5\linewidth}{Y{1}}
	     \whline
             $\tau$&$a$&$b$\\
             \whline
             $q_0$&$q_0$,$q_1$&\\
             \hline
             $q_1$&&$q_2$\\
             \hline
             $q_2$&$q_2$&$q_2$\\
             \hline
             $q_3$&$q_2$&$q_1$\\
             \whline
             \end{tabularx}
             \end{center}
sachant que $I=\bigl\{q_0,q_2\bigr\}$ et $T=\bigl\{q_0,q_1\bigr\}$.
\end{exercice}


\subsection{Automates déterministes}


\begin{exercice}
  

On consid\`{e}re l'automate $A=\left( A,E,I,T,U\right) $\ avec

\begin{enumerate}
\item 
\begin{itemize}
\item $A=\left\{ a,b\right\} ,$\ l'alphabet de l'automate $A.$

\item $Q=\left\{ 1,2,3\right\} $\ l'ensemble des \'{e}tats de $A.$

\item $I=\left\{ 1,3\right\} $\ l'ensemble des \'{e}tats initiaux de $A.$

\item $T=\left\{ 2,3\right\} $\ l'ensemble des \'{e}tats terminaux de $A.$

\item $U=\left\{ \left( 1,a,2\right) ,\left( 1,a,3\right) ,\left(
1,b,2\right) ,\left( 2,a,3\right) ,\left( 3,b,1\right) ,\left( 3,b,2\right)
\right\} $\ l'ensemble des transitions de $A,$\ $U$\ pouvant \^{e}tre repr%
\'{e}sent\'{e} par le tableau 
\[
\begin{tabularx}{0.5\linewidth}{Y{1}}
\whline
$\tau$ & $a$ & $b$ \\ \whline
1$\left( I\right) $ & 2,3 & 2 \\ \hline
2$\left( T\right) $ & 3 &  \\ \hline
3$\left( I,T\right) $ &  & 1,2 \\ \whline
\end{tabularx}%
\ 
\]%
On pr\'{e}cise dans ce tableau si un \'{e}tat est initial ou 
terminal.
\end{itemize}

\item Donnez une repr\'{e}sentation graphique de $A$.

\item D\'{e}terminez un automate d\'{e}terministe $A^{\prime }=\left(
A,E^{\prime },I^{\prime },T^{\prime },U^{\prime }\right) $\ \'{e}quivalent 
\`{a} $A,$\ on pr\'{e}sentera $U^{\prime }$\ sous forme d'un tableau.
\end{enumerate}

\end{exercice}




\begin{exercice}
\og D\'{e}terminisez\fg{} les automates suivants: $I$\ indique que l'\'{e}tat est
initial et $T$\ que l'\'{e}tat est final

\begin{enumerate}
\item 
\[
\begin{tabularx}{0.5\linewidth}{Y{1}}
\whline
$ \tau$ & $a$ & $b$ \\ \whline
1$\left( I\right) $ & 2,3 & 2 \\ \hline
2$\left( T\right) $ & 3 &  \\ \hline
3$\left( I,T\right) $ &  & 1,2 \\ \whline
\end{tabularx}%
\ 
\]

\item 
\[
\begin{tabularx}{0.5\linewidth}{Y{1}}
\whline
$ \tau$ & $a$ & $b$ \\ \whline
1$\left( I\right) $ & 2 & 2,3 \\ \hline
2$\left( T\right) $ &  & 1 \\ \hline
3$\left( I,T\right) $ & 1,2 &  \\ \whline
\end{tabularx}%
\ 
\]

\item 
\[
\begin{tabularx}{0.5\linewidth}{Y{1}}
\whline
$ \tau$ & $a$ & $b$ \\ \whline
1$\left( I\right) $ & 2 & 1,2 \\ \hline
2$\left( I\right) $ & 3 & 3 \\ \hline
3$\left( T\right) $ & 4 & 4,1 \\ \hline
4$\left( T\right) $ &  &  \\ \whline
\end{tabularx}%
\ 
\]
\end{enumerate}

\end{exercice}

\subsection{Construction d'automates}

\begin{exercice}
Construire  des  automates  correspondant aux  expressions  rationnelles
suivantes:
%\begin{multicols}{2}
\begin{enumerate}
\item $E=aab^\star ab$
\item $E=a^\star b^\star a^\star$
\item $E=a^\star b A^+$
\item $E=A^\star abcA^\star$
\item $E=abA^\star | (A^4)^\star$
\item $E=(a|aba)^\star b(a|b)^\star aba(a|b)^\star$
\end{enumerate}
%\end{multicols}
\end{exercice}


\begin{exercice}[Identités rationnelles]
  
Tout   comme  pour  les   automates,  on   peut  définir   une  relation
d'équivalence   sur  l'ensemble   des  expressions   rationnelles:  deux
expressions  sont équivalentes  si, et  seulement si,  les  langages qui
leurs sont associés sont égaux.

L'identité suivante est classique:

$(a|b)^\star\equiv (a^\star b)^\star a^\star$.

Prouvez-la en passant aux automates associés.



\end{exercice}

\subsection{Automates séquentiels}


\begin{exercice}[avertissement d'erreur de transmission]
Un  protocole de  codage de  message  prévoit d'indiquer  une erreur  de
transmission   si   trois  1   apparaissent   consécutivement  dans   le
message.  Construire un  automate à  états finis  qui renvoie  1  si, et
seulement si, la chaîne transmise contient trois 1 consécutifs.
\end{exercice}



\begin{exercice}[automate de rendu de monnaie]
Un distributeur de boisson accepte les pièces de 5, 10 et 20 centimes.

Une  fois que  l'utilisateur  a  introduit au  minimum  30 centimes,  le
distributeur lui rend la somme  dépassant 30 centimes et il peut choisir
entre un café en appuyant sur la  touche K ou un lait fraise en appuyant
sur la touche L.

Construire un automate à états finis avec sortie qui modélise ce distributeur.
\end{exercice}


\begin{exercice}[Retard]
Décrivez le plus précisément possible l'action de cet automate:



\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=2.5cm,semithick, bend angle=20]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 3em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)  {$q_0$};
 \node[state] (B) [above right of=A] {$q_1$};
 \node[state] (C) [ below right of=A] {$q_2$};
 
 
 \path (A) edge node {1,0} (B)
       (B) edge [loop right] node {1|1} (B)
       (B) edge [bend left] node {0|1} (C)
       (C) edge [bend left] node {0|1} (B)
       (C) edge [loop right] node {0|0} (C)
       (A) edge node[left] {0|0} (C);
\end{tikzpicture}
\end{center}

\end{exercice}


\begin{exercice}[Table de 3]
Écrivez la table de trois en binaire inversé.

Faites opérer l'automate suivant sur les nombres de un à dix représentés
sous forme binaire inversée:


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=3.2cm,semithick, bend angle=20]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 3em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial,accepting,accepting where = right, accepting text = $\vide$] (A) {$q_0$};
 \node[state,accepting,accepting where = right, accepting text = 1] (B) [ right of=A] {$q_1$};
 \node[state,accepting,accepting where = right, accepting text = 01] (C) [  right of=B] {$q_2$};
 
 
 \path (A) edge[bend left] node {1|1} (B)
       (A) edge [loop above] node {0|0} (A)
       (B) edge [bend left] node {0|1} (A)
       (C) edge [bend left] node {0|0} (B)
       (B) edge [bend left] node {1|0} (C)
       (C) edge [loop above] node {1|1} (C)
       ;
\end{tikzpicture}
\end{center}



\end{exercice}


\subsection{Automates à pile}


\begin{exercice}
Soit l'automate  \`{a} pile sur l'alphabet  $A=\left\{ a,b,...\right\} $
avec:
\begin{itemize}
\item $E=\left\{ s,q\right\} ,s$ est l'\'{e}tat initial

\item $T=\left\{ t\right\} $

\item $P=\left\{ A,B\right\} $

\item les transitions sont :
\begin{multicols}{2}
\begin{itemize}
\item $T_{1}=\left( \left( s,\vide \right) ,a,\left( s,A\right)
\right) $

\item $T_{2}=\left( \left( s,\vide \right) ,b,\left( s,B\right)
\right) $

\item $T_{3}=\left( \left( s,A\right) ,a,\left( s,AA\right) \right) $

\item $T_{4}=\left( \left( s,B\right) ,a,\left( s,AB\right) \right) $

\item $T_{5}=\left( \left( s,A\right) ,b,\left( s,BA\right) \right) $

\item $T_{6}=\left( \left( s,B\right) ,b,\left( s,BB\right) \right) $

\item $T_{7}=\left( \left( s,A\right) ,a,\left( t,\vide \right)
\right) $

\item $T_{8}=\left( \left( s,B\right) ,b,\left( t,\vide \right)
\right) $

\item $T_{9}=\left( \left( t,A\right) ,a,\left( t,\vide \right)
\right) $

\item $T_{10}=\left( \left( t,B\right) ,b,\left( t,\vide \right)
\right) $
\end{itemize}
\end{multicols}
\end{itemize}

\begin{enumerate}
\item Donner une repr\'{e}sentation graphique de cet automate. On remarquera
que cet automate n'est pas d\'{e}terministe.

\item On note $L$ le langage engendr\'{e} par cet automate, d\'{e}montrer que

\begin{enumerate}
\item $aaaa\in L$

\item $bbbbbb\in L$

\item $aaabaabbaabaaa\in L,$ observer l'\'{e}tat de la pile au fur et \`{a}
mesure de la reconnaissance du mot.

\item $L$ est un langage particulier sur $A$ en ce sens que tous les mots de 
$L$ ont une particularit\'{e}, deviner cette particularit\'{e}.
\end{enumerate}
\end{enumerate}


\end{exercice}



\begin{exercice}
  Déterminer un automate à pile qui reconnaît les langages:

  \begin{enumerate}
  \item $L_1=\bigl\{u\in\{a,b\}^\star\mid |u|_a=2|u|_b\bigr\}$;
\item   $L_2=\bigl\{u\in\{a,b\}^\star\mid   \overline{u}=u\bigr\}$  avec
  $\overline{u}$ le miroir de $u$.
  \end{enumerate}
\end{exercice}

\subsection{Problèmes divers}



\begin{exercice}[Minimalisation]
  Appliquez l'algorithme de \textsc{Moore} pour minimaliser les automates
  étudiés dans les exercices précédents.


\end{exercice}


\begin{exercice}[Une conséquence du théorème de \textsc{Kleene}]
  Soit A un alphabet et $L\in A^\star$ un
    langage reconnaissable de $A^\star$ donc il est rationnel.  Le langage
    $L^c=\complement_{E}A^\star=\bigl\{u\in                   A^\star\mid
    u\not\in L\bigr\}$ est aussi un langage rationnel donc il est
    reconnaissable.  
 


Soit maintenant $\AR=(A,Q,\{d\},T,\tau)$ un automate
    fini déterministe et complet qui reconnaît un langage L. L'automate
    $\AR'=(A,Q,\{d\},Q-T,\tau)$  reconnaît le  langage  $L^c$. En  effet,
    puisque $\AR$  et $\AR'$ sont  tous deux complets  et déterministes,
    chaque chaîne $u$ de $A^\star$ est l'étiquette d'exactement un
    calcul  commençant en $d$.  Soit $q_u$  l'extrémité terminale  de ce
    calcul. Alors $u$ appartient à L si, et seulement si, $q$ appartient
    à T et $u$ appartient à  $L^c$ si, et seulement si, $q$ appartient à
    $\complement_{Q}F=Q-F$.

On travaille sur l'alphabet $\bigl\{0,1\bigr\}$. Déterminer alors une expression rationnelle représentant le langage L
des chaînes NE contenant PAS la  chaîne 001. Il sera utile de passer par
la    construction   d'automates.    La    résolution   de    l'~\vref{exo::sans} se trouve ainsi facilitée...

\end{exercice}


\begin{exercice}[Extrait de l'épreuve Mines-Ponts 2011]
Pour tout entier $n$ non nul  on définit le langage $L_n$ sur l'alphabet
$A=\bigl\{a,b\bigr\}$ de  la manière suivante: $L_n$  est l'ensemble des
mots de longueur supérieure ou égale  à $2n$ dont le suffixe de longueur
$n$  est  le  miroir  du  préfixe  de  longueur  $n$.  Ainsi  $abbbbaba$
appartient à $L_1$ et à $L_2$ mais pas à $L_3$.

\begin{enumerate}
\item Expliquer pourquoi $abbbbaba$
appartient à $L_1$ et à $L_2$ mais pas à $L_3$.
\item Donner une expression rationnelle décrivant $L_1$.
\item Construire un automate $\AR$ non déterministe reconnaissant le langage
  $L_2$. On  impose que $\AR$ ait un  seul état initial et  un seul état
  final; par  ailleurs, les transitions de $\AR$  seront étiquetées par
  les éléments de A.
\item Déterminiser l'automate obtenu à la question précédente. 
\item En s'inspirant des questions précédentes, montrer que $L_n$ est un
  langage rationnel pour tout $n \geqslant 1$.

\end{enumerate}

\end{exercice}
  
\begin{exercice}[Addition binaire]
Le nombre 27  s'écrit 110011 en écriture binaire  inversée. Le nombre 14
s'écrit  0111.  On considère  le  couple  (110011,0111)  que l'on  écrit
${110011  \choose 011100}$  soit encore  ${1 \choose  0}{1  \choose 1}{0
  \choose 1}{0  \choose 1}{1 \choose 0}{1  \choose 0}$. On  peut donc le
considérer comme  une chaîne  sur l'alphabet $A=\bigl\{{0  \choose 0},{1
  \choose 0},{0 \choose 1},{1 \choose 1}\bigr\}$. 

Voici un automate séquentiel défini sur cet alphabet:



\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=2cm,semithick, bend angle=20]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 3em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial  left,initial  where   =  right,  initial  text  =
 $\vide$,accepting right, accepting text = $\vide$,fill=green!20,double] (A) {$q_0$};
 \node[state,accepting right, accepting text = 1,fill=blue!20,double] (B) [ below of=A] {$q_1$};
 
 
 \path (A) edge[bend left] node {${1\choose 1}|0$} (B)
       (A) edge [loop above] node {${0\choose 0}|0$, ${0\choose 1}|1$, ${1\choose 0}|1$} (A)
       (B) edge [bend left] node {${0\choose 0}|1$} (A)
       (B) edge [loop below] node {${0\choose 1}|0$, ${1\choose 0}|0$, ${1\choose 1}|1$} (C)
       ;
\end{tikzpicture}
\end{center}
Faites lire ${1 \choose  0}{1  \choose 1}{0
  \choose 1}{0 \choose 1}{1 \choose 0}{1 \choose 0}$ par l'automate. Que
fait cet automate?
\end{exercice}





\begin{exercice}[Parenthèses]\label{paren}
  Une   chaîne  bien   parenthésée   est  une   chaîne  sur   l'alphabet
  $\bigl\{(,)\bigr\}$ comportant autant  de parenthèses ouvrantes que de
  parenthèses fermantes et telle que  chacun de ses préfixes contient au
  moins autant de parenthèses ouvrantes que de parenthèses fermantes.

Déterminer un automate qui reconnaît les chaînes bien parenthèsées.
\end{exercice}


\subsection{Grammaires}

\begin{exercice}
Essayer de caractériser le langage engendré par la grammaire suivante:

$$S\to ab|aS|Sb$$

Est-elle régulière? 

Proposer  une  grammaire régulière  équivalente,  puis  un automate  qui
reconnaît le même langage puis une expression rationnelle associée.

Que dire de la grammaire:


$S\to AB$

$A\to a|aA$

$B\to b|bB$

Pour chacune  des trois grammaires,  proposer des dérivations  qui donnent
$aabbb$ puis  les arbres de  dérivation qui correspondent.  Les grammaires
sont-elles ambiguës?


Donner   maintenant   une   grammaire   qui  décrit   le   langage   sur
$\bigl\{a,b\bigr\}$ qui ne  contient que des chaînes avec  autant de $a$
que de $b$ avec tous les $a$ au début et au moins un $a$.

Donner une  grammaire qui décrit  les chaînes formées  de $a$ et  de $b$
contenant au  moins un $b$  et deux arbres  de dérivation associés  à la
chaîne $abb$.

\end{exercice}

%
\begin{exercice}[Palindromes]
Donner une grammaire qui engendre les palindromes sur l'alphabet $\bigl\{a,b\bigr\}$.
\end{exercice}
%

\begin{exercice}[Chaînes bien parenthésées]
  Donner  une  grammaire  qui   engendre  l'ensemble  des  chaînes  bien
  parenthésées  (voir \vref{paren}) et  donner  une dérivation
  gauche de (())().


Vérifier  que  ()(())  est   bien  parenthésée  par  analyse  syntaxique
descendante en largeur.


\end{exercice}

%

\begin{exercice}[Priorité et ambiguïté]
On étudie une grammaire  décrivant des expressions arithmétiques sur des
nombres  réduits à  un chiffre  en base  10 et  les  opérateurs binaires
d'addition, de soustraction et de multiplication. 

$\Sigma=\bigl\{0,1,2,3,4,5,6,7,8,9,+,-,\times\bigr\}$

Les  opérations sont
notées sous  forme \textit{infixée}, c'est-à-dire que si  $E_1$ et $E_2$
sont des  expressions arithmétiques,  alors $E_1 +  E_2$, $E_1  -E_2$ et
$E_1\times E_2$ aussi.

Voici une grammaire possible:

$S \to C|S+S|S-S|S\times S$

$C\to 0|1|2|3|4|5|6|7|8|9$

Donner deux arbres syntaxiques  correspondant à $1-2-3$ puis deux autres
correspondant à $1+2\times 3$.

Que dire alors de la grammaire?

Pour  contrer   ce  désagrément  (pourquoi  est-ce   un  désagrément  en
pratique?), on peut envisager plusieurs stratégies.



Par  exemple,  on  peut   décider  que  soustraction  et  addition  sont
associatives à gauche. On remplace donc l'axiome par:

$S\to C|S+C|S-C$

Que se passe-t-il maintenant pour $1-2-3$? $1-2+3$?


Comment  changer la  grammaire  pour  avoir cette  fois  l'associativité  à
droite?

On choisira par la suite la priorité à gauche.


On s'occupe maintenant de la priorité: $\times$ a priorité sur $+$ et $-$.

Ainsi, une expression est d'abord une somme ou une différence puis, à un
second niveau d'abstraction, chaque terme est un produit de facteurs.

Donner  une  grammaire traduisant  cette  construction  puis l'arbre  de
dérivation de $1+2\times 3$.

Une  possibilité  pour  \og  contrer  \fg{} la  règle  de  priorité  est
d'utiliser des parenthèses.

Comment réorganiser la grammaire avec la règle:

$F \to C | (E)$

Donner  alors les  arbres  de  dérivation de  $1\times  2+3\times 4$  et
$1\times(2+3)\times 4$.



\end{exercice}


\begin{exercice}[Notation polonaise inverse]

La  notation prefixée  a  été introduite  en  1920 par  le polonais  Jan
\textsc{\L ukasiewicz}  puis \og inversée\fg{}  par l'australien Charles
\textsc{Hamblin} dans les années 1950.

Elle  est utilisée  en  informatique car  elle  permet de  se passer  de
parenthèses (machines HP, PostScript, processeurs).

$1+2$ s'écrit  $12+$ et  $1\times 2$ s'écrit  $1 2 \times$.  Ensuite, on
écrit les triplets (nb,op,nb) dans le bon ordre de calcul.

Par exemple, $(1+2)\times(3+4)$ s'écrit $12+34+\times$.

$((1+2)\times 3)+4$
s'écrit  $12+3\times4+$ mais  aussi  $4312+\times +$  ce  qui est  moins
évident peut-être.

Comment décrire ce mécanisme à l'aide d'une pile?

Comment le décrire à l'aide d'une grammaire? Est-elle ambiguë? 
  
\end{exercice}

\begin{exercice}[Système de traduction]

Un  système de  traduction est  une grammaire  algébrique à  laquelle on
ajoute des \textit{actions sémantiques}.


Par exemple, la règle $A\to + B \,\bigl\{\, \mathtt{print('+')}\, \bigr\}\, C$
se traduira par l'arbre de dérivation:

\begin{center}
\tikz
\node{A}
child{node{+}}
child{node{B}}
child{node{$\bigl\{ \,\mathtt{print('+')}\, \bigr\}$}}
child{node{C}};
\end{center}

Donner un système de traduction effectuant la conversion notation infixe
avec associativité à gauche vers NPI. On se contentera de traiter le cas
d'additions et de soustractions de nombres d'un chiffre.

Donner l'arbre de dérivation correspondant à 9-8+1.

\end{exercice}



\begin{exercice}[Lemme de pompage]
Le lemme de pompage (ou \og{} de gonflement\fg ou \og de l'étoile\fg{} a
été vu  en cours et donne  une condition nécessaire pour  vérifier si un
langage défini  par une  grammaire est  régulier et dit  en gros  que si
un  arbre  de  dérivation  est  plus  \og haut\fg{}  que  le  nombre  de
variables, il y a au moins une  variable répétée sur un chemin issu de S
et la  portion de  branche située entre  ces deux occurrences  peut être
répétée autant de fois qu'on veut sans \og quitter\fg{} le langage.


Voyons une application classique qui va nous permettre de montrer que le
sempiternel  langage $L=\bigl\{a^nb^n\mid n\in  \bbn \bigr\}$  n'est pas
régulier.

On va raisonner par l'absurde.   Quelque soit l'entier $k$, on considère
la chaîne  $\mu=a^kb^k$ qui  est de longueur  supérieure à $k$.  Si le
langage 
est  régulier, alors  $\mu$  contient un  préfixe  $\nu\xi$ de  longueur
inférieur à  $k$ tel  que $\mu=\nu\xi\rho$ et  $nu\xi\xi\rho$ appartient
encore à L. En quoi cette condition aboutit à une contradiction? 

Appliquer cette méthode pour montrer  que le langage des palindromes sur
$\bigl\{a,b\bigr\}$  n'est  pas   régulier.  On  pourra  distinguer  les
palindromes de longueur paire et ceux de longueur impaire.
\end{exercice}

\begin{exercice}
  Déterminer un  automate qui reconnaît le  langage $\bigl\{a^{2n}\mid n
  \geqslant 0\bigr\}$.  Donner une grammaire régulière  qui reconnaît ce
  langage. 
\end{exercice}

\begin{exercice}[Ambiguïté]
Soit   $\Sigma=\bigl\{\mathtt{if},\mathtt{then},\mathtt{else},a,b\bigr\}$
et la grammaire:

 $S\to \mathtt{if} \ a\ \mathtt{then }\ S \ \mathtt{else}
\ S\ |\ \mathtt{if} \ a\ \mathtt{then }\ S \ |\ b$

Cette grammaire est-elle ambiguë? 

\end{exercice}


\begin{exercice}
Soit G et $G'$ les deux grammaires suivantes:

$G: S\to aSb|ab$

$G': S\to cSd|cd$

Comparer $\LR(G)\cup\LR(G')$ et $\LR(G\cup G')$.

\end{exercice}

\begin{exercice}[Automate $\to $ grammaire]
À chaque transition, on associe une règle de grammaire. Un état terminal
renvoie à un symbole terminal en doublant éventuellement la règle.

Donner une grammaire associée à l'automate suivant:

\begin{center}
             \begin{tabularx}{0.2\textwidth}{Y{1}}
	     \whline
             &a&b\\
             \whline
             1(I)&1,2&1,3\\
             \hline
             2&4&\\
             \hline
             3&&5\\
             \hline
             4(T)&4&4\\
             \hline
             5(T)&5&5\\
             \whline
             \end{tabularx}
             \end{center}

En déduire une simplification de l'automate puis le rendre déterministe.

En déduire une simplification de l'automate puis le rendre déterministe.
\end{exercice}

\subsection{Révisions}

\begin{exercice}
  Donner un automate qui reconnaît le langage de $\bigl\{a,b\bigr\}^\star$ dont les chaînes n'ont pas
  trois $a$ consécutifs.
\end{exercice}


\begin{exercice}[Glushkov et minimalisation]
  Soit $E=(a|b)^\star abb$

Écrire  un automate  qui  reconnaît le  langage  associé à  l'expression
rationnelle E. Est-il minimal?
\end{exercice}

\begin{exercice}
Donner  une  expression rationnelle  pour  le  langage  reconnu par  cet
automate:


\begin{center}
             \begin{tabularx}{0.2\textwidth}{Y{1}}
	     \whline
             &a&b\\
             \whline
             0(I)&1,2&0\\
             \hline
             1(T)&0,1,2&1\\
             \hline
             2&&2\\
             \whline
             \end{tabularx}
             \end{center}

Déterminiser cet  automate et  trouver une autre  expression rationnelle
associée.

Minimiser ensuite l'automate et trouver  une autre  expression rationnelle
associée.
\end{exercice}


\begin{exercice}
Minimaliser l'automate suivant:

\begin{center}
             \begin{tabularx}{0.2\textwidth}{Y{1}}
	     \whline
             &a&b\\
             \whline
             0(I)&1&5\\
             \hline
             1&2&3\\
             \hline
             2(T)&2&4\\
             \hline
             3&1&6\\
             \hline
             4(T)&1&4\\
             \hline
             5&5&5\\
             \hline
             6&1&6\\
             \whline
             \end{tabularx}
             \end{center}
\end{exercice}

\begin{exercice}[Machine de \textsc{Turing} plus forte qu'un automate à pile]
  Un automate à pile  ne peut reconnaître le langage $\bigl\{a^nb^nc^n\mid
  n\in\bbn\bigr\}$: un lemme de pompage généralisé permet de le montrer.

  Déterminer une machine de  \textsc{Turing} qui va reconnaître ce langage
  à l'aide de 5 états plus deux états (accepté, refusé).

  Le principe est de barrer le premier $a$, aller au bout du mot et barrer
  le dernier $c$ puis revenir en arrière et barrer le dernier $b$ et
  recommencer en allant vers le  rejet dès que l'occasion s'en présente et
  sachant que la chaîne vide est accepté.
\end{exercice}



\begin{exercice}[Machine de \textsc{Turing}]
  Construisez les machines de Turing suivantes:
  \begin{enumerate}
  \item $M$ qui écrit 0 1 0 1 0 1 0 ... sur un ruban blanc.  \emph{Pour ceux qui douteraient de l'intérêt de cette question, s'adresser à A. Turing.}
  \item   $M$ à un ruban sur l'alphabet $\{0,1,\varepsilon\}$ qui multiplie par 2 son
    entrée binaire.
  \item   $M$ à un ruban sur l'alphabet $\{0,1,\varepsilon\}$ qui multiplie par 2 et
    ajoute 1 à son entrée binaire.
  \item    $M$ à un ruban sur l'alphabet $\{0,1,\varepsilon\}$ qui ajoute 1 à son
    entrée binaire.
  \end{enumerate}
\end{exercice}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{listeexercices}
\modenormal % restaure les définitions de sections, sous-sections, etc;

\vfill

\eject


\section{Automates et Caml}

\subsection{Modélisation}

La  modélisation  adoptée  suit  la   définition  du  cours,  mais  nous
remplacerons la relation de transition par son graphe.

Ainsi, un automate $\AR$ est caractérisé par un quintuplet $<\Sigma,Q,D,T,\tau>$:
\begin{itemize}
\item un alphabet $\Sigma$ appelé l'\textit{alphabet d'entrée};
\item un alphabet Q appelé l'\textit{alphabet d'état} (Q est donc \textbf{fini});
\item  une partie  D non  vide de  Q appelée  \textit{ensemble  des états
    initiaux};
\item  une partie T  non vide  de Q  appelée \textit{ensemble  des états
    terminaux};
\item une relation  $\tau$ de $Q\times \Sigma$ vers Q  ou de $Q\times \left(\Sigma
    \cup   \{\vide\}\right)$  vers   Q,   appelée  \textit{relation   de
    transition} qui est  elle-même caractérisée par sont  graphe qui est
    une partie de $((Q\times\Sigma)\times Q)$.
\end{itemize}

Cela donne:

\begin{lstlisting}[caption={}]
(* un état construit à partir d'un entier *)
type etat = int;;

(* un symbole construit à partir d'un caractère  *)
type symbole = char;;

(* automate sous forme d'enregistrement (record) *)
type automate =
{
   q        : etat list;
   d        : etat list;
   t        : etat list ;
   graphe   : ((etat * symbole) * etat)  list;
   s        : symbole list;
};;
\end{lstlisting}


Voici un exemple d'automate: dessinez-le:

\begin{lstlisting}[caption={}]
let graphe1 = 
    [((1,'a'),  3)      ;((1,'b') , 2)
    ;((2,'a') , 3)      ;((2,'b') , 2)
    ;((3,'a') , 4)      ;((3,'b') , 3)
    ;((4,'a') , 3)      ;((4,'b') , 4)]
;;
let otto1 =
{
    q       = [1; 2; 3; 4];
    d       = [1];
    t       = [4];
    graphe  = graphe1;
    s       = ['a';'b'];
};;
\end{lstlisting}



Voici un extrait de la documentation Ocaml sur le module \verb+List+:

\begin{lstlisting}
val assoc : 'a -> ('a * 'b) list -> 'b
"assoc a l returns the value associated with key a in the list of pairs l. That is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost binding of a in list l. Raise Not_found if there is no value associated with a in the list l."
\end{lstlisting}

Déduisez-en une fonction \verb+tau+ de signature: 

\verb+val tau : automate -> etat * symbole -> etat = <fun>+

  N'oubliez pas que la
curryfication est associative à  droite: cette signature correspond donc
à \verb+val tau : automate -> ( (etat*symbole) -> etat ) = <fun>+

Par exemple, vous devriez obtenir:

\begin{lstlisting}[caption={}]
# tau otto1 (1,'a');;
- : etat = 3
\end{lstlisting}

Il  s'agit   maintenant  de   construire  le  cheminement   d'une  liste
d'étiquettes dans l'automate.


On veut donc construire une fonction \verb+parcours+ de signature:

\begin{lstlisting}[caption={}]
val parcours : automate -> symbole list -> etat list = <fun>
\end{lstlisting}

On se remémorera le filtrage par motif  vu il y a quelques semaines (\og
\textit{pattern matching}\fg{}).

Par exemple, on obtiendra:

\begin{lstlisting}[caption={}]
# parcours otto1 ['a';'a';'a';'b';'a'];;
- : etat list = [1; 3; 4; 3; 3; 4]
\end{lstlisting}

Pour   cela,    il   faudra   par   exemple    utiliser   une   fonction
\textit{locale}. On aura donc une structure du type:


\begin{lstlisting}[caption={}]
let parcours auto chaine =
    let rec parcours_local t e chaine =
        match chaine with
        | ...  -> ...
        | ...  -> ... 
    in
    parcours_local ...   ...   ...
;;
\end{lstlisting}

On pourra en déduire une fonction \verb+lit+ de signature:

\verb+val lit : automate -> symbole list -> bool = <fun>+ 

qui teste si une liste de symboles correspond à un parcours vers un état final:

\begin{lstlisting}[caption={}]
# lit otto1 ['a';'a';'a';'b';'a'];;
- : bool = true
# lit otto1 ['a';'a';'a';'b'];;
- : bool = false
\end{lstlisting}

\subsection{Visualisation}

Nous utiliserons le logiciel  \textsf{GraphViz} qui permet de visualiser
un  graphe  à partir  d'un  fichier  d'extension \verb+dot+.  Nous  vous
invitons à parcourir sa documentation.

Voici des fonctions qui font le boulot:

\begin{lstlisting}[caption={}]
let trans_to_string = fun ((e1, s), e2) ->  
    String.concat ""
    (string_of_int(e1)::"->"::string_of_int(e2)::"[label=\""::(String.make 1 s)::"\"];\n"::[]);;

let ini_to_string = fun auto ->
    let rec parcours = fun liste -> 
        match liste with
    |[] -> ""
    |t::q -> (string_of_int(t)^" [color = yellow,style=filled];\n ")^(parcours q)
    in parcours auto.d;;

let fin_to_string = fun auto ->
    let rec parcours = fun liste -> 
        match liste with
    |[] -> ""
    |t::q -> (string_of_int(t)^" [color = blue,style=filled,fontcolor=white];\n ")^(parcours q)
    in parcours auto.t;;

let fini_to_string = fun auto ->
    let rec parcours = fun liste -> 
        match liste with
    |[] -> ""
    |t::q -> (string_of_int(t)^" [color = red,style=filled,fontcolor=white];\n ")^(parcours q)
    in parcours (List.filter (fun x-> List.mem x auto.d) auto.t);;

let rec auto_to_string = fun graphe ->
    match graphe with
     |[] -> ""
     |t::q -> (trans_to_string t) ^ (auto_to_string q);;

let auto2dot nomFich auto  = 
    let chan = open_out nomFich in
    let print_str = output_string chan in
    print_str "digraph G {\n";
  print_str (auto_to_string (auto.graphe));
  print_str (ini_to_string auto);
  print_str (fin_to_string auto);
  print_str (fini_to_string auto);
  print_str "}\n";
  close_out chan
;;
\end{lstlisting}

Commentez-les!

Ainsi, la commande \verb+auto2dot "otto1.dot" otto1;;+ produit un fichier \og point dot\fg{} que l'on peut ouvrir. Emacs se met alors en mode GraphViz. On peut compiler le fichier avec C-c c et visualiser l'automate avec C-c p.

Visualisez \verb+otto1+.


\subsection{Standardisation}

Nous    allons   dans    un   premier    temps   nous    occuper   d'une
semi-standardisation: un automate fini sera dit semi-standard s'il admet
un unique état initial.

Explorons à nouveau la documentation du module \verb+List+:

\begin{lstlisting}[caption={}]
val length : 'a list -> int
"Return the length (number of elements) of the given list."

val mem : 'a -> 'a list -> bool
"mem a l is true if and only if a is equal to an element of l."

val exists : ('a -> bool) -> 'a list -> bool
"exists  p [a1;  ...; an]  checks if  at least  one element  of the  list satisfies  the  predicate p.  That  is,  it returns  (p  a1)  || (p  a2) || ... || (p an)."

val filter : ('a -> bool) -> 'a list -> 'a list
"filter p  l returns  all the  elements of  the list  l that  satisfy the predicate p. The order of the elements in the input list is preserved."

val map : ('a -> 'b) -> 'a list -> 'b list
"List.map f [a1; ...;  an] applies function f to a1,  ..., an, and builds the  list  [f a1;  ...;  f  an] with  the results  returned by f. Not tail-recursive."

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
"List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn."

val append : 'a list -> 'a list -> 'a list
"Catenate two lists. Same function as the infix operator @. Not tail-recursive (length of the first argument). The @ operator is not tail-recursive either."
\end{lstlisting}


Comment traduiriez-vous  à l'aide de  conditionnelles et de  boucles les
fonctions \verb+exists+, \verb+filter+, \verb+map+ et \verb+fold_left+?

Comment les  traduiriez-vous à l'aide  d'un filtrage par motif  et d'une
fonction récursive?
 

Créez un test \verb+est_semi_standard+ de signature:

\verb+val est_semi_standard : automate -> bool = <fun>+.

Encore un extrait de la documentation:


\begin{lstlisting}[caption={}]
val fst : 'a * 'b -> 'a
"Return the first component of a pair."

val snd : 'a * 'b -> 'b
"Return the second component of a pair."
\end{lstlisting}

Pour simplifier  notre travail et  clarifier nos fonctions,  nous allons
utiliser les fonctions suivantes:

\begin{lstlisting}[caption={}]
let src     t = fst(fst t);;
let label   t = snd(fst t);;
let tgt     t = snd t;;
\end{lstlisting}

Que représentent-elles?



Créez  alors  un test  \verb+est_standard+  en  utilisant la  définition
complète du cours.


Créez ensuite  une fonction \verb+sous_graphe+  qui a pour  arguments un
automate et  un sous-ensemble de ses  états et qui renvoie  la partie du
graphe contenant les transitions issues des états du sous-ensemble:

\verb+automate -> etat list -> ((etat*symbole)*etat) list = <fun>+


Voici un nouvel  extrait de la documentation au sujet  d'une fonction au
nom explicite:

\begin{lstlisting}[caption={}]
val max : 'a -> 'a -> 'a
"Return the greater of the two arguments. The result is unspecified if one of the arguments contains the float value nan."
\end{lstlisting}


Que représente alors \verb+id+ dans le code suivant:

\begin{lstlisting}[caption={}]
let id = (List.fold_left max 0  auto.q) + 1
\end{lstlisting}

Vous êtes maintenant armé(e) pour créez une fonction \verb+standard+ qui
va standardiser un automate donné en argument et dont la signature est:


\verb+- : automate -> automate = <fun>+.

\subsection{Opérations rationnelles}


Un nouvel extrait de la doc:


\begin{lstlisting}[caption={}]
val combine : 'a list -> 'b list -> ('a * 'b) list
"Transform a pair of lists into a list of pairs: combine [a1; ...; an] [b1; ...; bn] is [(a1,b1); ...; (an,bn)]. Raise Invalid_argument if the two lists have different lengths. Not tail-recursive."
\end{lstlisting}


Commentez alors les fonctions suivantes:

\begin{lstlisting}[caption={}]
let mystere_1 = fun inf sup ->
  let rec mkrange_aux = fun i j acc ->
    match (i,j) with
    |(i,j) when  i>j -> acc
    |_               ->  mkrange_aux (i+1) j (i::acc)
  in mkrange_aux inf sup []
;;

let mystere2 = fun auto ->
    let new_names = List.combine auto.q (mystere_1 (1, List.length auto.q))
    in
    let new_name e = List.assoc e new_names
    in
    {
        q = (List.map new_name auto.q);
        d = (List.map new_name auto.d);
        t = (List.map new_name auto.t);
        graphe = (
            List.map (
                fun t -> ((new_name(src t), (label t)), new_name(tgt t))
            )
            auto.graphe
        )
    }
;;
\end{lstlisting}


Vous êtes maintenant prêt(e) pour l'union, la concaténation et l'étoile:

\verb+val auto_union : automate -> automate -> automate = <fun>+

\verb+val auto_concat : automate -> automate -> automate = <fun>+

\verb+val auto_star : automate -> automate = <fun>+




%%% Local Variables: 
%%% TeX-master: "Poly_automates_2012"
%%% End: 
