Remerciez-le!

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

Automate a pile The ? orie des Langages et Calculabilite ? Chapitre IV Automates a piles Yousra Hlaoui FST-IF - Yousra Hlaoui FST-IF Automates a piles - CChapitre IV Automates apiles Pre ? sentation Automates a pile Transition d ? un automate apile Con ?g

The ? orie des Langages et Calculabilite ? Chapitre IV Automates a piles Yousra Hlaoui FST-IF - Yousra Hlaoui FST-IF Automates a piles - CChapitre IV Automates apiles Pre ? sentation Automates a pile Transition d ? un automate apile Con ?guration d ? un automate a pile Langages accepte ? s Automates a pile et langages non contextuels Yousra Hlaoui FST-IF Automates a piles - CPre ? sentation Pre ? sentation L ? automate ?ni permet de repre ? senter une grammaire re ? guliere Par suite il permet de reconna tre des mots d ? un langage re ? gulier associe ? a une grammaire re ? guliere A une regle A ? xB d ? une grammaire re ? gulie re on peut associer une transition A x B A x B Partant d ? une grammaire non contextuelle ayant une regle de production de la forme A ? xBy l ? automate doit se souvenir qu ? il doit lire la cha ne y apre s avoir lu la sous cha ne de ? rivant de B Pour cette raison on ajoute une pile al ? automate ?ni ou on empile ce que nous avons alire x et apre s avoir de ? rive ? la sous chaine de ? rivant de B on doit lire y et de ? piler le y de la pile On parle d ? automate a pile Yousra Hlaoui FST-IF Automates a piles - CAutomates a pile Pre ? sentation Description Pile z z z z q Ruban d ? entre ? e uuuuuuuuuu uuuuvuuuu L ? unite ? de contro le se trouve aun e ? tat q munie de deux te tes L E sur pile et L sur ruban d ? entre ? e Le ruban d ? entre ? e sert de support a un mot de X ? La lecture se fait de gauche adroite La pile est un ruban in ?ni du co te ? droit ou sont lus et e ? crits les symboles de la pile La case lue est toujours celle qui contient le symbole le plus a droite Yousra Hlaoui FST-IF Automates a piles - CAutomates apile Automates a pile De ? ?nition Un automate apile A est le tuplet A X Q q F ? Z ? Ou X est l ? alphabet d ? entre ? e Q est un ensemble non vide d ? e ? tats q ?? Q est l ? e ? tat initial F ? Q est l ? ensemble des e ? tats ?naux ou d ? acceptation ? est l ? alphabet de la pile pas ne ? cessairement disjoint de X Z ?? ? est le symbole initial de la pile symbole de fond de pile Z ?? X ? est l ? application de transition ? Q ? X ?? ? ? ?? ? P Q ? ? ? Yousra Hlaoui FST-IF Automates a piles - CAutomates apile Automates