CHAP 1 AUTOMATE À PILE – DÉFINITIONS ET MODÈLES
1.1 Introduction
1.2 Définitions et exemple
1.3 Généralisation de la forme des transitions
1.4 Restriction de la forme des transitions
1.5 Autres modes de reconnaissance. Configurations
Reconnaissance par état acceptant
Reconnaissance par pile vide
Configurations
CHAP. 2 EQUIVALENCE DES MODES DE RECONNAISSANCE
2.1 Equivalence des modes d’initialisation (états acceptants spécifiés)
2.2 Equivalence des modes de reconnaissance
2.3 Laquelle de ces variantes allons-nous privilégier ?
CHAP. 3 AUTOMATES À PILE ET GRAMMAIRES ALGÉBRIQUES
3.1 Automate à pile associé à une grammaire algébrique
3.2 Construction simplifiée (grammaire sous forme de Greibach)
3.3 Exemple
3.4 Grammaire algébrique associée à un automate à pile
CHAP. 4 QUELQUES OPÉRATIONS SUR LES LANGAGES ALGÉBRIQUES
4.1 Opérations régulières sur les langages algébriques
4.2 Intersections et compléments de langages
CHAP. 5 LE « LEMME DE L’ETOILE »
5.1 Le Lemme de l’Etoile (cas d’une grammaire algébrique)
5.2 Exemples d’application du Lemme de l’Etoile
CHAP. 6 AUTOMATES À PILE DÉTERMINISTES
6.1 Définition et exemple
6.2 Discussion des modes de reconnaissance
6.3 Des exemples parmi les palindromes
RÉFÉRENCES
Chap. 1 Automate à pile – Définitions et modèles
Conventions
En accord avec la convention maintenant adoptée par la plupart des références bibliographiques, nous noterons ε la chaîne vide, ou une étiquette vide pour une transition.
Dorénavant, nous dirons simplement « automate » pour un ε–automate, c’est-à-dire dans le cas où des transitions d’étiquette vide sont autorisées. Lorsque l’étiquette d’une transition devra être non vide, nous le préciserons.
On rappelle que dans une pile, l’élément qui se trouve en haut est le dernier à avoir été empilé et le premier que l’on peut dépiler. En représentant une pile « à l’horizontale », par une chaîne de symboles, on écrit de gauche à droite les symboles tels qu’ils figurent de haut en bas dans la pile. Le premier symbole (celui de gauche) est celui du haut de la pile.
Chap. 2 Equivalence des modes de reconnaissance
L’objectif est de prouver que si un langage est reconnu selon un certain mode de reconnaissance, alors ce langage est aussi reconnu selon n’importe quel autre de ces modes.
Les constructions qui suivent peuvent aussi être vues comme une série d’exercices permettant de s’habituer à la manipulation des automates à pile et des notions vues jusqu’à présent. Le lecteur pressé peut se reporter directement à la section 2.3 , où la forme exacte de l’automate à pile qui sera utilisé par la suite est précisée dans la Proposition.
Chap. 3 Automates à pile et grammaires algébriques
Les langages produits par les grammaires algébriques (dites aussi : hors-contexte) sont les langages reconnus par les automates à pile. Les constructions respectives se font explicitement.
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Automates à pile et grammaire algébriques (336.49 KB) (Cours PDF)
