t

[cours-maths-dis.git] / automates / AutomatesAPile.tex

On l'a dit, les expressions rationnelles ne permettent pas de représenter tous les langages.


\begin{Ex}
Le langage défini par $\{ a^n b^n | n \in \mathbb{N}^* \}$ n'est pas représentable par une expression rationnelle.
\end{Ex}

\begin{Exo}
Déterminez d'autres langages non reconnus par expression rationnelle.
\end{Exo}


On souhaite maintenant étudier \og une plus grande classe\fg{} de langages, et voir ce qu'il manque à nos automates pour pouvoir les associer à ces langages.\\

Dans l'exemple précédent, il faudrait \og noter quelque part \fg{} le nombre de $a$ rencontrés, pour s'assurer qu'il y aura bien autant de $b$. On peut imaginer y arriver avec une pile jointe à un automate non déterministe.

\begin{Rem}
Très précisément, les automates à pile vont jouer pour les langages dits non contextuels (voir chapitre suivant) le rôle des automates finis pour les langages rationnels (: représentables par expressions rationnelles).
\end{Rem}


\section{Automates à pile, déteministes ou pas.}

\subsection{Automate à pile non déterministe}

\subsubsection{Définition}

\begin{Def}[Automate à pile]
Un \emph{automate à pile}\index{automate!à pile} est donné par

\begin{enumerate}
\item Un alphabet d'entrée $\Sigma$ (ensemble fini non vide),
\item Un ensemble d'états $E$ (fini non vide),
\item Un état initial $e_0 \in E$,
\item \'Eventuellement, une partie $A \subset E$ des états d'acceptation (pour un automate à pile dit à \emph{états d'acceptation}\index{automate!à pile!à états d'acceptation}),
\item Un alphabet de pile $P$ (fini, non vide),
\item Un symbole de pile initial $p_0$,
\item \'Eventuellement, un ensemble $Q \subset P$ de symboles de sommet de pile,
\item Enfin, une relation $t : E \times (\Sigma \cup \{ \varepsilon \} \} \times P \rightarrow E \times P^*$.
\end{enumerate}
\end{Def}

\begin{Rem}
Le symbole de pile initial n'est pas toujours noté $p_0$.
\end{Rem}


\subsubsection{Transition}

\begin{Def}[Transition]
Lorsque $((e,x,p),(e',q))$ appartient au graphe de la relation $t$, on parle de la transition $(e,x,p) \longmapsto (e',q)$. 
\end{Def}


\noindent Elle indique que, lorsque l'automate se trouve : 
\begin{itemize}
 \item dans l'état $e$,
 \item alors que le symbole de sommet de pile est $p$,
 \item sur l'entrée $x$,
\end{itemize}

\noindent alors il évolue 

\begin{itemize}
\item vers l'état $e'$,
\item le symbole $p$ est dépilé,
\item et le mot de pile $q$ (éventuellement plusieurs symboles de pile) est empilé.
\end{itemize}

\bigskip

Comme $t$ est une relation, il est possible, dans le cas d'un automate à pile non déterministe, qu'il y ait plusieurs transitions possibles dans la même situation (même état, même entrée, même symbole de  sommet de pile).

\begin{Ex}[Automate à pile non déterministe]
Ici, l'alphabet d'entrée est $\{0,1\}$, le fond de pile est $T$ et alphabet de pile $\{T,Z,A\}$ :\\

\begin{center}
 \includegraphics[scale=0.5]{automates/automatePile2.eps}
\end{center}
Cet automate reconnaît, par pile vide, l'ensemble $$\{0^n 1^m, n \geqslant m > 0 \}$$
\end{Ex}

\begin{Rem}
Si un automate à états finis reconnaît un mot lorsqu'il s'arrête dans un état d'acceptation, il n'en est pas de même pour les automates à pile : on verra par la suite que ceux-ci ont plusieurs critères pour décider si un mot est reconnu ou non.

Le critère de reconnaissance \emph{par pile vide} fait partie de ceux-ci: lorsque l'automate s'arrête avec une pile vide, le mot est accepté.

On remarque que les mots 01, 001, 0011 sont acceptés par cet automate. Il n'en est pas de même pour 011.
\end{Rem}


\subsection{Automate à pile déterministe}

\subsubsection{Définition}
\begin{Def}[Automate à pile déterministe]
Dans le cas d'un \emph{automate à pile déterministe}\index{automate!à pile!déterministe}, $t$ est une fonction sur son domaine de définition, et $(e',q) = t(e,x,p)$.
\end{Def}

\begin{Rem}
En particulier si $t$ est définie pour le triplet $(e,x,p)$, $t(e,x,p)$ est unique.
\end{Rem}


