\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}
\usepackage[beamer,utf8,fourier]{preambuleTrm}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido,colortbl}
\usepackage{xlop}
\usepackage{tkz-graph,tkz-berge}
\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes.arrows,chains,positioning}
\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}

%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]

\usepackage{algo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}

\newcommand\nor{\downarrow}
\newcommand\nand{\mid}


\newcommand\blanc{ \square{} }



\newcommand\vide{\mathds{1}}



\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}


\graphicspath{{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}}




\lstset{numbers=none,language=caml,xleftmargin=10pt,%
keywordstyle =\small\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\small\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape\color{black!50!white},breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}





\setcounter{tocdepth}{2} %\setcounter{page}{0}


\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}


\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{elephantbird}



\begin{document}


\title[] % (optional, use only with long paper titles)
{Machines de \bsc{Turing}, langages, automates, grammaires}

\subtitle{INFO1 - Semaines 43 à 2}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{\textsc{IUT} de Nantes - Dpt d'informatique }% (optional, but mostly needed)

\logo{\includegraphics[scale=0.15]{logo_iut}}

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{Dernière mise à jour: \today}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }


\beamerdefaultoverlayspecification{<+->}

\AtBeginSubsubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}




\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection]
       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}







\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{multicols}{2} 
 \tableofcontents
\end{multicols}
}

 
 \end{frame}






\section{Approche historique}



\begin{frame}
  \begin{center}
    
\begin{figure}
\begin{center}
  \includegraphics[height=0.75\textheight]{godel}
\end{center}\caption{Kurt \bsc{Gödel (1906-1978)}}
\end{figure}

  \end{center}
\end{frame}



\begin{frame}
  \begin{center}
    
\begin{figure}
\begin{center}
  \includegraphics[height=0.75\textheight]{church}
\end{center}\caption{Alonzo \bsc{Church (1903-1995)}}
\end{figure}

  \end{center}
\end{frame}



\begin{frame}
  \begin{center}
    
\begin{figure}
\begin{center}
  \includegraphics[height=0.75\textheight]{kleene}
\end{center}\caption{Stephen \bsc{Kleene (1909-1994)}}
\end{figure}

  \end{center}
\end{frame}



\begin{frame}
  \begin{center}
    
\begin{figure}
\begin{center}
  \includegraphics[height=0.75\textheight]{turing}
\end{center}\caption{Alan \bsc{Turing (1912-1954)}}
\end{figure}

  \end{center}
\end{frame}


\begin{frame}
  \begin{center}
    
\begin{figure}
\begin{center}
  \includegraphics[height=0.75\textheight]{snowwhite}
\end{center}
\end{figure}

  \end{center}
\end{frame}
\section{Les machines de \bsc{Turing}}

\subsection{Présentation sommaire}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{machine_turing}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}
\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,-.6) {};
     \node [draw,on chain=1,scale=1.0]{\footnotesize$ \blanc $} ;
     \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.0]{\footnotesize$ \blanc $} ;
    \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.25,-1) {};    
    \node at (2.3,-1.2) {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}

\pause

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

\pause


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


\end{frame}





\subsection{Premier exemple}



\begin{frame}
  On entre un \og mot\fg{} écrit à partir de l'alphabet  $\bigl\{0,1,\blanc \bigr\}$. 

\pause

Nous voudrions changer
les 0 en 1 et vice-versa puis 
remettre le pointeur dans sa position initiale.
\end{frame}



\begin{frame}
\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}
\end{frame}


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



\pause

\begin{block}{Exemple}
    Testez cette machine sur la chaîne $ \blanc  10011\blanc $.
\end{block}
\end{frame}




\subsection{Définitions}


\begin{frame}
  

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

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

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  $\varphi$ 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 $\blanc \in X$ est le symbole blanc.
\end{itemize}
\end{definition}


\end{frame}






\begin{frame}
  \begin{itemize}
  \item $Q=\bigl\{q_0,q_1,q_2\bigr\}$
\item $X=\bigl\{\blanc ,0,1\bigr\}$
\item $Q_f=\bigl\{q_2\bigr\}$
\item  $ \varphi$ est  définie à  l'aide du
tableau suivant:
\begin{center}
             \begin{tabularx}{0.8\linewidth}{Y{2}}
	     \whline
             $ \varphi(q_i,x)$& $ q_0$& $ q_1$ & $ q_2$\\
             \whline
             $ \blanc $& $ (q_1,\blanc ,D)$& $ (q_2,\blanc ,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}

  \end{itemize}
