Remerciez-le!

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

Ch4 les automates a piles Théorie des langages et des automates ines channou ? esprit tn - CPLAN Généralités Dé ?nition Exemple introductif Transitions dans un PDA Con ?gurations Langage reconnu par un PDA CINTRODUCTION Par analogie avec les expressions r

Théorie des langages et des automates ines channou ? esprit tn - CPLAN Généralités Dé ?nition Exemple introductif Transitions dans un PDA Con ?gurations Langage reconnu par un PDA CINTRODUCTION Par analogie avec les expressions régulières qui engendrent les langages réguliers les grammaires hors contextes engendrent les langages hors contexte Aussi par analogie avec automates à états ?nis qui reconnaissent les langages réguliers les automates à pile reconnaissent les langages hors contextes Pour analyser la syntaxe d ? une grammaire hors- contexte nous ajoutons une pile à un automate ?ni pour obtenir un modèle de programmes plus puissant connu sous le nom de ??automate à pile ? CINTRODUCTION Grammaire hors contexte CFG Grammaire régulière Langage hors contexte CFL Automate à pile Langage régulier Automate ?ni CAUTOMATE À PILE Un automate à pile ressemble à un automate ?ni Il a ?? Une mémoire de lecture et un pointeur vers le prochain symbole à lire ?? un nombre ?ni d ? états y compris un état initial et des états accepteurs ?? une relation de transition La di ?érence est qu ? un automate à pile a en plus une pile initialement vide mais pouvant cro? tre arbitrairement Le contenu de la pile fait partie de l ? état d ? un automate Donc un automate à pile a potentiellement un nombre in ?ni d ? états CAUTOMATE À PILE Un automate à pile a ?? Une entrée et une tête de lecture ?? Un nombre ?ni d ? états dont un état initial et des états accepteurs ?? Une relation de transition ?? Une pile pouvant cro? tre arbitrairement entrée Automate à pile pile CAUTOMATE À PILE L ? entrée est une cha? ne de tokens scanné à partir du code source du programme à analyser La pile contient une cha? ne de symbole de la grammaire terminaux et non-terminaux Les transitions indiquent comment mettre à jour le contenu de la pile en fonction du token courant entrée Automate à pile pile CDÉFINITION FORMELLE Un automate à piles A ? E ? ? ? e z F ? E un ensemble ?ni d ? états ? un ensemble de symboles l ? alphabet des symboles d ? entrée ? est un alphabet ?ni dit l ? alphabet de la pile ? ? ? E ? ? ?? ? P ? ? E une fonction ?nie Un état e ?? E état de départ ou état initial z est le symbole initial de la pile Un ensemble d ? états F ? E connus comme états d ? acceptation CEXEMPLE INTRODUCTIF considérons l ? automate ?ni A de la Figure suivante qui reconna? t le langage anbm avec n et m et essayons d ? étendre ce modèle pour en dériver un automate à pile capable de reconna? tre anbm m n a b L ? automate A est incapable de ??compter ? a b le nombre de a déjà vus ce qui interdit d ? imposer la contrainte n m Con