automates/AutomatesAPile.tex

   1
   2
   3 On l'a dit, les expressions rationnelles ne permettent pas de représenter tous les langages.
   4
   5
   6 \begin{Ex}
   7 Le langage défini par $\{ a^n b^n | n \in \mathbb{N}^* \}$ n'est pas représentable par une expression rationnelle.
   8 \end{Ex}
   9
  10 \begin{Exo}
  11 Déterminez d'autres langages non reconnus par expression rationnelle.
  12 \end{Exo}
  13
  14
  15 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.\\
  16
  17 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.
  18
  19 \begin{Rem}
  20 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).
  21 \end{Rem}
  22
  23
  24 \section{Automates à pile, déteministes ou pas.}
  25
  26 \subsection{Automate à pile non déterministe}
  27
  28 \subsubsection{Définition}
  29
  30 \begin{Def}[Automate à pile]
  31 Un \emph{automate à pile}\index{automate!à pile} est donné par
  32
  33 \begin{enumerate}
  34 \item Un alphabet d'entrée $\Sigma$ (ensemble fini non vide),
  35 \item Un ensemble d'états $E$ (fini non vide),
  36 \item Un état initial $e_0 \in E$,
  37 \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}),
  38 \item Un alphabet de pile $P$ (fini, non vide),
  39 \item Un symbole de pile initial $p_0$,
  40 \item \'Eventuellement, un ensemble $Q \subset P$ de symboles de sommet de pile,
  41 \item Enfin, une relation $t : E \times (\Sigma \cup \{ \varepsilon \} \} \times P \rightarrow E \times P^*$.
  42 \end{enumerate}
  43 \end{Def}
  44
  45 \begin{Rem}
  46 Le symbole de pile initial n'est pas toujours noté $p_0$.
  47 \end{Rem}
  48
  49
  50 \subsubsection{Transition}
  51
  52 \begin{Def}[Transition]
  53 Lorsque $((e,x,p),(e',q))$ appartient au graphe de la relation $t$, on parle de la transition $(e,x,p) \longmapsto (e',q)$.
  54 \end{Def}
  55
  56
  57 \noindent Elle indique que, lorsque l'automate se trouve :
  58 \begin{itemize}
  59  \item dans l'état $e$,
  60  \item alors que le symbole de sommet de pile est $p$,
  61  \item sur l'entrée $x$,
  62 \end{itemize}
  63
  64 \noindent alors il évolue
  65
  66 \begin{itemize}
  67 \item vers l'état $e'$,
  68 \item le symbole $p$ est dépilé,
  69 \item et le mot de pile $q$ (éventuellement plusieurs symboles de pile) est empilé.
  70 \end{itemize}
  71
  72 \bigskip
  73
  74 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).
  75
  76 \begin{Ex}[Automate à pile non déterministe]
  77 Ici, l'alphabet d'entrée est $\{0,1\}$, le fond de pile est $T$ et alphabet de pile $\{T,Z,A\}$ :\\
  78
  79 \begin{center}
  80  \includegraphics[scale=0.5]{automates/automatePile2.eps}
  81 \end{center}
  82 Cet automate reconnaît, par pile vide, l'ensemble $$\{0^n 1^m, n \geqslant m > 0 \}$$
  83 \end{Ex}
  84
  85 \begin{Rem}
  86 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.
  87
  88 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é.
  89
  90 On remarque que les mots 01, 001, 0011 sont acceptés par cet automate. Il n'en est pas de même pour 011.
  91 \end{Rem}
  92
  93
  94 \subsection{Automate à pile déterministe}
  95
  96 \subsubsection{Définition}
  97 \begin{Def}[Automate à pile déterministe]
  98 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)$.
  99 \end{Def}
 100
 101 \begin{Rem}
 102 En particulier si $t$ est définie pour le triplet $(e,x,p)$, $t(e,x,p)$ est unique.
 103 \end{Rem}
 104
 105
 106 \begin{Ex}[Automate à pile déterministe]
 107 Ici, l'alphabet d'entrée est $\{0,1\}$, le fond de pile est $Z$ et alphabet de pile $\{Z,A\}$ :\\
 108 \begin{center}
 109  \includegraphics[scale=0.5]{automates/automatePile3.eps}
 110 \end{center}
 111 \end{Ex}
 112
 113 \begin{Rem}
 114 Cet automate à pile déterministe reconnaît, par état final, le même langage que l'exemple précédent.
 115 \end{Rem}
 116
 117 \subsubsection{Transitions}
 118
 119 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.\\
 120
 121
 122 \begin{Rem}
 123 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.
 124
 125 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.
 126 \end{Rem}
 127
 128
 129 \begin{Rem}
 130 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.
 131 \end{Rem}
 132
 133
 134 \section{Calcul dans un automate à pile}
 135
 136 \subsection{Encore quelques définitions...}
 137
 138 \begin{Def}[Configuration]
 139 On appelle \emph{configuration d'un automate à pile}\index{automate!à pile! configuration} un triplet $(e,w,q)$ où
 140 \begin{itemize}
 141  \item $e$ est l'état dans lequel se trouve l'automate à l'instant considéré,
 142  \item $w$ est le mot à lire,
 143  \item $q$ est le mot de pile (en tête, le symbole de sommet de pile, en queue, le symbole de fond de pile).
 144 \end{itemize}
 145 \end{Def}
 146
 147
 148 \begin{Def}[Dérivation valide]
 149 Si
 150 \begin{itemize}
 151  \item $q$ est de la forme $pq'$ où $p$ est le symbole de sommet de pile,
 152  \item $w$ est de la forme $xw'$, où $x$ est un symbole d'entrée,
 153  \item il existe une transition $(e,x,p) \longmapsto (e',q'')$,
 154 \end{itemize}
 155 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}.
 156 \end{Def}
 157
 158
 159 \begin{Def}[Calcul valide]
 160 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) $.
 161
 162
 163 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) $
 164 \end{Def}
 165
 166
 167
 168 \begin{Notation}
 169 On peut noter cela : $(e_1,w_1,q_1) \stackrel{*}{\vdash} (e_n,w_n,q_n) $.
 170 \end{Notation}
 171
 172
 173 \begin{Def}[Mot reconnu]
 174 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
 175
 176 \begin{itemize}
 177 \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},
 178 \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},
 179 \item $q = \varepsilon$ (symbole de pile vide) : le mot $w$ est dit \emph{reconnu par pile vide}\index{mot reconnu!par pile vide},
 180 \end{itemize}
 181 \end{Def}
 182
 183 \begin{Rem}
 184 On peut envisager des reconnaissances par combinaison de deux de ces conditions, voire les trois simultanément.
 185 \end{Rem}
 186
 187
 188 \noindent On démontre que...
 189
 190 \begin{Th}
 191 Tous ces types de reconnaissance peuvent se ramener à la seule reconnaissance par pile vide (éventuellement avec un automate beaucoup plus compliqué ).
 192 \end{Th}
 193
 194 %
 195 \noindent C'est pourquoi nous n'envisagerons plus que cette dernière dans la suite. Enfin,
 196
 197 \begin{Def}[Langage reconnu]
 198 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).
 199 \end{Def}
 200
 201 \subsection{Premiers exemples}
 202
 203 \begin{Ex}
 204 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 :\\
 205
 206 \begin{center}
 207  \includegraphics[scale=0.5]{automates/automatePile4.eps}
 208 \end{center}
 209
 210 \noindent (Alphabet d'entrée $\{0,1\}$, fond de pile $Z$, alphabet de pile $\{Z,A,B\}$.)
 211 \end{Ex}
 212
 213
 214
 215 \begin{Ex}
 216 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$ :\\
 217
 218 \begin{center}
 219  \includegraphics[scale=0.5]{automates/automatePile1.eps}
 220 \end{center}
 221 \noindent (Alphabet d'entrée $\{0,1,c\}$, fond de pile $Z$, alphabet de pile $\{Z,A,B\}$.)
 222 \end{Ex}
 223
 224
 225 \subsection{Exemple plus complet : le langage $\{0^n 1^n | n \in \mathbb{N}^* \}$}
 226
 227 \noindent Le principe est le suivant :
 228
 229 \begin{enumerate}
 230  \item Tant qu'on lit des 0, on les empile, sans changer d'état,
 231  \item Au premier 1 rencontré, on change d'état (pour ne plus accepter de 0),
 232  \item On dépile alors un à un les symboles de pile (sans jamais rien empiler),
 233  \item Si le mot se vide en même temps que la pile, il comportait autant de 0 que de 1.
 234 \end{enumerate}
 235
 236 \bigskip
 237
 238 \noindent Voici les transformations :
 239
 240 \begin{itemize}
 241  \item $(e_0,0,p_0) \rightarrow (e_0,0)$
 242  \item $(e_0,0,0) \rightarrow (e_0,00)$
 243  \item $(e_0,1,0) \rightarrow (e_1,\varepsilon)$
 244  \item $(e_1,1,0) \rightarrow (e_1,\varepsilon)$
 245 \end{itemize}
 246
 247 \begin{Exo}
 248 Représentez cet automate.
 249 \end{Exo}
 250
 251
 252 \section{Construction d'un automate à pile}
 253
 254 \subsection{Introduction à la méthode}
 255 On peut évidemment utiliser la méthode \og directe\fg, comme dans l'exemple précédent.\\
 256
 257
 258 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 :
 259
 260 $$\begin{array}{lll}
 261 <expression> & ::= & <terme>\\
 262
 263  & ::= & <terme> ~ '+' ~ <expression>\\
 264
 265 <terme> &::=& <facteur>\\
 266
 267 &::=& <facteur> ~ '*' ~ <terme>\\
 268
 269 <facteur> &::=& ~ '(' ~ <expression> ~')'\\
 270
 271 & ::=& <variable>
 272 \end{array}$$
 273
 274 \noindent en omettant la définition du SNT \og variable\fg{}, inutile ici.\\
 275
 276 \subsection{Utilisation d'un symbolisme}
 277
 278 On introduit un nouveau symbolisme (développé dans la suite) pour cette même grammaire ; il se comprend aisément :
 279
 280 $$\begin{array}{ccl}
 281 E & -> &T\\
 282 E & -> &T + E\\
 283 T & -> &F\\
 284 T & -> &F * T\\
 285 F & -> &( E )\\
 286 F & -> &a\\
 287 F & -> &b\\
 288 &...&\\
 289 F & -> & z\\
 290 \end{array}$$
 291
 292
 293 \noindent ...en admettant comme symboles de variables les caractères alphabétiques minuscules.\\
 294
 295
 296 \subsection{Algorithme de construction}
 297
 298 Le principe est de construire un automate à pile non déterministe qui admet des transitions vides :
 299
 300 \begin{enumerate}
 301  \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).
 302 %  \item Quelle que soit l'entrée qui se présente,
 303 % \begin{itemize}
 304 %  \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,
 305 %  \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.
 306 % \end{itemize}
 307 \item associer à chaque règle non terminale une $\epsilon$-transition qui empile les symboles de la partie droite (\emph{c.f.} transitions (2) à (6))
 308 \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))
 309 \item associer à chaque symbole terminal une transition qui reconnaît ce symbole et dépile ce caractère (\emph{c.f.} transitions (9) à (12))
 310 \end{enumerate}
 311
 312
 313 \bigskip
 314
 315 On obtient les transitions suivantes :
 316 $$
 317 \begin{array}{llll}
 318 (1) & (e_0,\varepsilon,p_0) &\longmapsto &(e_0,E)\\
 319 (2) & (e_0,\varepsilon,E) &\longmapsto &(e_0,T)\\
 320 (3) & (e_0,\varepsilon,E) &\longmapsto &(e_0,T+E)\\
 321 (4) & (e_0,\varepsilon,T) &\longmapsto &(e_0,F)\\
 322 (5) & (e_0,\varepsilon,T) &\longmapsto &(e_0,F*T)\\
 323 (6) & (e_0,\varepsilon,F) &\longmapsto &(e_0,(E))\\
 324 (7) & (e_0,a,F) &\longmapsto &(e_0,\varepsilon)\\
 325 \vdots & \vdots & \vdots & \vdots \\
 326 (8) & (e_0,z,F) &\longmapsto &(e_0,\varepsilon)\\
 327 (9) & (e_0,+,+) &\longmapsto &(e_0,\varepsilon)\\
 328 (10) & (e_0,*,*) &\longmapsto & (e_0,\varepsilon)\\
 329 (11) & (e_0,(,() &\longmapsto & (e_0,\varepsilon)\\
 330 (12) & (e_0,),)) &\longmapsto & (e_0,\varepsilon)\\
 331 \end{array}$$
 332
 333
 334
 335 \subsection{Exercices}
 336
 337 \begin{Exo}
 338 Soit l'automate à pile défini par $\Sigma=\{a,b\}$, $E=\{q_0,q_1,q_2\}$, $P=\{p_, A\}$ et les transitions suivantes
 339
 340 \begin{eqnarray*}
 341 (q_0,a,p_0) & \mapsto&  (q_1,A) \\
 342 (q_1,b,A) & \mapsto&  (q_2,\epsilon) \\
 343 (q_1,a,p) & \mapsto&  (q_1,Ap)\\
 344 (q_2,b,A) & \mapsto&  (q_2,\epsilon) \\
 345 \end{eqnarray*}
 346 \begin{enumerate}
 347 \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.
 348 \item Donner l'enchanement des transitions conduisant à l'échec de l'acceptation de la chaîne $aaba$.
 349 \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.
 350 \end{enumerate}
 351 \end{Exo}
 352
 353
 354
 355 \begin{Exo}
 356 Pour $u \in \Sigma^*$ , on note $|u|_a$ le nombre de $a$ dans $u$ et $|u|_b$ le nombre de $b$ dans $u$.
 357
 358 Donner un automate à pile qui reconnaît $L = \{u \in \Sigma^*, |u|_a = |u|_b \}$.
 359 \end{Exo}
 360
 361
 362 \begin{Exo}
 363 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.
 364 \end{Exo}
 365
 366
 367 \begin{Exo}
 368 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\}$$
 369 Préciser si l’automate est déterministe.
 370 \end{Exo}
 371
 372 \begin{Exo}
 373 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\}$$
 374 Préciser si l’automate est déterministe.
 375 \end{Exo}
 376
 377 \begin{Exo}
 378 Soit $G$ la grammaire suivante :
 379 $$S \rightarrow aAB ~~~ A \rightarrow aAB | a ~~~ B \rightarrow bBA | aC ~~~ C \rightarrow BaA.$$
 380 \begin{enumerate}
 381 \item Donner des exemples de mots reconnus.
 382 \item Donner un automate à pile qui reconnaît le langage généré par la grammaire $G$.
 383 \end{enumerate}
 384 \end{Exo}
 385
 386
 387 \begin{Exo}
 388 Soit $G$ la grammaire suivante :
 389 $$S \rightarrow aAB ~~~ A \rightarrow aAB | a ~~~ B \rightarrow bBA | aC | b ~~~ C \rightarrow BaA.$$
 390 Donner un automate à pile qui reconnaît le langage généré par la grammaire $G$.
 391 \end{Exo}
 392
 393
 394 \gsaut
 395 \centerline{\x{Fin du Chapitre}}
 396