\end{frame}




\begin{frame}
En  fait,  une  machine  de  \bsc{Turing}  agit  sur  des  \textit{mots}
construits à partir  d'un \textit{alphabet}.
\end{frame}


\begin{frame}
  \begin{definition}
Soit  X  un  alphabet.  Soit  $  \vide$ le  mot  ne  comportant  aucun
caractère. L'ensemble $  X^*$ des mots construits avec  l'alphabet X est
défini par:
\begin{enumerate}
\item $ \vide \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 $\vide$ par application de l'étape 2 un nombre fini de fois.
\end{enumerate}
\end{definition}
\end{frame}





\begin{frame}
  \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}
\end{frame}


\subsection{Fonctions MT-calculables}

\begin{frame}
  \begin{example}
    Nous  allons construire  une machine  de  \bsc{Turing} qui
calcule le successeur de la représentation unaire d'un entier.
  \end{example}
\end{frame}


\begin{frame}
  \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\}$.
\pause
Ainsi, la représentation de  0 est 1, celle de 1 est  11, celle de 2 est
111, etc.
\pause
On notera $ \overline{n}$ la représentation de l'entier $n$.
\end{definition}

\end{frame}






\begin{frame}
  
Décrivons une machine de \bsc{Turing} qui calcule cette fonction:
\begin{itemize}
\item la fonction successeur  $s$ est définie sur $D=\bigl\{\vide,\blanc  1
  \blanc , \blanc  11 \blanc , \blanc  111\blanc ,...\bigr\}$:  l'entrée sur le ruban est donc la
  représentation unaire du
  nombre $n$  précédée du symbole $  \blanc $, toutes les  autres cases étant
  occupées par des $ \blanc $;
\item l'alphabet de ruban est $ X=\bigl\{1,\blanc \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 $\varphi$ est décrite par l'automate suivant:
\end{itemize}


\end{frame}


\begin{frame}
  

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

\pause

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

\pause

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

\end{frame}



\begin{frame}


  \begin{definition}[Fonction MT-calculable]
{\small
Soit  $f~: D\subseteq  X^* \to  X^*$  une fonction  et $M=(Q,X,\varphi)$  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
  $\varphi(q_0,\blanc )=(q_i,\blanc ,D)$  avec $q_i\neq  q_0$ (\textit{il  faut quitter
    l'état initial à partir de $ \blanc $});
\item il n'existe pas de  transition de la forme $ \varphi(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  $ \varphi(q_f,\blanc )$  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\blanc  \mu \blanc $
  s'arrête après un nombre fini  d'étapes dans la configuration finale $
  q_f\blanc  \nu \blanc $ (\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}


\end{frame}



\begin{frame}
  
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}
\end{frame}




\subsection{La théorie en pratique}



\begin{frame}[fragile]

  \begin{lstlisting}[caption={}]
let en_place vec pos valeur =
  vec.(pos) <- valeur;
  vec;
;;
  \end{lstlisting}
  
\end{frame}



\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
exception Pas_lu;;
let rec  phi q pos vec =
  match (q,vec.(pos)) with
  |("q0","b")  -> phi "q1" (pos+1) vec
  |("q0",  _)  -> raise Pas_lu
  |("q1","b")  -> phi "q2" (pos-1) (en_place vec pos "b")
  |("q1","0")  -> phi "q1" (pos+1) (en_place vec pos "1")
  |("q1","1")  -> phi "q1" (pos+1) (en_place vec pos "0")
  |("q2","b")  -> (en_place vec pos (vec.(pos)^"^")) (* sortie *)
  |("q2","1")  -> phi "q2" (pos-1) (en_place vec pos "1")
  |("q2","0")  -> phi "q2" (pos-1) (en_place vec pos "0")
  |_ -> raise Pas_lu;;

let turing phi vec = phi "q0" 0 vec;;

\end{lstlisting}


\pause


\begin{lstlisting}[caption={}]
# turing phi [|"b";"1";"0";"0";"1";"1";"b"|];;
- : string array = [|"b^"; "0"; "1"; "1"; "0"; "0"; "b"|]
\end{lstlisting}


\end{frame}




\subsection{Fonctions récursives}
\subsubsection{Fonctions primitives récursives}

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

\pause


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

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

\end{frame}



\begin{frame}
  \begin{example}
    
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)=$$


  \end{example}
\end{frame}



\begin{frame}
  

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


\end{frame}

\begin{frame}
\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}
\end{frame}



