Remerciez-le!

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

Chapitre 3 automates a piles

Chapitre Langages hors-contexte et automates à piles Enseignant Manel Ben Salem Niveau ième Licence SI - Plan du cour Grammaires hors-contexte Arbres syntaxiques Automates à piles Automates à piles déterministes Théorie des langages et des automates Chapitre Langages hors-contexte et automates à piles C Grammaire hors-contexte Théorie des langages et des automates Chapitre Langages hors-contexte et automates à piles ? Certains langages ne peuvent pas être décrits par une grammaire régulière et ne peuvent donc pas être reconnus par un automate ?ni par exemple le langage anbn n ? Appartiennent à une classe de langages plus générale que celle des langages réguliers la classe des langages hors- contexte décrits par des grammaires hors-contextes et reconnus par des automates à pile ? Dé ?nition Grammaire hors-contexte G T N S R est une grammaire hors-contexte si toutes les règles de R sont de la forme A ? w avec A ?? N et w ?? N ?? T ? ? Dé ?nition Langage hors-contexte On appelle langage hors-contexte un langage généré par une grammaire hors contexte ? On rappelle qu ? un ensemble est fermé relativement à une opération à n opérandes si tout résultat de cette opération appliquée à n éléments de l ? ensemble appartient encore à l ? ensemble Grammaire hors-contexte Théorie des langages et des automates Chapitre Langages hors-contexte et automates à piles ? Théorème ?? l ? union de deux langages hors-contexte est un langage hors- contexte ?? le produit de deux langages hors-contexte est un langage hors- contexte ?? l ? itéré d ? un langage hors contexte est un langage hors contexte En e ?et soient deux langages L généré par la grammaire G T N S R et L généré par la grammaire G T N S R tels que N ?? N ? si tel n ? est pas le cas on renomme certains éléments non-terminaux alors ?? Le langage L ?? L est généré par la grammaire hors contexte G T N S R telle que ? T T ?? T ? S est un nouveau symbole non terminal S ?? N ?? N ? N N ?? N ?? S ? R R ?? R ?? S ? S S ? S C Grammaire hors-contexte Théorie des langages et des automates Chapitre Langages hors-contexte et automates à piles ?? Le langage L L est généré par la grammaire hors contexte G T N S R telle que ? T T ?? T ? S est un nouveau symbole non terminal S ?? N ?? N ? N N ?? N ?? S ? R R ?? R ?? S ? S S ?? Le langage L ? est généré par la grammaire hors contexte G T N S R telle que ? S est un nouveau symbole non terminal S ?? N ?? N ? N N ?? S ? R R ?? S ? S S S ? En revanche l ? intersection de deux langages hors-contexte et le