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éorie des langages et des automates ines.channoufi@esprit.tn 2013-2014 PLAN

Théorie des langages et des automates ines.channoufi@esprit.tn 2013-2014 PLAN Généralités. Définition. Exemple introductif Transitions dans un PDA 2 Transitions dans un PDA Configurations Langage reconnu par un PDA INTRODUCTION 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 finis 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 fini pour obtenir un modèle de programmes plus puissant connu sous le nom de “automate à pile”. 3 INTRODUCTION Grammaire hors contexte (CFG) Grammaire régulière Langage régulier 4 Langage hors contexte (CFL) Automate à pile Langage régulier Automate fini AUTOMATE À PILE Un automate à pile ressemble à un automate fini. Il a : − Une mémoire de lecture et un pointeur vers le prochain symbole à lire; − un nombre fini d’états, y compris un état initial et des états accepteurs; − une relation de transition. 5 La diffé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 infini d’états. AUTOMATE À PILE Un automate à pile a : −Une entrée et une tête de lecture. −Un nombre fini d’états dont un état initial et des états accepteurs. −Une relation de transition. 6 −Une relation de transition. −Une pile pouvant croître arbitrairement. Automate à pile entrée pile $ $ AUTOMATE À 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. 7 fonction du token courant. Automate à pile entrée pile 1 2 3 4 $ $ DÉFINITION FORMELLE Un automate à piles A = 〈E, Σ, Π, δ, e0, z0, F 〉 E : un ensemble fini d’états. Σ un ensemble de symboles (l’alphabet des symboles d’entrée). Π est un alphabet fini dit l’alphabet de la pile. δ : Π* × E × (Σ ∪{ε}) →P (Π* × E), une fonction finie. ∈ 8 Un état e0 ∈E : état de départ ou état initial. z0 est le symbole initial de la pile. Un ensemble d’états F ⊆E connus comme états d’acceptation EXEMPLE INTRODUCTIF considérons l’automate fini A de la Figure suivante, qui reconnaît le langage {anbm, avec n > 0 et m > 0} et essayons d’étendre ce modèle pour en dériver un automate à pile capable de reconnaître {anbm, m = n > 0}. 1 2 a b 0 a b L’automate A est incapable de “compter” le nombre de a déjà vus, ce qui interdit 9 1 2 a b 0 le nombre de a déjà vus, ce qui interdit d’imposer la contrainte n = m. Confions alors cette tâche au mécanisme de pile, en empilant un symbole Z lors de chaque passage dans la boucle de l’état 1 et en dépilant un symbole lors de chaque passage dans la boucle de l’état 2. Si l’on impose, de plus, qu’un calcul réussi dans A doit correspondre à une pile intégralement vide, alors il apparaît que chaque mot reconnu par l’automate fini A augmenté de la pile est bien tel que le nombre de a est exactement égal au nombre de b. EXEMPLE INTRODUCTIF a b input state stack aaabbb 0 ε aabbb 1 ε abbb 1 Z 10 1 2 a b 0 abbb 1 Z bb 2 ZZ b 2 Z 2 ε UTILISATION D'UN AUTOMATE À PILE L'automate à pile va tenter de lire le mot aaabbb pour vérifier s'il appartient ou pas à L = {anbn , n>=0} qui n'est pas régulier sinon on aurait utilisé un AFD. L’idée consiste empiler un X (ou a) à la lecture d'un a et dès la lecture du premier b il commence à dépiler à partir de la pile. Chaque lecture d’un b signifie dépiler un X (ou a) de la pile. Il accepte le mot quand la chaine est lu et la pile devient vide . 11 UTILISATION D'UN AUTOMATE À PILE Entrée a a b b Lecture d’un a empiler X dans la pile 12 Pile Z0 Lecture d’un a empiler X dans la pile Symbole de pile vide Z0 et X représentent l’alphabet de la pile UTILISATION D'UN AUTOMATE À PILE Entrée a a b b Lecture d’un a empiler X dans la pile 13 Pile X Z0 Lecture d’un a empiler X dans la pile UTILISATION D'UN AUTOMATE À PILE Entrée a a b b X Lecture d’un a empiler X dans la pile 14 Pile X Z0 Lecture d’un a empiler X dans la pile UTILISATION D'UN AUTOMATE À PILE Entrée a a b b X Lecture d’un b dépiler X de la pile 15 Pile X Z0 Lecture d’un b dépiler X de la pile UTILISATION D'UN AUTOMATE À PILE Entrée a a b b Lecture d’un b dépiler X de la pile 16 Pile X Z0 Lecture d’un b dépiler X de la pile UTILISATION D'UN AUTOMATE À PILE Entrée a a b b Lecture d’un b dépiler X de la pile 17 Pile Z0 Lecture d’un b dépiler X de la pile Critères d’acceptations: 1. Mot lu + Etat final 2. Mot lu + Pile Vide TRANSITION Une transition dans un automate à pile s’écrit sous la forme suivante: (symbole lu, sommet de la pile, Action) Action: Signifie l’action réalisée par rapport à la pile. Action: Signifie l’action réalisée par rapport à la pile. Empiler symbole à empiler, sommet de la pile Dépiler ε Ne rien faire Z0 18 CONFIGURATIONS La configuration d’un automate est défini comme suit: (u,q,x, γ) u: mot lu, q: état courant, x: le reste à lire, γ: contenu de la pile. 19 γ: contenu de la pile. L’exécution d’un automate sur une entrée est la séquence de configurations qu’il produit en lisant son entrée et en suivant ses transitions. . AU-DELÀ DES LANGAGES HORS CONTEXTE − Bien qu’un automate à pile peut avoir un nombre infini d’états (configurations), il existe des langages qui ne sont pas acceptés par un automate à pile, c-à-d., des langages qui ne sont pas hors-contextes. − Exemple: L(M) = {an bn cn | n ≥0} 20 L(M) = {an bn cn | n ≥0} n’est pas hors-contexte. − Toutefois, il existe des modèles théoriques de programmes qui accepte un tel langage. En particulier, les machines de Turing sont des généralisations des automates à piles, pouvant accepter n’importe quel langage. uploads/Litterature/ ch4-les-automates-a-piles.pdf