\begin{frame}
  \begin{example}[La fonction add]
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\\
\pause
\add(m,n+1)=h(m,n,add(m,n))=s(add(m,n))
\end{cases}
$$
  \end{example}
\end{frame}




\begin{frame}
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}
$$
\end{frame}




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

\begin{frame}
  \begin{itemize}
  \item On pourrait généraliser en définissant les fonctions récursives.
\item Alors les fonctions MT-calculables sont les fonctions récursives.
\item  \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{}.
\item 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.
\item Le programmeur est lui-même une  machine de \textsc{Turing} s'il a écrit
son programme (et prouvé qu'il fonctionne...).
\item Un langage est une machine de \textsc{Turing}.

  \end{itemize}
\end{frame}


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




\begin{frame}
  \begin{itemize}
  \item  Est-ce  qu'une machine sera  un jour capable  de raisonner
comme un cerveau humain?
\item  {\itshape 
Science is what we understand well  enough to explain to a computer. Art
is everything else we do.  
}
  \end{itemize}
\end{frame}



















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





\section{Langages}


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

\end{frame}



\subsection{Un exemple pour découvrir}

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


\begin{frame}
  L'\textit{alphabet des symboles} est:

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


\end{frame}


{\scriptsize
\begin{frame}
  \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}
\end{frame}
}






\begin{frame}
  

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

LA FILLE ÉTUDIE LE JEUNE COURS.

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



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




\subsection{Définitions et notations}


\begin{frame}
  \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}
\end{frame}



\begin{frame}
  

\begin{definition}
 Soit A un alphabet.  Soit $ \vide_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 $ \vide_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 $\vide_A$ par application de l'étape 2 un nombre fini de fois.
\end{enumerate}
\end{definition}
\end{frame}



\begin{frame}
  \begin{definition}
\begin{itemize}
\item La
  \textit{longueur}  d'une  chaîne est  le  nombre  de  symboles qui  la
  composent.
\item On note souvent $|\mu|$ la longueur de la chaîne $\mu$. En particulier $|\vide_A|=0$.


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

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

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

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

\item La concaténation des chaînes $\mu$ et $\nu$ sera notée $\mu\nu$.
\end{itemize}
\end{definition}


Conventions


\end{frame}
\begin{frame}
  Monoïde libre
\end{frame}

\begin{frame}
  $$
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}}
$$
\end{frame}









\begin{frame}
  \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\vide$, 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\vide$, 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(\vide,\vide)$,   on   dit   que   $\mu$   est   un
  \textit{facteur propre} de $\nu$.
