Automate à piles intégrées

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En linguistique et en théorie des automates, un automate à piles intégrées en anglais « embedded pushdown automaton » ou EPDA est une automate pour la reconnaissance d'un langages engendré par une grammaire d'arbres adjoints (en anglais « tree-adjoining grammar » ou TAG).

Un tel automate ressemble à un automate à pile utilisé pour l’analyse des langages algébriques, mais à la place d'une pile simple contenant des symboles, il possède une pile composée de piles. Ainsi, la pile d'un EPDA est une constituée d'une suite de piles (ordinaires) juxtaposées. Ceci donne aux grammaires correspondantes une capacité générative plus importante et les situe entre les grammaires algébriques et les grammaires contextuelles ; ces grammaires forment un sous-ensemble des grammaires regroupées sous le terme de grammaires faiblement contextuelles (en).

Les automates à piles intégrées ne doivent pas être confondues avec les automates à piles emboîtées dont la puissance de reconnaissance est encore plus importante puisque ces derniers reconnaissent les langages indexés.

Description[modifier | modifier le code]

Les automates à piles intégrées (EPDA) ont été introduits par K. Vijay-Shanker en 1987 dans sa thèse de doctorat[1]. Les automates à piles intégrées reconnaissent la classe de langages d'arbres adjoints ; ils constituent une extension naturelle des automates à pile qui eux reconnaissent les langages algébriques. La caractéristique principales des EPDA est de remplacer la pile unique utilisée dans un automate à pile par une pile constituée elle-même de piles non vides. Ceci permet de réaliser des réécritures emboîtées sur l'élément de tête de la pile : en plus de la traiter comme une pile simple, on peut l'entourer de nouvelles piles. Cet aspect est fondamental dans la comparaison de la puissance de reconnaissance entre automates à pile et automates à piles intégrées. Alors que la pile simple d'une automate à pile usuel ne peut traiter que les emboîtements d'un langage algébrique, la pile de piles d'un EPDA peut gérer les dépendances croisées comme on les rencontre dans les langages d'arbres adjoints[2].

Définition informelle[modifier | modifier le code]

Un automate à piles intégrées est composé d'une unité de contrôle avec un nombre fini d'états, et d'une pile principale, composée d'une suite de piles non vides. L'unité de contrôle voit le symbole de tête de la pile de tête sur la pile principale, et la lettre courante du mot d'entrée. En fonction de ces données et de l'état courant, l’automate réalise une transition, composée de deux parties : dans un premier temps, la pile la plus haute dans la pile principale est traitée comme une pile ordinaire, c'est-à-dire que son symbole de tête est remplacé par une suite éventuellement vide de symboles de pile ; dans un deuxième temps, c'est la pile principale tout entière qui est considérée comme une pile ordinaire, et sa pile de tête, modifiée dans la première étape, est remplacée par une suite de piles qui, si elle n'est pas la suite vide, entoure la pile modifiée.

Comme dans le cas des automates à pile usuels, il y a deux modes d'acceptation. Un mot est accepté si, après la lecture du mot, l'automate termine avec la pile vide, ou alors le mot est accepté si l'automate termine en un état final. Comme dans le cas usuel, l'automate peut être déterministe ou non[2],[3].

Un exemple[modifier | modifier le code]

L'exemple qui suit est dans la thèse de Vijay-Shanker[1],[2]. C'est un EPDA qui accepte le langage . Son fonctionnement est le suivant. Chaque fois que l'automate lit une lettre a, il empile le symbole B sur la pile qui est en haut de la pile principale, et il insère, juste en-dessous ce la pile des B, une nouvelle pile contenant simplement le symbole D. Après avoir lu n lettres a, la pile principale est donc constituée de n piles contenant chacune un symbole D et, tout en haut, d'une pile contenant n symboles B. Pour chaque lettre b lue sur l'entrée, le symbole B en tête de la pile de tête est supprimé et de plus, une pile contenant simplement le symbole C est introduit juste en-dessous. Après avoir lu tous les b et supprimé la pile vide en haut de la pile principale, celle-ci est composée de n piles contenant chacune un symbole C et de n piles contenant chacune une symbole D. Pour chaque lettre c lue, on supprime la pile C correspondante, et de même pour chaque lettre d, on supprime la pile D du haut. Le mot est accepté si la pile est vide.

Définition formelle[modifier | modifier le code]

L'automate[modifier | modifier le code]

