\chapterimage{logic}
\chaptertext{Nous essaierons dans ce chapitre de découvrir comment parler à une machine?... }
\chapter{Langages, grammaires, automates, logique}



%\section{Systèmes formels}

\section{Approche historique}

\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{turing}
\caption{A.\bsc{Turing (1912-1954)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.6cm}
\begin{minipage}[t]{\linewidth}
Les essais de formalisation de la pensée ont commencé bien avant l'apparition des
ordinateurs  (notamment avec  \bsc{Leibniz} au  XVII\ieme siècle)  mais ont
réellement  pris leur essor avec  les travaux de  \bsc{Boole} (fin du
XIX\ieme).

La période qui va surtout influencer le monde informatique se situe pendant
l'entre-deux-guerres marquée par les travaux d'Alonzo \bsc{Church}, Alan
\bsc{Turing}, Stephen \bsc{Kleene}, Haskell \bsc{Curry} entre autres car
elle marque  les prémisses de l'informatique avant  même la construction
du  premier   ordinateur:  $\lambda$-calcul,  calculabilité,  complexité
algorithmique, équivalence entre  fonctions mécaniquement calculables et
définitions formelles des fonctions récursives.

Nous n'allons pas  voguer dans les hautes sphères de la logique
mathématique et  de l'informatique théorique mais il  est important pour
un(e)  informaticien(ne) d'aborder  ces  notions de  mécanisation de  la
pensée qui sont l'essence de sa discipline.

Nous aborderons la logique
comme un exemple de système formel  que nous étudierons plus en détail à
travers la  théorie des  langages, des grammaires  et des  automates qui
sont à la base de la construction des compilateurs.  Mais pour commencer par
le commencement, nous étudierons  brièvement l'ordinateur le plus simple
qu'on puisse imaginer:  la machine de \bsc{Turing}. Nous  ferons le lien
entre  calculabilité   et  récursivité.  
\end{minipage}

\section{Les machines de \bsc{Turing}}

\subsection{Description sommaire}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{snowwhite}
%\caption{A.\bsc{Turing (1912-1954)}}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3cm}
\begin{minipage}[t]{\linewidth}
Alan \bsc{Turing} est  le véritable homme à la pomme  (dont il a utilisé
un exemplaire pour s'empoisonner) de l'informatique
car  il en  a posé  les  fondements et  non pas  exploité les  capacités
commerciales. 

En 1936,  il présente sa \og  machine\fg{} théorique afin  de donner une
définition précise du concept d'algorithme.

Il s'agit  d'un ruban ayant un  commencement mais une  longueur infinie et
qui représente la mémoire d'un ordinateur (qui, elle, est finie...).

Le ruban  est constituée  de cases pouvant  contenir un symbole.  À tout
moment, seul un nombre fini de  cases ne sont pas blanches (ou plutôt ne
contenant pas le symbole \og  blanc\fg{}). Un pointeur identifie la case
sur laquelle la machine \og travaille\fg{} à un instant donné.

Ce  que nous  appelons un  programme est  une fonction  qui  prend comme
argument le symbole pointé et le degré d'avancement du pointeur.
\end{minipage}

Commençons par un problème simple.


\subsection{Un exemple pour découvrir}


Il faut s'imaginer une machine de \bsc{Turing} comme ceci par exemple:

\begin{center}
\begin{tikzpicture}[
      start chain=1 going right,start chain=2 going below,node distance=-0.15mm
    ]
    \node [on chain=2] {Ruban};
    \node [on chain=1] at (-1.5,-.4) {};
     \node [draw,on chain=1,scale=1.18]{\footnotesize$ \varepsilon$} ;
     \node [draw,on chain=1,scale=1.05]{\footnotesize$1$} ;
     \node [draw,on chain=1,scale=1.05]{\footnotesize$0$} ;
      \node [draw,on chain=1,scale=1.05]{\footnotesize$0$} ;
     \node [draw,on chain=1,scale=1.05]{\footnotesize$1$} ;
     \node [draw,on chain=1,scale=1.05]{\footnotesize$1$} ;
     \node [draw,on chain=1,scale=1.18]{\footnotesize$ \varepsilon$} ;
    \foreach \x in {2,...,11} {
        \x, \node [draw,on chain=1,scale=1.95] {};
    } 
    \node [name=r,on chain=1] {\ldots}; 
    \node [name=k, arrow box, draw,on chain=2,
        arrow box arrows={east:.25cm, west:0.25cm}] at (-0.15,-0.8) {};    
    \node at (2,-0.9) {Tête de lecture/écriture};
    \node [on chain=2] {};
    \node [draw,on chain=2] {État $q_i$};
    \chainin (k) [join]; % Verbindung vom Programm zum Leseschreibkopf
\end{tikzpicture}
\end{center}


Un symbole  $\varepsilon$ symbolise une case \og  blanche\fg{} et occupe
la première  case. Il est  suivi par des  0 et des  1 et une  autre case
blanche marque la fin de la chaîne.

L'ensemble des symboles $\bigl\{0,1,\varepsilon\bigr\}$ forme un \textbf{alphabet}.


Le pointeur indique la première case. Nous voudrions par exemple changer
les 0 en 1 et vice-versa puis 
remettre le pointeur dans sa position initiale.

Il est  possible d'effectuer  trois actions qui  dépendent de  l'état du
pointeur et du caractère pointé:

\begin{itemize}
\item changer l'état du pointeur;
\item changer le caractère pointé sur le ruban;
\item déplacer le pointeur d'une case vers la gauche ou vers la droite.
\end{itemize}

L'algorithme est donc:

\begin{itemize}
\item lorsque le pointeur rencontre le premier blanc, il se déplace vers
  la droite;
\item chaque fois que  le pointeur rencontre un 0 ou un  1, il le change
  en son complémentaire et se déplace vers la droite;
\item lorsqu'il rencontre  le deuxième blanc, il recule  d'une case vers
  la gauche jusqu'à ce qu'il rencontre le premier blanc.
\end{itemize}

Ceci  constitue   un  algorithme   que  nous  prendrons   l'habitude  de
représenter par \textbf{l'automate} suivant:


\begin{center}\label{autoturing}
\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 {$ \varepsilon$/$ \varepsilon$,D} (B)
        (B) edge [loop above] node {1/0,D} (B)
            edge [loop below] node {0/1,D} (B)
            edge              node {$ \varepsilon$/$ \varepsilon$,G} (C)
        (C) edge [loop below] node {0/0,G} (C)
            edge [loop above] node {1/1,G} (C);
\end{tikzpicture}
\end{center}


Les cercles correspondent aux différents états  de la machine: il y en a
trois.  Les  flèches  décrivent,  elles,  les actions  accomplies  par  la
machine.

La flèche entrante en $ q_0$  indique qu'il s'agit de l'état initial. Le
double cercle autour de $ q_2$ indique qu'il s'agit de l'état final.

Une  flèche allant  de $q_i$  à $  q_j$ surmontée  d'un couple  $a/b, c$
signifie que si la machine est  dans l'état $ q_i$ et qu'elle pointe sur
une case contenant $ a$ alors elle remplace $ a$ par $ b$ et bouge d'une
case  vers la direction  indiquée par  $ c$:  Gauche, Droite,  Reste sur
place.



On voit qu'un nombre fini d'instructions permet de traiter une chaîne de
longueur aussi longue que l'on veut.

\begin{recherche}
  Testez cette machine sur la chaîne $ \varepsilon 10011\varepsilon$.
\end{recherche}





\subsection{Définitions}



\begin{definition}[Machine de \bsc{Turing}]
Une  machine de  \bsc{Turing} standard  (il en  existe d'autres)  est un
triplet:

$$M=(Q,X,\f)$$

où 
\begin{itemize}

\item Q est un ensemble fini appelé \textit{alphabet d'état};
\item  X  est un
autre ensemble fini appelé \textit{alphabet de ruban};
\item  $\f$ est  une fonction  de domaine  $D\subseteq Q\times  X$  et à
  valeurs dans $Q\times X\times  \bigl\{G,R,D\bigr\}$ avec $G$, $R$, $D$
  les options du mouvement du pointeur (gauche, reste immobile, droite).
\end{itemize}

On choisira en général Q et  X de telle sorte que leur intersection soit
vide.
Quelques éléments particuliers:
\begin{itemize}
\item $q_o\in Q$ est l'\textit{état initial};
\item $Q_f\subseteq Q$ est l'\textit{ensemble des états finaux};
\item $\varepsilon\in X$ est le symbole blanc.
\end{itemize}
\end{definition}




Cela    donne,    avec    les    données   de    l'exemple    précédent,
$Q=\bigl\{q_0,q_1,q_2\bigr\}$,                  $X=\bigl\{\e,0,1\bigr\}$,
$Q_f=\bigl\{q_2\bigr\}$ et  la fonction  $ \f$ est  définie à  l'aide du
tableau suivant:


\begin{center}
             \begin{tabularx}{0.5\linewidth}{Y{2}}
	     \whline
             $ \f(q_i,x)$& $ q_0$& $ q_1$ & $ q_2$\\
             \whline
             $ \e$& $ (q_1,\e,D)$& $ (q_2,\e,G)$& \\
             \hline
             0 & & $ (q_1,1,D)$& $ (q_2,0,G)$\\
             \hline
             1 & & $ (q_1,0,D)$& $ (q_2,1,G)$\\

             \whline
             \end{tabularx}
             \end{center}


En  fait,  une  machine  de  \bsc{Turing}  agit  sur  des  \textit{mots}
construits à partir  d'un \textit{alphabet}. Un alphabet est  en fait un
ensemble fini. Définissons un peu mieux ce que peut être un mot:


\begin{definition}
Soit  X  un  alphabet.  Soit  $  \lambda$ le  mot  ne  comportant  aucun
caractère. L'ensemble $  X^*$ des mots construits avec  l'alphabet X est
défini par:
\begin{enumerate}
\item $ \lambda \in X^*$;
\item si $  a\in X$ et $ m\in  X^*$, alors le mot construit  à partir de
  $m$ en ajoutant $a$ à droite est un mot de $ X^*$;
\item $\mu$  est un élément de  $X^*$ seulement s'il peut  être obtenu à
  partir de $\lambda$ par application de l'étape 2 un nombre fini de fois.
\end{enumerate}
\end{definition}







On peut donc à l'aide de  cette définition construire un mot en ajoutant
un  par  un des  éléments  de l'alphabet.  Nous  devons  donc créer  une
fonction plus rapide pour créer des mots:

\begin{definition}[Concaténation]
Soient $m_1$ et  $m_2$ deux mots de $X^*$.  La \textbf{concaténation} de
ces deux mots est le mot $  m_1m_2\in X^*$ obtenu en écrivant $m_2$ à la
suite de $ m_1$.
\end{definition}


\subsection{Fonctions MT-calculables}


La notion  de fonction calculable  par une fonction de  \bsc{Turing} est
primordiale en informatique. Une telle fonction sera dite \textbf{MT-calculable}.


Cette notion peut  paraître assez abstraite alors mieux  vaut étudier un
exemple avant de l'affronter.

Par  exemple, nous  allons construire  une machine  de  \bsc{Turing} qui
calcule le successeur de la représentation unaire d'un entier.

\begin{definition}[Représentation unaire d'un entier]
Un nombre  entier $n\in  \bbn$ a pour  représentation unaire  $ 1^{n+1}$
c'est-à-dire  la  concaténation  de   $n+1$  symboles  de  l'alphabet  $
X=\bigl\{1\bigr\}$.

Ainsi, la représentation de  0 est 1, celle de 1 est  11, celle de 2 est
111, etc.

On notera $ \overline{n}$ la représentation de l'entier $n$.
\end{definition}


Ainsi, le successeur  de $n$ est obtenu en ajoutant un  1 à son écriture
unaire.

Décrivons une machine de \bsc{Turing} qui calcule cette fonction:
\begin{itemize}
\item la fonction successeur  $s$ est définie sur $D=\bigl\{\lambda,\e 1
  \e, \e 11 \e, \e 111\e,...\bigr\}$:  l'entrée sur le ruban est donc la
  représentation unaire du
  nombre $n$  précédée du symbole $  \e$, toutes les  autres cases étant
  occupées par des $ \e$;
\item l'alphabet de ruban est $ X=\bigl\{1,\e\bigr\}$;
\item l'alphabet d'état est $ \bigl\{q_0,q_1,q_2\bigr\}$;
\item $Q_f=\bigl\{q_2\bigr\}$;
\item la fonction $\f$ est décrite par l'automate suivant:
\end{itemize}




\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 {$ \varepsilon$/$ \varepsilon$,D} (B)
        (B) edge [loop above] node {1/1,D} (B)
            edge              node {$ \varepsilon$/1,G} (C)
        (C)  edge [loop above] node {1/1,G} (C);
\end{tikzpicture}
\end{center}


La configuration initiale est le mot $ q_0\e \overline{n}\e$.

Le  pointeur rencontre  le premier  blanc et  change donc  d'état  et se
dirige vers la droite jusqu'à rencontrer un deuxième blanc qui est alors
remplacé  par un  1. Le  pointeur change  d'état et  se déplace  vers la
gauche tant qu'il pointe sur un 1. 

La  machine s'arrête  lorsqu'elle rencontre  à  nouveau un  blanc car  $
\f(q_2,\e)$ n'est pas définie.



La configuration finale est $ q_2\e \overline{n}1\e$.

Cela  vous  aidera alors  peut-être  à  comprendre  la définition  d'une
fonction MT-calculable:

\begin{definition}[Fonction MT-calculable]
Soit  $f~: D\subseteq  X^* \to  X^*$  une fonction  et $M=(Q,X,\f)$  une
machine de \bsc{Turing}. M calcule $f$ si:
\begin{itemize}
\item  il existe  une unique  transition de  $q_0$ et  que sa  forme est
  $\f(q_0,\e)=(q_i,\e,D)$  avec $q_i\neq  q_0$ (\textit{il  faut quitter
    l'état initial à partir de $ \e$});
\item il n'existe pas de  transition de la forme $ \f(q_i,x)=(q_0,x',m)$
  avec  $i\neq   0$,  $(x,x')\in  X^2$   et  $m\in  \bigl\{G,R,D\bigr\}$
  (\textit{il ne faut pas revenir à l'état initial});
\item  il  n'existe pas  de  transition de  la  forme  $ \f(q_f,\e)$  où
  $q_f\in Q_f$ (\textit{il ne faut pas que la machine continue à
    fonctionner dans son  état final en présence d'un blanc  car il y en
    a une infinité et la machine ne s'arrêterait jamais});
\item pour tout $\mu in  D$, notons $\nu=f(\mu)$. Le calcul effectué par
  la machine M  en partant de la configuration initiale  $ q_0\e \mu \e$
  s'arrête après un nombre fini  d'étapes dans la configuration finale $
  q_f\e \nu \e$ (\textit{la machine doit calculer $ f(\mu)$});
\item  le  calcul  ne  s'arrête  jamais si  $\mu\not\in  D$  (\textit{la
    machine ne calcule $ f(\mu)$ que si ce nombre est défini}).
\end{itemize}
  
\end{definition}


Nous définirons en TD:

\begin{itemize}
\item la fonction identiquement nulle;
\item la fonction addition;
\item les fonctions projections:
$$\pi_i^{(n)}(x_1,x_2,...,x_n)=x_i,\quad 1 \leqslant i \leqslant n$$
\end{itemize}


\subsection{Fonctions récursives}


Nous avons découvert des  fonctions MT-calculables. Pour arriver jusqu'à
la thèse de \bsc{Church-Turing}, il faudrait déterminer quelles sont les
fonctions qui sont MT-calculables.

Nous allons  montrer qu'il s'agit des fonctions  récursives dont l'étude
est donc indispensable pour étudier l'algorithmique...

\subsubsection{Fonctions primitives récursives}

Les  fonctions de  base  des fonctions  primitives  récursives sont  les
fonctions précédemment étudiées:

\begin{itemize}
\item la fonction successeur $s$: $ s(x)=x+1$;
\item la fonction identiquement nulle $z$: $ z(x)=0$;
\item les fonctions projection $ \pi_i^{(n)}$.
\end{itemize}


Nous appellerons \textbf{fonction arithmétique} une fonction de $\bbn^k$
dans $\bbn$.

Les  fonctions de  base  sont MT-calculables.  Nous  admettrons que  les
fonctions arithmétiques  obtenues par composition et  récurrence le sont
aussi, en définissant ces opérations ainsi:

\begin{definition}[Composition de fonctions arithmétiques]
Soient $ g_1,g_2,...,g_k$ $k$  fonctions arithmétiques de $k$ variables
et $h$ une fonction arithmétique  de $k$ variables. Soit $f$ la fonction
définie par:

$$f(x_1,x_2,...,x_n)=h(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n))$$
alors   $f$  est   appelée  la   \textbf{composition}  de   $h$   et  de
$g_1,g_2,...,g_n$ et se note:

$$f=h\circ (g_1,g_2,...,g_n)$$

\end{definition}


Par    exemple,    si    $h(x_1,x_2)=s(x_1)+s(x_2)$,   $g_1(x)=2x$    et
$g_2(x)=x^2+37$ alors:

$$f(x)=$$




\begin{definition}[Récurrence]
  Soient $g$ et $h$ des  fonctions arithmétiques totales de $n$ et $n+2$
  variables respectivement.  La fonction $f$ de  $n+1$ variables définie
  par:

  \begin{itemize}
  \item $ f(x_1,...,x_n,0)=g(x_1,...,x_n)$;
\item $ f(x_1,x_n,y+1)=h(x_1,...,x_n,y,f(x_1,x_2,...,x_n,y))$,
  \end{itemize}
 est   appelée  \textbf{récurrence   de  base   \textit{g}  et   de  pas
   \textit{h}}.

On conviendra qu'une fonction de zéro variable est constante.
\end{definition}




On peut alors définir les fonctions récursives primitives:

\begin{definition}[Fonctions récursives primitives]
Une fonction est \textbf{primitive  récursive} si elle peut être obtenue
à   partir   des   fonctions   \textit{successeur},   \textit{zéro}   et
\textit{projection} par  l'application d'un nombre  fini de compositions
et de récurrences.
\end{definition}



Par exemple, il est possible de définir l'addition de deux entiers à partir de la
fonction $s$, des projections $  \pi_1^{(1)}$ et $ \pi_3^{(3)}$ et d'une
récurrence   de   base  $g(x)=\pi_1^{(1)}(x)$   et   de  pas   $h=s\circ
\pi_3^{(3)}$:

$$
\begin{cases}
  \add(m,0)=g(m)=m\\
\add(m,n+1)=h(m,n,add(m,n))=s(add(m,n))
\end{cases}
$$


Nous  verrons  en exercice  quelques  exemples  de fonctions  primitives
récursives.

Cependant,  certaines fonctions  ne le  sont  pas comme  par exemple  la
fonction d'\textsc{Ackermann}:

$$
\begin{cases}
  A(0,y)=y+1\\
A(x+1,0)=A(x,1)\\
A(x+1,y+1)=A(x,A(x+1,y))
\end{cases}
$$

qui est cependant MT-calculable mais la preuve est hors de notre portée.



\subsubsection{La thèse de \bsc{Church-Turing}}


Si  nous  avions  un peu  plus  de  temps,  nous pourrions  définir  les
fonctions  récursives  (comme   par  exemple  les  fonctions  primitives
récursives et  la fonction d'\bsc{Ackermann}) et montrer  que toutes les
fonctions récursives sont MT-calculables.

% Mais ce qui  est plus fort c'est que  la condition nécessaire précédente
% est aussi suffisante.

% Ainsi,  une   fonction  est  calculable  s'il  existe   une  machine  de
% \textsc{Turing} pour la calculer.

% Le problème,  c'est qu'on ne sait toujours  pas définir mathématiquement
% ce qu'est la calculabilité et donc la notion d'algorithme.


Ainsi les travaux de \textsc{Turing} tendant à définir un critère de \og
calculabilité\fg{} par une machine (ou  un être humain muni d'une feuille
et d'un  crayon) rejoignent  ceux de \textsc{Church}  et \textsc{Kleene}
sur le $\lambda$-calcul ou, ce qui revient au même, les fonctions récursives
(notion introduite par \textsc{Gödel} au même moment).

C'est  un  domaine d'étude  fort  paradoxal:  techniquement réduit  (les
machines de \textsc{Turing} sont simples à décrire!), il entraîne depuis
80 ans des recherches fort ardues.


Il faut  cependant garder  en tête que  les machines  de \textsc{Turing}
sont des \og humains qui calculent\fg{} comme le formulera le philosophe
\textsc{Wittgenstein}  et évidemment  \textsc{Turing}  lui-même: \og  un
être humain  muni d'un papier, d'un  crayon, d'un ruban et  soumis à une
stricte discipline est en fait une machine universelle\fg{}.

Comme  tous  nos ordinateurs  \textit{actuels}  sont  équivalents à  des
machines de \textsc{Turing}, ils sont donc également des modèles d'êtres
humains en train d'effectuer des calculs de manière disciplinée mais non
intelligente.

Cette  notion est  fondamentale également  du côté  matériel et  du côté
logiciel. Un  ordinateur est une machine de  \textsc{Turing} car, pourvu
qu'on lui donne un bon code, il effectuera ce que vous voulez.

Le programmeur est lui-même une  machine de \textsc{Turing} s'il a écrit
son programme (et prouvé qu'il fonctionne...).

Un langage est une machine de \textsc{Turing}.

L'architecture  même  de  l'ordinateur  fonctionne  selon  ce  principe:
données  et  instructions  sont  de  même  nature  dans  la  mémoire  de
l'ordinateur   comme   nombres  et   fonctions   dans   la  machine   de
\textsc{Turing}.

Cependant, les  machines de \textsc{Turing} sont  des modèles théoriques
(ruban  infini) et  donc éloignés  du quotidien  du  programmeur. Savoir
qu'il  existe un  algorithme qui  résout notre  problème est  une chose,
connaître sa complexité en est  une autre...L'étude de la complexité des
algorithmes est un domaine de recherche en soi.

Mais  \textsc{Turing} aura  surtout  lancé le  débat sur  l'intelligence
artificielle: est-ce  qu'une machine sera  un jour capable  de raisonner
comme un cerveau humain? Il avait proposé un test: entamer un dialogue à
distance avec  une \og entité\fg{} qui  peut être un être  humain ou une
machine.  Lorsque le comportement  de la  machine sera  indiscernable de
celui de l'être humain par ce test, alors on pourra considérer la machine
aussi intelligente que l'être humain.


Cette  évolution   passera  peut-être  par   une  remise  en   cause  de
l'ordinateur électronique:  des essais d'ordinateur à ADN  sont en cours
depuis une quinzaine  d'années par exemple mais leur  base théorique est
toujours la machine de \textsc{Turing}...








Pour finir, une nouvelle citation de Donald E. \textsc{Knuth}:

\begin{quote}
  {\itshape 
Science is what we understand well  enough to explain to a computer. Art
is everything else we do.  
}
\end{quote}



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 etc.
\end{itemize}


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$, etc.

\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 $ \lambda_A$ la \textit{chaîne vide} (ne comportant aucun
symbole). 

L'ensemble $ A^*$ des chaînes construites avec l'alphabet A est
défini par:
\begin{enumerate}
\item $ \lambda_A \in A^*$;
\item si $ a\in A$ et $ c\in A^*$, alors la chaîne construite à partir de
  $c$ en concaténant $a$ à droite est une chaîne de $ A^*$;
\item $\mu$  est un élément de  $A^*$ seulement s'il peut  être obtenu à
  partir de $\lambda_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 $|\lambda_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\{\lambda_A\bigr\}$ qui n'est donc pas vide.

$A^*  = \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^*$ 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^*$
car en concaténant deux éléments  de $A^*$, on obtient encore un élément
de $A^*$.

Cette  loi  est  également  associative et  possède  un  \textit{élément
  neutre}   $\lambda$.   Cela   confère   à  $A^*$   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}=%
\lambda $ pour tout $a$ \'{e}l\'{e}ment de $A.$



\begin{definition}
\begin{itemize}
\item   On dit que $\mu\in A^*$ est un \textit{préfixe} de $\nu\in A^*$ si, et
  seulement si, il existe $\xi\in A^*$ telle que $\nu = \mu\xi$.  Si
  $\xi\neq\lambda$, on dit que $\mu$ est un \textit{préfixe propre} de $\nu$.
\item On dit que $\mu\in A^*$ est un \textit{suffixe} de $\nu\in A^*$ si, et
  seulement si, il existe $\xi\in A^*$ telle que $\nu = \xi\mu$.  Si
  $\xi\neq\lambda$, on dit que $\mu$ est un \textit{suffixe propre} de $\nu$.
\item On dit que $\mu\in A^*$ est un \textit{facteur} de $\nu\in A^*$ si, et
  seulement si, il existe $\xi\in A^*$ et $xi'\in A^*$ telles que $\nu = \xi\mu\xi'$.  Si
  $(\xi,\xi')\neq(\lambda,\lambda)$,   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^*$.
\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\{ \lambda\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\{ \lambda%
,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\{ \lambda\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\{ \lambda\right\} $ alors $L^{\ast }=\left\{ \lambda%
\right\} .$ Si $L=\varnothing $ alors $L^{\ast }=\left\{ \lambda\right\} $
puisque nous avons d\'{e}cid\'{e} (par convention) que, pour tout langage $%
L, $ nous avions $L^{0}=\left\{ \lambda\right\} .$

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

\item $L^{\ast }=L^{+}\cup \left\{ \lambda\right\} =L^{+}+\left\{ \lambda\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\{\lambda_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 et lançons la commande suivante:

\shell
\begin{lstlisting}
$ egrep rationnel* ./logic.tex 
\end{lstlisting}


On obtient:

\begin{lstlisting}[caption={}]
l'inventeur du concept d'expression  ?\textbf{rationnel}!le et de langage ?\textbf{rationnel}!
sentation des expressions ?\textbf{rationnel}!les.
\subsection{Langages et expressions ?\textbf{rationnel}!s (ou réguliers)}
\subsubsection{Langage ?\textbf{rationnel}!}
\begin{definition}[Langage ?\textbf{rationnel}! (ou régulier)]
Soit L un langage sur l'alphabet  A. Il est dit ?\textbf{rationnel}! s'il peut être
C'est  donc un langage  ?\textbf{rationnel}! car  obtenu à  partir de  singletons et
d'opérations ?\textbf{rationnel}!les.
  \item Tout langage \textbf{fini} est ?\textbf{rationnel}!.
\item Si L est ?\textbf{rationnel}!, alors $L^\star$ est ?\textbf{rationnel}!.
\item Si $L_1$ et $L_2$ sont ?\textbf{rationnel}!s, alors $L_1+L_2$ et $L_1L_2$ sont ?\textbf{rationnel}!s
\end{lstlisting}

On obtient alors toutes les lignes où apparaît une chaîne de préfixe \og
rationnel\fg{} dans le début du  fichier source \LaTeX{} de ce document,
celle-ci étant mise en gras.

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 $\lambda_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( \lambda_A\right) =\left\{ \func{\lambda_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} exclusif. 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
$\lambda$, 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\lambda=\lambda
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( 
\lambda+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\{ \lambda\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,\varphi$:
\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 \{\lambda\}\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 $\lambda$ 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 {$\lambda$} (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 {$\lambda$} (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 {\lambda}\lambda^\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 {$\lambda$} (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 {$\lambda$} (E);
\end{tikzpicture}
\end{center}

\item   on     élimine     l'état      $q_1$:     $L_{d02}=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 {$\lambda$} (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 {$\lambda$} (E);
\end{tikzpicture}
\end{center}


\item   on     élimine     l'état      $q_2$:     $L_{dt}=L_{dt}\cup
  L_{d2}L_{22}^\star L_{2t}=\emptyset \cup ab^\star cd^\star\lambda=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 {$\lambda$} (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 {$\lambda$} (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 é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{}.



\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{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{Glushkov}}

La méthode  suivante est  attribuée à l'informaticien  soviétique Viktor
\textsc{Glushkov}  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 $\lambda$ 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 à états finis avec sortie}

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...

\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...


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\{ \lambda \right\} \right)
\right) \times \left( A\cup \left\{ \lambda \right\} \right) \longrightarrow E\times \left( P\cup \left\{ \lambda \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}=\lambda $ 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}=\lambda $ cela
indique que l'on n'empile rien. La possibilit\'{e} de pouvoir avoir $\alpha
_{z}=\lambda $ 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 $\lambda )$, 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}=\lambda $ 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,\lambda \right) ,a,\left( 1,u\right) \right) \\
T_{2} &:&\left( \left( 1,\lambda \right) ,a,\left( 1,u\right) \right) \\
T_{3} &:&\left( \left( 1,u\right) ,b,\left( 2,\lambda \right) \right) \\
T_{4} &:&\left( \left( 2,u\right) ,b,\left( 2,\lambda \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 ($\lambda $) 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 ($\lambda )$ 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 ($\lambda ).$

$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 ($\lambda ).$

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 {$\lambda,a,u$} (B)
       (B) edge[loop above] node {$\lambda,a,u$} (B)
       (B) edge node {$u,b,\lambda$} (C)
       (C) edge[loop above] node {$u,b,\lambda$} (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 $\lambda $ 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) ,\lambda ,\left( e_{i},\lambda \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}

\begin{quote}
\textit{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}

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






\section{Présentation générale de la logique des propositions} 

On appellera \textbf{proposition} tout  énoncé dont on peut décider s'il
est vrai ou faux indépendamment de ses composantes.

On  distinguera   la  logique  des   propositions  de  la   logique  des
\textbf{prédicats} qui  introduit des variables dans  les assertions qui
peut  les rendre  donc parfois  vraies et  parfois fausses  et  que nous
étudierons en deuxième année.


Par exemple \og \textit{Igor dort}\fg{} est une proposition susceptible d'être
vraie ou  fausse dans toute situation  alors que la valeur  de vérité de
\og \textit{x dort}\fg{} dépend de $x$.

Nous  distinguerons  également la  \textbf{syntaxe}  de  la logique  des
propositions de sa \textsc{sémantique}.

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}
  

L'étude  de  l'aspect  syntaxique   consiste  à  préciser  comment  l'on
construit les formules et l'aspect sémantique interprète les formules en
terme de \textit{Vrai} ou \textit{Faux}.

\subsection{Syntaxe}

\subsubsection{Les symboles}

L'alphabet du langage de la logique des propositions est constitué de:

\begin{itemize}
\item  un  ensemble  fini  ou infini  dénombrable  de  \textit{variables
    propositionnelles};
\item la constante logique $\bot$ qui se lit \og FAUX\fg{};
\item les \textit{connecteurs} $\lnot$ (non), $\land$ (et), $\lor$ (ou),
  $\rightarrow$ (implique) et $\leftrightarrow$ (équivalent);
\item les parenthèses \og (\fg{} et \og )\fg{}.

\end{itemize}
 

Le connecteur  $\lnot$ est un  \textit{connecteur unaire} et  les autres
sont des \textit{ connecteurs binaires}.

L'\textit{ensemble des  formules} de la logique  propositionnelle est le
plus petit ensemble $\CR F$ tel que:

\begin{itemize}
\item toute variable propositionnelle est un élément de $\FR$;
\item $\bot$ est un élément de $\FR$;
\item si $p\in \FR$, alors $(\lnot p)\in \FR$;
\item si $p$ et $q$ sont  dans $\FR$, alors $(p\land q)$, $(p\lor q)$,
  $(p \rightarrow q)$,  et $(p \leftrightarrow q)$ sont  des éléments de
  $\FR$.
\end{itemize}

Par exemple, $s\rightarrow ((p\lor (\lnot q))\lor(p\lor (\lnot r)))$ est une
proposition mais $\lnot \land(p)\lor$ ne l'est pas.

On  peut se passer  de quelques  parenthèses en  adoptant les  règles de
priorité suivantes:

\begin{itemize}
\item $\lnot$ est prioritaire sur les autres opérateurs;
\item  $\lor$   et  $\land$  sont  prioritaires   sur  $\rightarrow$  et
  $\leftrightarrow$.
\end{itemize}

Mais attention! $p\lor q\land r$ est ambigu.


\subsubsection{Démonstration par induction}


\begin{theoreme}
  Si une propriété P portant sur les formules de $\FR$ est telle que:

  \begin{itemize}
  \item toute variable propositionnelle vérifie P;
\item $\bot$ vérifie P;
\item si la formule $p$ vérifie P, alors $(\lnot p)$ vérifie P;
\item  si $p$  et  $q$ vérifient  P,  alors $(p\lor  q)$, $(p\land  q)$,
  $(p\rightarrow q)$ et $(p \leftrightarrow q)$ vérifient P;
  \end{itemize}

alors toutes les formules de $\FR$ vérifient P.
\end{theoreme}


Ce théorème permet par exemple de prouver le théorème suivant:

\begin{theoreme}
Toute  formule  de  $\FR$  a  autant de  parenthèses  ouvrantes  que  de
parenthèses fermantes.
\end{theoreme}

La preuve est laissée en exercice.

\subsubsection{Sous-formules}

Nous n'entrerons pas dans les détails mais on peut définir par induction
les sous-formules d'une formule  donnée: on retiendra juste qu'il s'agit
de toutes les formules apparaissant dans une formule donnée.

Par exemple, l'ensemble des sous-formules de $(p\rightarrow q)\lor
\lnot(q\leftrightarrow r)$ est $$\bigl\{p\rightarrow q,
\lnot(q\leftrightarrow r),q\leftrightarrow r,p,q,r\bigr\}$$


\subsection{Sémantique}


\subsubsection{Valeurs et tables de vérité}


On considère  un ensemble $\BR=\bigl\{0,1\bigr\}$  ou $\bigl\{F,V\bigr\}$ ou
$\bigl\{{\rm Oui},{\rm Non}\bigr\}$, etc.


\begin{definition}
Une \textit{distribution des valeurs  de vérité} est une application $v$
de $\FR$ dans $\BR$ définie inductivement par:

\begin{itemize}
\item $v(\bot)=0$,
\item $v(\lnot p)=1$ si, et seulement si, $v(p)=0$;
\item $v(p\land q)=1$ si, et seulement si, $(p)=v(q)=1$;
\item $v(p\lor q)=0$ si, et seulement si, $v(p)=v(q)=0$;
\item $v(p \rightarrow q)=0$ si, et seulement si, $v(p)=1$ et $v(q)=0$;
\item $v(p\leftrightarrow)=1$ si, et seulement si, $v(p)=v(q)$,
\end{itemize}

avec $p$ et $q$ des éléments quelconques de $\FR$.
\end{definition}


% Cette  définition   permet  d'établir  les   \textit{tables  de  vérité}
% suivantes:

% puis de généraliser à n'importe quelle formule:









































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

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


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

\small
\begin{listeexercices}


\subsection{Machines de \bsc{Turing}}






\begin{exercice}
  On  considère la  machine  de \bsc{Turing}  représentée par  l'automate
    ci-dessous   qui   est   dans   l'état  initial   $   q_0\varepsilon
    1111\varepsilon   111111    \varepsilon   111111   \varepsilon   111
    \varepsilon 1111 \varepsilon 111011 \varepsilon$:



{\small


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,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] (C) [ right of=B] {$q_2$};
  \node[state,accepting]         (D) [ right of=C] {$q_3$};
 
  \path (A) edge              node {$ \varepsilon$/$ \varepsilon$,D} (B)
        (B) edge [loop above] node {1/1,D} (B)
            edge node {$ \varepsilon$/$ \varepsilon$,D} (C)
(C) edge [loop above] node {1/1,D} (B)
            edge node {$ \varepsilon$/$ \varepsilon$,D} (D)
        (D)  edge [loop above] node {1/1,D} (D);
\end{tikzpicture}
\end{center}


}

Quelle est la configuration finale de la machine?
\end{exercice}











\begin{exercice}
Quelle est la configuration finale de la machine de \bsc{Turing} décrite
par l'automate 
suivant  sachant   que  la  configuration   initiale  du  ruban   est  $
q_0\varepsilon    \overline{x}\varepsilon$   (on    rappelle    que   la
représentation unaire d'un nombre $x$ est noté $ \overline{x}$):





{\footnotesize
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=1.6cm,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] (C) [ right of=B] {$q_2$};
\node[state]         (E) [ right of=C] {$q_3$};
  \node[state,accepting]         (F) [ right of=E] {$q_4$};
 
  \path (A) edge              node {$ \varepsilon$/$ \varepsilon$,D} (B)
        (B) %edge [loop above] node {1/0,D} (B)
            %edge [loop below] node {0/1,D} (B)
            edge              node {$1$/$1$,D} (C)
        (C) %edge [loop below] node {0/0,G} (C)
            edge [loop above] node {1/$ \varepsilon$,D} (C)
            edge node {$ \varepsilon$/$ \varepsilon$,G} (E)
         (E)  edge [loop above] node {$ \varepsilon$/$ \varepsilon$,G} (E)
            edge node {1/1,G} (F);
\end{tikzpicture}
\end{center}
}
\end{exercice}











% \begin{exercice}
%   Construire une machine de \bsc{Turing}  qui recopie un nombre unaire à
%   sa  suite en  laissant  un blanc  entre  les deux  et  en ramenant  le
%   pointeur avant le premier nombre.
% \end{exercice}

\begin{exercice}
  Construire une machine de \bsc{Turing} qui calcule la fonction prédécesseur.
\end{exercice}

\begin{exercice}
Comment  s'écrit  0  en   système  unaire?  Construire  une  machine  de
\bsc{Turing}   qui   calcule  la   fonction   identiquement  nulle:   la
configuration  initiale est $q_0\varepsilon  \overline{x}\varepsilon$ et
la configuration finale est $q_f\varepsilon 1 \varepsilon$
\end{exercice}


\begin{exercice}
  Nous allons  construire une  machine à additionner.  En base  1, c'est
  assez simple: écrivez l'addition en base 1 de 4 et 1 puis de 4 et 0.

On    suppose    qu'on    a    marqué   en    entrée    $    \varepsilon
\overline{x}\varepsilon\overline{y}\varepsilon$ avec $x$ et $y$ les deux
nombres à additionner.

La     configuration     finale     attendue     est     $q_f\varepsilon
\overline{x+y}\varepsilon$.


\end{exercice}






\begin{exercice}
  
Voici les codes ASCII décimaux de quelques caractères affichables:


\begin{center}
%\begin{table}[h!]
{\scriptsize



\begin{tabularx}{\linewidth}{Il*{10}{|X}I}
\hline
Caractère& A & B & C & D & E &F & G & H & I & J\\
\hline
Code & 65 & 66 & 67 & 68 & 69&70 & 71 & 72 & 73 & 74\\
\hline
\end{tabularx}






\begin{tabularx}{\linewidth}{Il*{10}{|X}I}
\hline
Caractère&  a & b & c & d & e & f & g & h & i & j \\
\hline
Code & 97 & 98 & 99 & 100 & 101 & 102 & 103 & 104 & 105 & 106  \\
\hline
\end{tabularx}


}
%\caption{Table des caractères ASCII affichables}
%\end{table}

\end{center}

\begin{enumerate}
\item Écrire les valeurs  en base 2 des codes de A, B et  C puis a, b et
  c.
\item Déterminer un automate décrivant une machine de \textsc{Turing} la
  plus simple possible 
  qui transforme le code ASCII (en binaire) d'une lettre minuscule en le
  code ASCII (en binaire toujours) de la majuscule correspondante.
\end{enumerate}


\end{exercice}





\subsection{Fonctions récursives}

\sage

\begin{exercice}

Soit $g$ la fonction  projection $\pi_1^{(1)}$ et $h=s\circ \pi_3^{(3)}$
avec $s$ la fonction successeur.

  Soit $f$ la récurrence de base $g$ et de pas $h$ définie sur $\bbn^2$.

Calculer  $f(0,0)$, $f(0,1)$,  $f(1,1)$,  $f(2,1)$, $f(1,2)$,  $f(4,2)$,
$f(2,4)$.

A-t-on $f(x,y)=f(y,x)$ pour tout couple $(x,y)$ d'entiers?
\end{exercice}



\begin{exercice}\label{exo::pyt_1}
Voici quelques fonctions écrites sous Python:

\begin{lstlisting}[caption={}]
def succ(x):
    return x+1

def pred(x):
    if x == 0:
        return 0
    else:
        return x-1


def pi(k,T):
    return T[k-1]


def g(x):
    return x

def h(T):
    return succ(pi(3,T))


def A(x1,x2):
    if x2 == 0:
        return g(x1)
    else:
        return h([x1,x2,A(x1,pred(x2))])
\end{lstlisting}


Que va retourner \lstinline+A(2,3)+? 

De quels types sont les arguments \verb+x+, \verb+T+, \verb+x1+ dans les
différentes fonctions ci-dessus?


\end{exercice}



\begin{exercice}
Soit   $g$  la  fonction   identiquement  nulle   et  $h$   définie  par
$h(x,y,z)=add(\pi_1^{(3)}(x,y,z),\pi_3^{(3)}(x,y,z))$    avec   add   la
fonction d'addition définie en cours.

  Soit $f$ la fonction définie sur $\bbn^2$ par:

$$
\begin{cases}
  f(x,0)=0\\
f(x,y+1)={\rm add}(x,f(x,y))
\end{cases}
$$


Montrer que $f$ peut être définie  comme la récurrence de base $g$ et de
pas $h$ avec  $g$ et $h$ des fonctions  primitives récursives définies à
partir des fonctions de base. 




Calculer  $f(0,0)$, $f(0,1)$,  $f(1,1)$,  $f(2,1)$, $f(1,2)$,  $f(4,2)$,
$f(2,4)$.

Que pensez-vous de $f$?

\end{exercice}



\begin{exercice}
  On définit sur Python une  nouvelle fonction à partir de la définition
  vue  à l'exercice  précédent  et  de la  fonction  \verb+A+ définie  à
  l'exercice \vref{exo::pyt_1}:

  \begin{lstlisting}[caption={}]
def M(x1,x2):
    if x2 == 0:
        return 0
    else:
        return A(x1,M(x1,pred(x2)))
  \end{lstlisting}


Que pensez-vous de la fonction suivante:


\begin{lstlisting}[caption={}]
def E(x1,x2):
    if x2 == 0:
        return 1
    else:
        return M(x1,E(x1,pred(x2)))
\end{lstlisting}


On peut continuer ainsi:


\begin{lstlisting}[caption={}]
def T(x1,x2):
    if x2 == 0:
        return 1
    else:
        return E(x1,T(x1,pred(x2)))
\end{lstlisting}

Comment écririez-vous \verb+T(2,4)+? Quel nombre va renvoyer Python?



Remarque:{\itshape
quand on passe sur machine, on  atteint vite les limites de Python quant
au  nombre   de  récursions,  même  en  augmentant   cette  limite  avec
\verb+setrecursionlimit(10000)+ par exemple.

Pour travailler confortablement avec des fonctions récursives, on peut
employer  des  langages  pour  qui  ce mode  de  programmation  est  \og
naturel\fg{} comme Caml, Scheme, Haskell.

}
 
\medskip

\begin{minipage}[t]{0.25\linewidth}
   \includegraphics[width=2.5cm]{knuth}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.7\linewidth}\vspace{-3.8cm}
  \hspace{5.5cm} 
 % \begin{flushright}

   On  peut itérer ce  genre de  construction pour  obtenir la  famille des
puissances itérées  de \textsc{Knuth}, du nom du  célébrissime auteur de
\textit{The  Art of  computer programming}  et du  langage  \TeX{} entre
autres...

Quelques citations:

\textit{Computer programming  is an art, because  it applies accumulated
  know-}
\end{minipage}

 {\itshape ledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better. }

Ou encore:

\textit{The psychological profiling [of a programmer] is mostly the ability to shift levels of abstraction, from low level to high level. To see something in the small and to see something in the large.}

On utilise en général les notations suivantes:

$$    a\uparrow^n b= \left\{ \begin{matrix} a^b\qquad\qquad\qquad\qquad&&\mbox{si }n=1\quad\\ 1\qquad\qquad\qquad\qquad\ &&\mbox{si }b=0\quad\,\\ a\uparrow^{n-1}(a\uparrow^n(b-1))&&\mbox{sinon}\ \, \end{matrix} \right. 
$$

 %\end{flushright}






\end{exercice}



\begin{exercice}
Montrer   que   la  fonction   $f:   \bbn^2   \to   \bbn$  définie   par
$f(x,y)=xy+3x^2+1$ est primitive récursive.
\end{exercice}




\begin{exercice}
Définissez récursivement la fonction sgn  définie sur $\bbn$ et qui vaut
0 en 0 et 1 sinon.

Définissez récursivement la fonction cosgn  définie sur $\bbn$ et qui vaut
1 en 0 et 0 sinon.

Définissez récursivement la soustraction propre définie sur $\bbn$ par:

$$
\begin{cases}
  {\rm sous}(x,y)=x-y \quad \text{si } x \geqslant y\\
 {\rm sous}(x,y)=0 \quad \text{si } x < y
\end{cases}
$$

à l'aide de la fonction pred. 


Montrez alors que les tests $(x<y)$, $(x>y)$ et $x=y$ sont des fonctions
primitives récursives en utilisant sgn, cosgn, sous et add.
\end{exercice}


\begin{exercice}
  \begin{enumerate}
  \item Calculez quelques termes de la suite d'\textsc{Ackermann}.
\item   Proposez  une  fonction   Python  traduisant   littéralement  la
  définition récursive de  la fonction d'\textsc{Ackermann}. Placez-y un
  \og espion \fg{} qui compte  le nombre d'appels. Testez sur l'image de
  $(3,6)$.
\item Commentez le programme suivant:
  \begin{lstlisting}[caption={}]
def f(a,b):
    global espion
    espion += 1
    while a > 0:
        if b == 0:
            b = 1
        else:
            b = f(a, b - 1)
        a -= 1
    return b + 1
  \end{lstlisting}
\item Démontrer (éventuellement par récurrence) que:
  \begin{enumerate}
  \item $A(0,n)=n+1$
\item $A(1,n)=n+2$
\item $A(2,n)=2n+3$
\item $A(3,n) =2^{n+3}-3$
  \end{enumerate}
\item  Utilisez tous ces  résultats afin  d'obtenir une  fonction Python
   plus  efficace. Par exemple, calculez  $A(4,2)$. Comme Python
  va  calculer avec  des  grands entiers,  vous  utiliserez la  commande
  \verb+long+:

  \begin{lstlisting}[caption={}]
>>> A(long(4),long(2))
  \end{lstlisting}

Vous  vérifierez que  $A(4,2)$ est  un nombre  dont  l'écriture décimale
comporte $\numprint{19729}$ caractères...

Quel  est  le  lien   entre  la  fonction  d'\textsc{Ackermann}  et  les
puissances itérées  de \textsc{Knuth}? Comment  alors exprimer $A(4,n)$,
$A(5,n)$, etc. à l'aide des puissances itérées  de \textsc{Knuth}?

  \end{enumerate}
  
\end{exercice}




\vfill
\eject




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

\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\{ \lambda\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^*$.

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 $\lambda_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 $\lambda\in \mu^{-1}L\Leftrightarrow \mu\in L.$

\item D\'{e}terminer $\lambda^{-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 }+\lambda=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}
  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  $\lambda$\   d\'{e}signe  la  chaîne   vide.  Expliquez  pourquoi
  $\lambda$ 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 à états finis avec sortie}


\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=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) [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 above] node {1,1} (B)
       (B) edge [bend left] node {0,1} (C)
       (C) edge [bend left] node {0,1} (B)
       (C) edge [loop below] node {0,0} (C)
       (A) edge node {0,0} (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,\lambda \right) ,a,\left( s,A\right)
\right) $

\item $T_{2}=\left( \left( s,\lambda \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,\lambda \right)
\right) $

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

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

\item $T_{10}=\left( \left( t,B\right) ,b,\left( t,\lambda \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 $aaa\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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{listeexercices}
\modenormal % restaure les définitions de sections, sous-sections, etc;
%%% Local Variables: 
%%% TeX-master: "PolyInfo1"
%%% End: 
