Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Th´ eorie des Langages et Calculabilit´ e Chapitre IV Automates ` a piles Yousr

Th´ eorie des Langages et Calculabilit´ e Chapitre IV Automates ` a piles Yousra Hlaoui FST-IF4 2018-2019 Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 1 / 26 Chapitre IV Automates ` a piles 1 Pr´ esentation 2 Automates ` a pile Transition d’un automate ` a pile Conﬁguration d’un automate ` a pile 3 Langages accept´ es 4 Automates ` a pile et langages non contextuels Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 2 / 26 Pr´ esentation Pr´ esentation L ’automate ﬁni permet de repr´ esenter une grammaire r´ eguli` ere. Par suite, il permet de reconnaˆ ıtre des mots d’un langage r´ egulier (associ´ e ` a une grammaire r´ eguli` ere). ` A une r` egle (A →xB) d’une grammaire r´ eguli` ere, on peut associer une transition (A, x, B) A B x Partant d’une grammaire non contextuelle ayant une r` egle de production de la forme (A →xBy), l’automate doit se souvenir qu’il doit lire la chaˆ ıne y apr` es avoir lu la sous chaˆ ıne d´ erivant de B. Pour cette raison, on ajoute une pile ` a l’automate ﬁni o` u on empile ce que nous avons ` a lire(x) et apr` es avoir d´ eriv´ e la sous chaine d´ erivant de B, on doit lire y et d´ epiler le y de la pile. On parle d’automate ` a pile. Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 3 / 26 Pr´ esentation Automates ` a pile Description z0 Pile Ruban d’entr´ ee z0 z0 z0 q uuuuuuuuuu uuuuvuuuu L ’unit´ e de contrˆ ole, se trouve ` a un ´ etat q munie de deux tˆ etes (L/E sur pile et L sur ruban d’entr´ ee). Le ruban d’entr´ ee sert de support ` a un mot de X ∗. La lecture se fait de gauche ` a droite. La pile est un ruban inﬁni du cˆ ot´ e droit o` u sont lus et ´ ecrits les symboles de la pile. La case lue est toujours celle qui contient le symbole le plus ` a droite. Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 4 / 26 Automates ` a pile Automates ` a pile D´ eﬁnition Un automate ` a pile A est le tuplet A =< X, Q, q0, F, Γ, Z0, δ > O` u : X est l’alphabet d’entr´ ee Q est un ensemble non vide d’´ etats q0 ∈Q est l’´ etat initial F ⊂Q est l’ensemble des ´ etats ﬁnaux ou d’acceptation Γ est l’alphabet de la pile ( pas n´ ecessairement disjoint de X) Z0 ∈Γ est le symbole initial de la pile (symbole de fond de pile)(Z0 / ∈X) δ est l’application de transition. δ : Q × (X ∪{ε}) × (Γ ∪{ε}) →P(Q × Γ∗) Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 5 / 26 Automates ` a pile Automates ` a pile Exemple 1 : un automate ` a pile qui accepte le langage :{ancbn/n ≥0} q0 q1 (c, a, a)(c, Z0, Z0) (a, Z0, Z0a) (a, a, aa) (b, a, ε) (ε, Z0, ε) Commencer par empiler tous les a, On doit lire un c, le c peut ˆ etre pr´ ec´ ed´ e d’un a comme il peut ˆ etre le seule symbole dans le mot Dans les deux cas, il ne doit pas ˆ etre empil´ e et il faut changer d’´ etat pour s´ eparer la lecture des a de la lecture des b. Si on lit un b alors il doit ˆ etre pr´ ec´ ed´ e d’un a. On le d´ epile et on continue ` a accepter uniquement des b et d´ epiler les a correspondants. A la ﬁn, il faut arriver ` a vider la pile Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 6 / 26 Automates ` a pile Automates ` a pile Exemple 2 : un automate ` a pile qui accepte le langage :{ωcωR} q0 q1 (c, ε, ε)(3) (a, ε, a)(1)(b, ε, b)(2) (a, a, ε)(4) (b, b, ε)(5) Etat Entr´ ee non encore lue Pile Transition utilis´ ee q0 abbcbba Z0 − q0 bbcbba Z0a (1) q0 bcbba Z0ab (2) q0 cbba Z0abb (2) q1 bba Z0abb (3) q1 ba Z0ab (5) q1 a Z0a (5) q1 ε Z0 (4) Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 7 / 26 Automates ` a pile Transition d’un automate ` a pile Transition d’un automate ` a pile D´ eﬁnition 3 (Transition) Une transition est de la forme δ(q0, c, s) = (q1, ω), avec : (c, s, ω) ∈X ∪{ε} × Γ ∪{ε} × Γ∗ c est le caract` ere lu sur l’entr´ ee. s est le sommet de la pile. ω est le mot qui remplace s sur la pile. q0 q1 (c, s, ω) Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 8 / 26 Automates ` a pile Transition d’un automate ` a pile Transition d’un automate ` a pile Exemples de signiﬁcation d’´ etiquettes de transitions (a, b, ba) : si a est sur la bande d’entr´ ee et b est au sommet de la pile, alors on empile a. (a, b, ε) : si a est sur la bande d’entr´ ee et b est au sommet de la pile, alors b est d´ epil´ e. (a, a, b) : si a est sur la bande d’entr´ ee et a est au sommet de la pile, alors a est d´ epil´ e et b est empil´ e. (a, b, a) : si a est sur la bande d’entr´ ee et b est au sommet de la pile, alors b est d´ epil´ e et a est empil´ e. (a, b, bbaa) : si a est sur la bande d’entr´ ee et b est au sommet de la pile, alors aab est empil´ e. (a, a, aa) : si a est sur la bande d’entr´ ee et a est au sommet de la pile, alors un nouveau a est empil´ e. (ε, a, a) : sans lire le symbole en entr´ ee, si a est au sommet de la pile, alors il reste au sommet de la pile. Dans ce cas, la tˆ ete de lecture ne bouge pas. Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 9 / 26 Automates ` a pile Transition d’un automate ` a pile Transition d’un automate ` a pile Exemples de signiﬁcation des ´ etiquettes de transitions (suite) (ε, ε, b) : sans lire le symbole en entr´ ee ni le sommet de la pile, b est empil´ e. Dans ce cas, la tˆ ete de lecture ne bouge pas. (ε, a, ε) : sans lire le symbole en entr´ ee, si a est au sommet de la pile, alors, il n’est pas remis. Dans ce cas, la tˆ ete de lecture ne bouge pas et a est tout simplement d´ epil´ e. (ε, ε, ε) : correspond ` a un changement d’´ etat sans aucun changement sur l’entr´ ee ni sur la pile. Si dans un ´ etat donn´ e apparaˆ ıt seulement cette transition, elle doit ˆ etre effectu´ ee, car l’automate ne peut pas avoir un comportement passif. (ε, Z0, Z0c) : La tˆ ete de lecture ne bouge pas et c est empil´ e sur une pile vide. (a, Z0, Z0a) : si a est sur la bande d’entr´ ee et la pile est vide, alors on empile a. (ε, Z0, ε) : vider la pile. Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 10 / 26 Automates ` a pile Conﬁguration d’un automate ` a pile Conﬁguration d’un automate ` a pile D´ eﬁnition (Conﬁguration) Une conﬁguration d´ etermine de mani` ere pr´ ecise le comportement d’un automate. Elle sp´ eciﬁe tous les aspects pertinents de la machine dans une situation donn´ ee. Formellement, une conﬁguration est un triplet (q, m, u) ∈(Q × X ∗× Γ∗), avec : q est l’´ etat courant de l’unit´ e de contrˆ ole m repr´ esente la partie du mot ` a reconnaˆ ıtre non encore lue. Le symbole le plus ` a gauche de m est le caract` ere sous la tˆ ete de lecture. u est le contenu de la pile. Le symbole le plus ` a droite de u est le sommet de la pile. Pour sp´ eciﬁer, formellement, le comportement de l’automate ` a pile, on dira que (q′, ω, uv R) se d´ erive en une ´ etape ` a partir de (q, aω, ub) o` u (q′, v) ∈δ(q, a, b). On note (q, aω, ub) ⊢M (q′, ω, uv R) Yousra Hlaoui (FST-IF4) Automates ` a piles 2018-2019 11 / 26 Automates ` a pile Conﬁguration d’un automate ` a pile Conﬁguration d’un automate ` a pile D´ eﬁnition (Conﬁguration) - Suite Lors du mouvement (q, aω, ub) ⊢M (q′, ω, uv R) : l’unit´ e de contrˆ ole passe de q ` a q′ le symbole a a ´ et´ e uploads/S4/ automate-a-pile.pdf