\begin{Ex}[Automate à pile déterministe]
Ici, l'alphabet d'entrée est $\{0,1\}$, le fond de pile est $Z$ et alphabet de pile $\{Z,A\}$ :\\
\begin{center}
 \includegraphics[scale=0.5]{automates/automatePile3.eps}
\end{center}
\end{Ex}

\begin{Rem}
Cet automate à pile déterministe reconnaît, par état final, le même langage que l'exemple précédent.
\end{Rem}

\subsubsection{Transitions}

Il est fondamental de comprendre qu'une transition d'un automate à pile, quelle qu'elle soit, exige toujours de dépiler un symbole de pile.\\


\begin{Rem}
Autrement dit, si la pile vient à se vider, l'automate se bloque et ne peut plus évoluer, même si le mot d'entrée n'a pas été entièrement lu.

Ceci explique le \og symbole de pile initial\fg{} , la plupart du temps sans intérêt autre que celui de permettre le début du calcul dans l'automate. 
\end{Rem}


\begin{Rem}
On admet des \og transitions vides\fg{} , du type $(e,\varepsilon,p) \longmapsto \hdots)$, qui permettent de ne pas avancer sur le mot d'entrée, par exemple pour vider la pile. Il faut les utiliser avec précautions.
\end{Rem}


\section{Calcul dans un automate à pile}

\subsection{Encore quelques définitions...}

\begin{Def}[Configuration]
On appelle \emph{configuration d'un automate à pile}\index{automate!à pile! configuration} un triplet $(e,w,q)$ où
\begin{itemize}
 \item $e$ est l'état dans lequel se trouve l'automate à l'instant considéré,
 \item $w$ est le mot à lire,
 \item $q$ est le mot de pile (en tête, le symbole de sommet de pile, en queue, le symbole de fond de pile). 
\end{itemize}
\end{Def}


\begin{Def}[Dérivation valide]
Si 
\begin{itemize}
 \item $q$ est de la forme $pq'$ où $p$ est le symbole de sommet de pile,
 \item $w$ est de la forme $xw'$, où $x$ est un symbole d'entrée,
 \item il existe une transition $(e,x,p) \longmapsto (e',q'')$,
\end{itemize}
alors, après application de cette transition, la nouvelle configuration de l'automate est $(e',w',q'' q')$ et la correspondance $(e,w,q) \vdash (e',w',q'' q')$ est appelée une \emph{dérivation valide dans l'automate}\index{automate!à pile!dérivation valide}.
\end{Def}


\begin{Def}[Calcul valide]
Un \emph{calcul valide}\index{automate!à pile!calcul valide} dans l'automate est une famille de dérivations $(e_1,w_1,q_1) \vdash (e_2,w_2,q_2) \vdash \hdots \vdash (e_n,w_n,q_n) $.


On dit que ce calcul valide mène de la configuration $(e_1,w_1,q_1) $ à la configuration $ (e_n,w_n,q_n) $
\end{Def}



\begin{Notation}
On peut noter cela : $(e_1,w_1,q_1) \stackrel{*}{\vdash} (e_n,w_n,q_n) $. 
\end{Notation}


\begin{Def}[Mot reconnu]
On dit qu'un mot $w$ est \emph{reconnu}\index{automate!à pile!mot reconnu} par un automate à pile (état initial $e_0$, symbole de pile initial $p_0$) lorsqu'il existe un calcul valide $$(e_0,w,q_0) \stackrel{*}{\vdash} (e,\varepsilon,q) $$ tel que, au choix

\begin{itemize}
\item $e$ est un état d'acceptation : le mot $w$ est dit \emph{reconnu par l'état d'acceptation}\index{mot reconnu!par état d'acceptation},
\item $q$ est de la forme $q_sq'$ où $q_s \in Q$ : le mot $w$ est dit \emph{reconnu par symbole de sommet de pile}\index{mot reconnu!par symbole de sommet de pile},
\item $q = \varepsilon$ (symbole de pile vide) : le mot $w$ est dit \emph{reconnu par pile vide}\index{mot reconnu!par pile vide},
\end{itemize}
\end{Def}

\begin{Rem}
On peut envisager des reconnaissances par combinaison de deux de ces conditions, voire les trois simultanément.
\end{Rem}


\noindent On démontre que...

\begin{Th}
Tous ces types de reconnaissance peuvent se ramener à la seule reconnaissance par pile vide (éventuellement avec un automate beaucoup plus compliqué ). 
\end{Th}

%
\noindent C'est pourquoi nous n'envisagerons plus que cette dernière dans la suite. Enfin,

