Remerciez-le!

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

V . Les automates à Piles 1 Plan V.1 . V.2 . V.3 . V.4 . V.5 . V.6 Présentation

V . Les automates à Piles 1 Plan V.1 . V.2 . V.3 . V.4 . V.5 . V.6 Présentation Définition d’un automate à pile Description d’un automate à pile Exemple d’automate à Pile Fonctionnement d’un automate à pile Langages acceptés par des automates à pile Construction d’un automate à pile à partir d’une grammaire non contextuelle V.1. Présentation L’automate fini permet de représenter une grammaire régulière. Par suite, il permet de reconnaître des mots d’un langage régulier (associé à une grammaire régulière). À une règle (A  x B) d’une grammaire régulière, on peut associer une transition (A, x, B) A B x Partant d’une grammaire non contextuelle ayant une règle de production de la forme (A  x B y), l’automate doit se souvenir qu’il doit lire la chaine y après avoir lu la sous chaine dérivant de B. Pour cette raison, on ajoute une pile à l’automate fini où on empile ce que nous avons à lire (y) et après avoir dérivé la sous chaine dérivant de B, on doit lire y et dépiler le y de la pile. On parle d’automate à pile 2 V.2. Définition d’un automate à pile 3 Un automate à pile A est un septuplet A = < X, Q, q0, F, , Z0, > Où X est un alphabet Q est un ensemble d’états q0  Q est l’état initial F  Q est l’ensemble des états finaux  est le vocabulaire de la pile Z0 est le symbole initial de la pile (symbole de fond de pile)  est une fonction de transition  : Q x (X  {}) x   { parties finies de Q x *} V.3. Description d’un automate à pile q Z0 Pile Tête de lecture/écriture Unité de contrôle U V 4 Tête de lecture Ruban d’entrée L’unité de contrôle, se trouve à un état q munie de deux têtes (L/E sur pile et L sur ruban d’entrée). Le ruban d’entrée sert de support à un mot de X*. La lecture se fait de gauche à droite. La pile est un ruban infini du côté droit où sont lus et écrits les symboles de la pile (*). La case lue est toujours celle qui contient le symbole le plus à droite. V.4. Exemple d’un automate à pile qui accepte {ancbn / n 0} q0 (a, Z0, Z0a) (a, a, aa) (c, a, a) •Commencer par empiler tous les a •On doit lire un c • Le c peut être précédé d’un a comme il peut être le seule symbole dans le mot •Dans les deux cas, il ne doit pas q1 (c, Z0 , Z0) (b, a, ) (, Z0, ) 5 être empilé et il faut changer d’état pour séparer la lecture des a de la lecture des b. •si on lit un b alors il doit être précédé d’un a. On le dépile et on continue à accepter uniquement des b et dépiler les a correspondants. •A la fin, il faut arriver à vider la pile Exemple d’un automate à pile qui accepte {ancbn / n 0} suite Acceptation du mot aacbb a a c b b q0 Z0 a a c b b q0 Z0a a a c b b q0 Z0aa a a c b b q1 Z0aa a a c b b Z0 a a c b b q1 q1 a a c b b q1 Z0a a c b b q0 Z0 a c b b q0 Z0a a c b b q1 Z0a Le mot aacbb est lu et la pile est vide alors il est accepté Rejet du mot acbb a c b b q1 6 Z0 Le mot acbb n’est pas accepté par ce que le mot n’est pas entièrement lu. La transition de q1 avec b, Z0 n’est pas définie. Exemple d’un automate à pile qui accepte {ancbn / n 0} suite a a c b q0 Z0 a a c b q0 Z0a a a c b q0 Z0aa Le mot c est accepté C C C q0 q1 q1 Z0 Z0 Le mot c est lu et la pile est vide alors il est accepté Rejet du mot aacb a a c b q1 Z0aa a a c b q1 7 Z0a Le mot aacb n’est pas accepté par ce que on n’arrive pas à vider la pile V.5. Fonctionnement d’un automate à pile 8 a- Configuration Une configuration d’un automate à pile est le contenu des deux rubans, d’un état et de la lettre à lire  = (U, q, aV, Z) Où Le contenu du ruban d’entrée est : UaV Le contenu de la pile est : Z avec  * Z   : somm et de pile La configuration initiale est : (, q0, , Z0) U =  par ce que rien n’a été lu donc  lu aV =  puisqu’il reste tout le mot à lire L’état initial est q0 Le symbole sommet de pile est le symbole fond de pile Z0 puisque la pile est vide initialement V.5. Fonctionnement d’un automate à pile 9 b. Configuration successeur de  = (U, q, aV, Z)  est une configuration successeur de  qu’on note  |--  si Si (qi, i)  δ(q, a, Z) alors  = (Ua, qi, V,  i) (qi, i)  δ(q, , Z) alors  = (U, qi, aV,  i) Autrement dit, le symbole a peut ou non être lu ( transition, sans consommer un symbole), l’unité de contrôle passe de l’état q à l’état qi. Le symbole au sommet Z est remplacé par i c. Configuration k successeur k  |--    |-- 1 |-- 2 |-- … k / k =  * k  |--   k0  |--  + k  |--   k>0  |--  V.5. Langages acceptés par un automate à pile 10 Deux critères d’acceptation sont définis pour un automate à pile - Le critère pile vide (mot accepté = mot lu + pile vide) - Le critère état final (mot accepté = mot lu + état final) Pour un automate à pile A= <X, Q, q0, F, , Z0,  >, L(A) désigne le langage accepté avec le critère pile vide c-a-d un mot  est accepté par A ssi en partant d’une pile contenant Z0 comme symbole de fond de pile, après la lecture du mot, on arrive à vider la pile. N(A), le langage accepté avec le critère état final c-a-d un mot  est accepté par A ssi en partant d’une pile contenant Z0 comme symbole de fond de pile, après la lecture du mot, on arrive à un état final ; pas de soucis sur le contenu de la pile. V.5. Langages acceptés par un automate à pile 11 Pour un automate à pile A, deux langages sont acceptés L(A) et N(A) qui peuvent être vides (cas de N(A) lorsqu’il n’ya pas d’état final N(A) =  si F = ) * * L(A) = {  X* / (, q0,  , Z0) |-- ( , q, , )} N(A) = {  X* / (, q0,  , Z0) |-- (, qF, , )/ qF  F} On n’a pas toujours L(A) = N(A) mais on a :  A’ / L(A) = N(A’) et  A’’/ L(A’’) = N(A) V.5. Langages acceptés par un automate à pile q0 Pour un automate à pile A sans état final,N(A) =  (a, Z0, Z0a) Pour l’automate A suivant : L(A) = {anbn / n 1} N(A) = {aibj / i j>0} 12 A (a, a, aa) q1 (b, a, ) (b, a, ) (, Z0, ) a2b2  L(A) en effet (, q0, aabb, Z0) |-- (a, q0, abb, Z0 a) |-- (aa, q0, bb, Z0 aa) |-- (aab, q1, b, Z0 a) |-- (aabb, q1, , Z0 )|-- (aabb, q1,  ,  ) a2b  N(A) en effet ( , q0, aab , Z0) |-- (a, q0, ab, Z0 a) |-- (aa, q0, b, Z0 aa) |-- (aab, q1,  , Z0 a) V.6. Construction d’un automate à pile à partir d’une grammaire non contextuelle (GNC) Définition. Un langage est dit non contextuel ou indépendant du contexte ou hors contexte s’il existe un automate à pile qui l’accepte Construction d’un automate à pile à partir d’une grammaire non contextuelle Soit G = (V, T , S, R) une GNC, il existe un automate à pile A / N(A) = L(G) A = < X, Q, q0, F, , Z0, > Où X = T 13 Q = {q0, q1} F = {q1} = X  {Z0}  / (q0, , Z0) = (q1, S) (q1, , A) = (q1, ) (  A  ~  R  a  X V.6. Construction d’un automate à pile à partir d’une grammaire non contextuelle (GNC) V.6. Construction d’un automate à pile à partir d’une grammaire non contextuelle (GNC) uploads/Litterature/ automates-a-piles.pdf