Un automate à piles intégrées (EPDA) est une structure , où

  • est un ensemble fini d'états, est l'état initial et est l'ensemble des états terminaux.
  • est l'alphabet de pile, et est le symbole de fond de pile.
  • est l'alphabet d'entrée.
  • est la fonction de transition

dénote les parties finies et sert à décrire les mots de pile.

Configuration[modifier | modifier le code]

Une description instantanée ou configuration d'un EPDA est un quadruplet

élément de composé de l’état courant q, , du contenu de la pile de piles , de la partie déjà lue du mot d'entrée et de la partie encore à traiter. Le contenu s de la pile de piles est représenté par une suite de mots séparés par un symbole particulier . Ainsi, la suite des contenu des piles peut s'écrire comme un seul mot . Par convention, la pile du haut de la pile principale est le dernier mot , et l'élément de haut de la dernière pile est la dernière lettre de . La configuration initiale d'un EPDA et

où l'état initial est , il n'y a qu'une seule pile sur la pile réduite au fond de pile , et où toute l'entrée est encore à lire.

Transitions[modifier | modifier le code]

Pour une règle , une transition signifie que lorsque la pile principale s'écrit et le mot se termine par , la pile principale est remplacée par , pourvu que ; en d'autres termes, des piles décrites par sont insérée avant la dernière pile remplacée par et elle-même suivie de piles . Si en revanche , la pile où on a donc est remplacée par .

Dans la définition, des transitions spontanées ou epsilon transitions sont possibles, si le symbole examiné dans la règle est le mot vide.

Exemple[modifier | modifier le code]

Voici la description formelle de l’automate pour l'exemple esquissé plus haut Il comporte 4 états , pas d'état final parce qu'il reconnaît par pile vide, l'alphabet d'entrée est , l'aphabet de pile est , où est le symbole de fond de pile. La fonction de transition \delta est la suivante :

Les règles de transition (1)-(4) servent à empiler ou dépiler, les règles (5)-(8) à dépiler seulement.

Pour , on obtient le calcul suivant :

Automates d'ordre supérieur et hiérarchie de Weir[modifier | modifier le code]

La notion d'automate à piles intégrés a été étendu par David J. Weir[4],[5] à des automates d'ordre supérieur, appelés automates à piles imbriquées d'ordre k. Dans son premier travail, ces automates sont appelés Nested Push-Down Automata. La généralisation est comme suit : on appelle pile d'ordre 1 une pile simple, pile d'ordre 2 une pile de piles, et plus généralement pile d'ordre k une pile de piles d'ordre k-1. Dans un automate à pile usuel, la pile est d'ordre 1 ; dans un EPDA, la pile est d'ordre 2. Une opération de manipulation de la pile d'un EPDA consiste en une opération de pile sur la pile d'ordre 1 en tête de pile, puis sur une opération de pile sur la pile principale, d'ordre 2. Cette opération peut être étendue à des piles d'ordre k : on opère récursivement sur la pile d'ordre k-& en haut de pile, puis sur la pile d'ordre k.

Cette définition conduit à une hiérarchie d'automate, appelée la hiérarchie de Weir. La première classe de cette hiérarchie, les EPDA d'ordre 1, sont les automates à mile qui reconnaissent les langages algébriques. La deuxième classe, les EPDA d'ordre 2, sont les automates à piles intégrées de Vijay-Shanker définis plus haut et reconnaissent exactement les langages d'arbres adjoints.

La hiérarchie de Weir est stricte : chacune des classe contient strictement la classe précédente :

  • la classe de langes d'ordre k contient , mais pas ,
  • ou encore , mais .

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Embedded pushdown automaton » (voir la liste des auteurs).

Bibliographie[modifier | modifier le code]

  • Laura Kallmeyer, Parsing Beyond Context-Free Grammars, Springer Science & Business Media, (ISBN 978-3-642-14846-0), chap. 10.1 (« Embedded Push-Down Automata ») Document utilisé pour la rédaction de l’article
  • Aravind K. Joshi et Yves Schabes, « Tree-adjoining grammars », dans G. Rosenberg et A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 3 : Beyond Words, Springer, , p. 69-123.
  • David J. Weir, Characterizing mildly context sensitive languages, thèse de doctorat, université de Pennsylvanie, .
  • David J. Weir, « A geometric hierarchy beyond context-free languages », Theoretical computer science, vol. 104, no 2,‎ , p. 235–261 (DOI 10.1016/0304-3975(92)90124-X, lire en ligne).
  • K. Vijay-Shanker, A study of tree adjoining grammars, thèse de doctorat, université de Pennsylvanie, (présentation en ligne).

Articles liés[modifier | modifier le code]