\item Pour toutes chaînes $\mu$ et $\nu$ de $A^{\ast },$ le quotient \`{a} gauche de $\nu$
par $\mu$ est not\'{e} $\mu^{-1}\nu$ et d\'{e}fini par: 
$$
\mu^{-1}\nu=\left\{ 
\begin{array}{l}
\xi\text{ si }\nu=\mu\xi \\ 
\text{n'a pas de sens si }\mu\text{ n'est pas un pr\'{e}fixe de }\nu%
\end{array}%
\right.
$$%
On d\'{e}finit de m\^{e}me le quotient \`{a} droite.

\end{itemize}
\end{definition}
\end{frame}




\begin{frame}
  

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



\end{frame}


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

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



\end{frame}






\subsection{Langages}

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





\begin{frame}
  
\begin{theorem}

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{theorem}



\end{frame}



\begin{frame}
  

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

\end{frame}


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

\pause


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



\end{frame}

\begin{frame}
  

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

\pause


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

\end{frame}







\begin{frame}
  

\begin{definition}

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


\end{frame}



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




\subsubsection{Langage rationnel}


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

\begin{frame}

\begin{theorem}
  \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{theorem}
\end{frame}

\subsubsection{Expression rationnelle}

\begin{frame}

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




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





\begin{frame}[fragile]


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


\pause

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






























\begin{frame}

\begin{theorem}
\`{A} chaque expression rationnelle $E$ on fait correspondre le langage $%
\mathcal{L}\left( E\right)$  de $A^{\star }$ d\'{e}fini par :

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

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

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

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

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

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

\end{theorem}

\end{frame}



\begin{frame}
  
\begin{theorem}

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

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

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

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

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

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

\end{frame}





\begin{frame}

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

\end{frame}




\section{Automates}


\subsection{Définitions}


\begin{frame}
  
\begin{definition}
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};
\item  une partie  I non  vide de  Q appelée  \textit{ensemble  des états
    initiaux};
\item  une partie T  non vide  de Q  appelée \textit{ensemble  des états
    terminaux};
\item une relation  $\tau$ de $Q\times A$ vers Q  ou de $Q\times \left(A
    \cup \{\vide\}\right)$ vers Q, appelée \textit{relation de transition}.
\end{itemize}
\end{definition}
\end{frame}

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


\begin{itemize}
\item transition
\item étiquette
\item origine
\item extrémité terminale
\end{itemize}
\end{frame}


\begin{frame}\frametitle{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}
\end{frame}
\subsection{Langage reconnaissable}

\begin{frame}
Un \textbf{calcul }$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 : 
$$
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 
$$
c=q_{i_{0}}\xrightarrow{\alpha _{1}\alpha _{2}\cdots \alpha _{n}}q_{i_{n}}
$$

\pause

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. 




\end{frame}






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


\end{frame}














\begin{frame}\frametitle{Langage reconnaissable par un automate}
  


\begin{definition}
On note $\mathcal{L}\left( \mathcal{A}\right) $ l'ensemble des mots reconnus
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}$ si, et seulement si, $\mathcal{L}\left( \mathcal{A}\right) =L.$

Un langage est \textbf{reconnaissable}  si, et seulement si,il existe un
automate qui le 
reconna\^{\i}t.

 L'ensemble des langages reconnaissables de $A^{\star }$ est
not\'{e} $\text{Rec}\left( A^{\star }\right) .$


\end{definition}

\end{frame}




\subsection{Langage reconnu}

\begin{frame}
  Méthode \og manuelle\fg{}
\end{frame}

\begin{frame}
Technique d'élimination d'états.

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

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

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



\end{frame}





\begin{frame}
  
\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,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}

\end{frame}




\begin{frame}

\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_d$};
 \node[state] (B) [ right of=A] {$q_0$};
 \node[state] (C) [ right of=B] {$q_1$};
 \node[state] (D) [ right of=C] {$q_2$};
 \node[state,accepting] (E) [ right of=D] {$q_t$};
 
 \path (A) edge node {$\vide$} (B)
       (B) edge node {$a$} (C)
       (C) edge [loop above] node {$b$} (C)
           edge node {$c$} (D)
       (D) edge [loop above] node {d} (D)
       (D) edge node {$\vide$} (E);
\end{tikzpicture}
\end{center}


\pause

\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_d$};
% \node[state] (B) [ right of=A] {$q_0$};
 \node[state] (C) [ right of=B] {$q_1$};
 \node[state] (D) [ right of=C] {$q_2$};
 \node[state,accepting] (E) [ right of=D] {$q_t$};
 
 \path %(A) edge node {$\vide$} (B)
       (A) edge node {$a$} (C)
       (C) edge [loop above] node {$b$} (C)
           edge node {$c$} (D)
       (D) edge [loop above] node {d} (D)
       (D) edge node {$\vide$} (E);
\end{tikzpicture}
\end{center}


\pause


\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_d$};
% \node[state] (B) [ right of=A] {$q_0$};
% \node[state] (C) [ right of=B] {$q_1$};
 \node[state] (D) [ right of=C] {$q_2$};
 \node[state,accepting] (E) [ right of=D] {$q_t$};
 
 \path %(A) edge node {$\vide$} (B)
       (A) edge node {$ab^\star c$} (D)
 %      (C) edge [loop above] node {$b$} (C)
 %          edge node {$c$} (D)
       (D) edge [loop above] node {d} (D)
       (D) edge node {$\vide$} (E);
\end{tikzpicture}
\end{center}


\pause

\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_d$};
% \node[state] (B) [ right of=A] {$q_0$};
% \node[state] (C) [ right of=B] {$q_1$};
% \node[state] (D) [ right of=C] {$q_2$};
 \node[state,accepting] (E) [ right of=D] {$q_t$};
 
 \path %(A) edge node {$\vide$} (B)
       (A) edge node {$ab^\star cd^\star$} (E);
 %      (C) edge [loop above] node {$b$} (C)
 %          edge node {$c$} (D)
 %      (D) edge [loop above] node {d} (D)
 %      (D) edge node {$\vide$} (E);
\end{tikzpicture}
\end{center}


\end{frame}






\subsection{Automates équivalents}


\begin{frame}
  
\begin{theorem}{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{theorem}
\end{frame}



\subsection{Automates standards}


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

\end{frame}


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

\end{frame}


\begin{frame}
  \begin{exercice}
    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{exercice}
\end{frame}



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





\subsection{Automates déterministes}



\begin{frame}

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

\pause


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


\end{frame}





\begin{frame}

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

\end{frame}

\begin{frame}

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

\pause

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





\end{frame}



\begin{frame}
  \begin{exercice}
    Déterminez  l'automate déterministe  équivalent à  l'automate défini
    par la table de transition:
\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\}$
  \end{exercice}




\end{frame}


\begin{frame}


{\small

\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=3.2cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 5em]
\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{frame}







\begin{frame}

\begin{theorem}
Tout  automate   peut  être  transformé  en   un  automate  déterministe
reconnaissant le même langage.
\end{theorem}

\end{frame}





\subsection{Automates émondés}

\begin{frame}

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

\end{frame}



\begin{frame}

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


\begin{frame}[fragile]

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

\end{frame}



\begin{frame}[fragile]
  
\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}

\end{frame}


\begin{frame}

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





\subsection{Opérations rationnelles sur les automates}

\subsubsection{Union}



\begin{frame}
  
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{theorem}
  L'automate $\AR_1 | \AR_2$ reconnaît le langage $L_1 | L_2$.
\end{theorem}
\end{frame}




\subsubsection{Produit}


\begin{frame}
  
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 à 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),D_1,T',\tau_1\cup\tau_2\cup\tau''_2>$$ avec:

\begin{itemize}
\item  $T'=(T_1\cup  T_2)$  si  $d_2\in  T_2$ et  $T_2$
  sinon;

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

\end{frame}

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

\end{frame}


\subsubsection{Étoile}

\begin{frame}
  
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\}$


\end{frame}



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



\begin{frame}

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

\subsection{Lemme de la pompe}


\begin{frame}

\begin{theorem}[Lemme de la Pompe: version automate]
  Soit $\AR$ un automate tel que:
  \begin{itemize}
  \item $\AR$ a $k$ états;
  \item $\AR$ accepte une chaîne $\mu$ de longueur $|\mu|>k$;
  \end{itemize}

  \pause

Alors il existe trois chaînes $\nu$, $\xi$ et $\rho$ telles
que
\begin{itemize}
\item $\mu$ puisse s'écrire sous la forme $\nu\xi\rho$,
\item $\xi$ étant non vide,
\item pour tout
entier naturel $n$, chaque chaîne $\nu\xi^n\rho$ est acceptée par $\AR$.
\end{itemize}

\end{theorem} 

\end{frame}



\begin{frame}
  \begin{exercice}[Application du lemme de la pompe]
    Le langage $\bigl\{a^nb^n\mid n\in\bbn\bigr\}$ n'est pas rationnel.  
  \end{exercice}
\end{frame}


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



\subsubsection{Algorithme de \textsc{Glushkov}}


\begin{frame}
  
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.

\pause

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

\pause

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

\pause

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

\pause

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

\pause

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.

\pause

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

\end{frame}


\subsection{Automate minimal}

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



\begin{frame}

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


\pause


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


\pause



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

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

    \pause

\begin{itemize}
\item  $q_0$ et $q_1$ sont-ils distinguables par $a$? Par $b$?

\item Par quelle chaîne $q_1$ et $q_2$ sont-ils distinguables?
\end{itemize}
\end{frame}

\begin{frame}
  
\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,accepting] (B) [ right of=A] {$q_1$};
 \node[state] (C) [ right of=B] {$q_2$};
 \node[state,accepting] (D) [ right of=C] {$q_3$};

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

\pause

Notons $L(q)$  l'ensemble des chaînes  qui sont l'étiquette  d'un chemin
allant de $q$ à un état terminal: déterminez $L(q_0)$, $L(q_1)$, $L(q_2)$ et $L(q_3)$.

\pause 

Quel est le langage reconnu par cet automate?
\end{frame}


\begin{frame}
  $L(q_0)=L(q_2)$ et $L(q_1)=L(q_3)$.


\pause


\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,q_2$};
 \node[state,accepting] (B) [ right of=A] {$q_1,q_3$};

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


\pause

Langage reconnu?

\end{frame}



\begin{frame}

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

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

\end{theorem}

\pause

Si on note $L(q)= \bigl\{a  \in A^\star\mid \tau(q,a)\in T\bigr\}$, cela
revient à dire que $L(q_i)=L(q_j)$.

\pause

On définit ainsi une relation d'équivalence.

Notons  $[q]_N$ la  classe d'un  état  $q$: la  relation $\equiv_N$  est
compatible avec la fonction de transition:
\pause

$$q_i\equiv_N q_j \limp \tau(q_i,a) \equiv_N \tau(q_j,a)$$

\end{frame}

\begin{frame}
  On peut  donc définir  l'\textbf{automate de  \textsc{Nérode}} $\AR_N$
  associé à $\AR$:



$$\AR_N=\left(A,[Q]_N,[q_0]_N,[T]_N,\tau_N\right)$$

avec

\begin{itemize}
\item $[Q]_N=\bigl\{[q]_N\mid q\in Q\bigr\}$
\item $[T]_N=\bigl\{[q]_N\mid q\in T\bigr\}$
\item $\tau_N([q]_N,a)=\left[\tau(q,a)\right]$
\end{itemize}


\end{frame}

\begin{frame}

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



\end{frame}



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

\begin{frame}
  On va en fait travailler par approximation successives de $\ equiv_N$
  par des relations de plus en  plus fines, en considérant les relations
  $\equiv_N^p$ :

$$q\equiv_N^pq' \limp L(q)\cap A^{\leqslant p} = L(q')\cap A^{\leqslant p}$$

On peut montrer  que la suite de ces  relations d'équivalences stationne
vers $\equiv_N$ dès  que deux relations consécutives sont  égales ce qui
va nous donner un algorithme pratique pour minimaliser un automate.
\end{frame}


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

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


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


\pause


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
















\end{frame}








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

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



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

\end{frame}









\subsection{Automates à états finis avec sortie}


\begin{frame}

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

\end{frame}



\begin{frame}




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



\end{frame}



\subsection{Automates à pile}

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




\begin{frame}


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

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

\end{frame}







\section{Grammaires}



\subsection{Syntaxe et sémantique}



\begin{frame}

\begin{quote}
{\itshape \large Mon père est marinier\\
Dans cette péniche\\
Ma mère dit : « La paix niche\\
Dans ce mari niais »\\
Ma mère est habile\\
Mais ma bile est amère\\
Car mon père et ses verres\\
Ont les pieds fragiles}
\end{quote}

\end{frame}



\begin{frame}
  \begin{center}
  \includegraphics[height=\textheight]{boby}
\end{center}
\end{frame}

\begin{frame}
  \begin{itemize}
  \item \og le
vendredi matin, l'étudiant sent la rose\fg{}
\item \og  Tous les
matins, je mange un avocat\fg{}
\item \og Tous les
avocats, je mange la Pologne\fg{}
\item \og Je regarde cette jolie fille qui se promène avec des jumelles\fg{}
  \end{itemize}
\end{frame}

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

\pause

%\caml

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

\end{frame}




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

\subsubsection{Définitions}


\begin{frame}

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

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

\end{definition}
\end{frame}


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

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

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



\begin{frame}

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

\end{definition}

\end{frame}



\subsubsection{Arbre de dérivation}



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

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


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

  \end{itemize}
\end{frame}




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




\subsection{Grammaire régulière}

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

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

\end{definition}

\pause


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

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

\end{frame}






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

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




\subsubsection{Analyse syntaxique descendante en largeur}
\renewcommand{\algokeywordfont}[1]{{\tiny\sffamily\upshape\bfseries#1}}
\begin{frame}[fragile]


\tiny

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

\end{frame}











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


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

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

\item L'axiome est l'unique état initial.


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

\item Une règle $A\to \vide$ donne un état terminal.
  \end{itemize}
\end{frame}



\end{document}
%%% Local Variables: 
%%% TeX-master: t
%%% End: 