\begin{Def}[Langage reconnu]
Le \emph{langage reconnu}\index{automate!à pile!langage reconnu} par automate est l'ensemble des mots reconnus par cet automate (par le même mode de reconnaissance). 
\end{Def}

\subsection{Premiers exemples}

\begin{Ex}
Automate à pile (non déterministe) reconnaissant, par pile vide, l'ensemble des mots de la forme $ww^t$, concaténation de $w$ (constitué de 0 et de 1) et de son image miroir :\\

\begin{center}
 \includegraphics[scale=0.5]{automates/automatePile4.eps}
\end{center} 

\noindent (Alphabet d'entrée $\{0,1\}$, fond de pile $Z$, alphabet de pile $\{Z,A,B\}$.)
\end{Ex}



\begin{Ex}
Automate à pile reconnaissant, par pile vide, l'ensemble des mots de la forme $wcw^t$, concaténation de $w$ (constitué de 0 et de 1) et de son image miroir séparés par le caractère $c$ :\\

\begin{center}
 \includegraphics[scale=0.5]{automates/automatePile1.eps}
\end{center}
\noindent (Alphabet d'entrée $\{0,1,c\}$, fond de pile $Z$, alphabet de pile $\{Z,A,B\}$.)
\end{Ex}


\subsection{Exemple plus complet : le langage $\{0^n 1^n | n \in \mathbb{N}^* \}$}
 
\noindent Le principe est le suivant :

\begin{enumerate}
 \item Tant qu'on lit des 0, on les empile, sans changer d'état,
 \item Au premier 1 rencontré, on change d'état (pour ne plus accepter de 0),
 \item On dépile alors un à un les symboles de pile (sans jamais rien empiler),
 \item Si le mot se vide en même temps que la pile, il comportait autant de 0 que de 1.
\end{enumerate}

\bigskip

\noindent Voici les transformations :

\begin{itemize}
 \item $(e_0,0,p_0) \rightarrow (e_0,0)$
 \item $(e_0,0,0) \rightarrow (e_0,00)$
 \item $(e_0,1,0) \rightarrow (e_1,\varepsilon)$
 \item $(e_1,1,0) \rightarrow (e_1,\varepsilon)$
\end{itemize}

\begin{Exo}
Représentez cet automate.
\end{Exo}


\section{Construction d'un automate à pile}

\subsection{Introduction à la méthode}
On peut évidemment utiliser la méthode \og directe\fg, comme dans l'exemple précédent.\\


Pour les langages plus complexes, il peut être nécessaire d'avoir recours à un algorithme. Nous l'aborderons par l'exemple de la grammaire écrite pour les expressions algébriques élémentaires :

$$\begin{array}{lll}
<expression> & ::= & <terme>\\

 & ::= & <terme> ~ '+' ~ <expression>\\

<terme> &::=& <facteur>\\

&::=& <facteur> ~ '*' ~ <terme>\\

<facteur> &::=& ~ '(' ~ <expression> ~')'\\

& ::=& <variable>
\end{array}$$

\noindent en omettant la définition du SNT \og variable\fg{}, inutile ici.\\

\subsection{Utilisation d'un symbolisme}

On introduit un nouveau symbolisme (développé dans la suite) pour cette même grammaire ; il se comprend aisément :

$$\begin{array}{ccl}
E & -> &T\\
E & -> &T + E\\
T & -> &F\\
T & -> &F * T\\
F & -> &( E )\\
F & -> &a\\
F & -> &b\\
&...&\\
F & -> & z\\
\end{array}$$


\noindent ...en admettant comme symboles de variables les caractères alphabétiques minuscules.\\


\subsection{Algorithme de construction}

Le principe est de construire un automate à pile non déterministe qui admet des transitions vides :

\begin{enumerate}
 \item Au départ, sur une transition vide, on empile le SNT de l'axiome de la grammaire (ici, E) : \emph{c.f.} transition (1).
%  \item Quelle que soit l'entrée qui se présente,
% \begin{itemize}
%  \item Si c'est un SNT qui figure en sommet de pile, on crée une transition vide qui le remplace par les symboles de sa définition,
%  \item Lorsque c'est un ST qui est au sommet de la pile, on le compare avec le symbole qui figure en entrée et, s'il est bon, on se contente de le dépiler.
% \end{itemize}
\item associer à chaque règle non terminale une $\epsilon$-transition qui empile les symboles de la partie droite (\emph{c.f.} transitions (2) à (6))
\item associer à chaque règle terminale $A \rightarrow x$ une transition $(e_0,x,A) \mapsto (e_0,\epsilon)$ (\emph{c.f.}. transitions (7) et (8))
\item associer à chaque symbole terminal une transition qui reconnaît ce symbole et dépile ce caractère (\emph{c.f.} transitions (9) à (12))
\end{enumerate}


\bigskip

On obtient les transitions suivantes :
$$
\begin{array}{llll}
(1) & (e_0,\varepsilon,p_0) &\longmapsto &(e_0,E)\\
(2) & (e_0,\varepsilon,E) &\longmapsto &(e_0,T)\\
(3) & (e_0,\varepsilon,E) &\longmapsto &(e_0,T+E)\\
(4) & (e_0,\varepsilon,T) &\longmapsto &(e_0,F)\\
(5) & (e_0,\varepsilon,T) &\longmapsto &(e_0,F*T)\\
(6) & (e_0,\varepsilon,F) &\longmapsto &(e_0,(E))\\
(7) & (e_0,a,F) &\longmapsto &(e_0,\varepsilon)\\
\vdots & \vdots & \vdots & \vdots \\
(8) & (e_0,z,F) &\longmapsto &(e_0,\varepsilon)\\
(9) & (e_0,+,+) &\longmapsto &(e_0,\varepsilon)\\
(10) & (e_0,*,*) &\longmapsto & (e_0,\varepsilon)\\
(11) & (e_0,(,() &\longmapsto & (e_0,\varepsilon)\\
(12) & (e_0,),)) &\longmapsto & (e_0,\varepsilon)\\
\end{array}$$



\subsection{Exercices}

\begin{Exo}
Soit l'automate à pile défini par $\Sigma=\{a,b\}$, $E=\{q_0,q_1,q_2\}$, $P=\{p_, A\}$ et les transitions suivantes 

\begin{eqnarray*}
(q_0,a,p_0) & \mapsto&  (q_1,A) \\
(q_1,b,A) & \mapsto&  (q_2,\epsilon) \\
(q_1,a,p) & \mapsto&  (q_1,Ap)\\
(q_2,b,A) & \mapsto&  (q_2,\epsilon) \\
\end{eqnarray*}
\begin{enumerate}
\item Donner les enchaînements des transitions permettant d'accepter $aabb$ en précisant s'il y a des points de non déterminisme dans la dérivation. 
\item Donner l'enchanement des transitions conduisant à l'échec de l'acceptation de la chaîne $aaba$.
\item Décrire l'état de l'automate après avoir lu $n$ symboles $a$ en entrée $(n \in \mathbb{N})$. Quelle est alors la seule façon de vider la pile~? En déduire le langage reconnu par cet automate à pile avec arrêt sur pile vide.
\end{enumerate}
\end{Exo}



\begin{Exo}
Pour $u \in \Sigma^*$ , on note $|u|_a$ le nombre de $a$ dans $u$ et $|u|_b$ le nombre de $b$ dans $u$.

Donner un automate à pile qui reconnaît $L = \{u \in \Sigma^*, |u|_a = |u|_b \}$.
\end{Exo}


\begin{Exo}
Soit $\Sigma = \{0, 1\}$. Donner un automate à pile qui accepte un mot $u \in \Sigma^*$ ssi aucun préfixe de $u$ ne contient plus de 1 que de 0. Préciser si l’automate est déterministe.
\end{Exo}


\begin{Exo}
Soit $\Sigma = \{1, 2\}$. Donner un automate à pile qui reconnaît le langage suivant : $$\{1^n 2^n | n \geqslant 0\}\cup \{1^n 2^{2n} | n \geqslant 0\}$$
Préciser si l’automate est déterministe.
\end{Exo}

\begin{Exo}
Soit $\Sigma = \{a, b, c\}$. Donner un automate à pile qui reconnaît le langage suivant : $$\{a^i b^j c^k | i = j \textrm{ ou } j = k\}$$
Préciser si l’automate est déterministe.
\end{Exo}

\begin{Exo}
Soit $G$ la grammaire suivante :
$$S \rightarrow aAB ~~~ A \rightarrow aAB | a ~~~ B \rightarrow bBA | aC ~~~ C \rightarrow BaA.$$
\begin{enumerate}
\item Donner des exemples de mots reconnus.
\item Donner un automate à pile qui reconnaît le langage généré par la grammaire $G$.
\end{enumerate}
\end{Exo}


\begin{Exo}
Soit $G$ la grammaire suivante :
$$S \rightarrow aAB ~~~ A \rightarrow aAB | a ~~~ B \rightarrow bBA | aC | b ~~~ C \rightarrow BaA.$$
Donner un automate à pile qui reconnaît le langage généré par la grammaire $G$.
\end{Exo}


\gsaut
\centerline{\x{Fin du Chapitre}}