Remerciez-le!

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

Automates a piles V Les automates à Piles Plan V Présentation Dé ?nition d ? un automate à pile V Description d ? un automate à pile Exemple d ? automate à Pile V Fonctionnement d ? un automate à pile Langages acceptés par des automates V à pile Construct

V Les automates à Piles Plan V Présentation Dé ?nition d ? un automate à pile V Description d ? un automate à pile Exemple d ? automate à Pile V Fonctionnement d ? un automate à pile Langages acceptés par des automates V à pile Construction d ? un automate à pile à partir V d ? une grammaire non contextuelle V CV Présentation L ? automate ?ni 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 Ax B 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 ?ni 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 CV Dé ?nition d ? un automate à pile Un automate à pile A est un septuplet A X Q q F ?? Z ? O? X est un alphabet Q est un ensemble d ? états q ? Q est l ? état initial F ?? Q est l ? ensemble des états ?naux ?? est le vocabulaire de la pile Z est le symbole initial de la pile symbole de fond de pile ? est une fonction de transition ? Q x X ?? ? x ?? parties ?nies de Q x ?? CV Description d ? un automate à pile Z Tête de lecture écriture q Unité de contrôle Tête de lecture U V Pile 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 in ?ni 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 CV Exemple d ? un automate à pile qui accepte ancbn n ? a Z Z a a a aa q c a a c Z Z q b a ? ? Z ? ? 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 êptraes empilé et il faut changer d ? état pour séparer la