Automate à piles intégrées

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

Les automates à piles intégrées (EPDA) ont été introduits par K. Vijay-Shanker en 1987 dans sa thèse de doctorat. 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.

Définition informelle

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.

Un exemple

L'exemple qui suit est dans la thèse de Vijay-Shanker. C'est un EPDA qui accepte le langage $L=\{a^{n}b^{n}c^{n}d^{n}\mid n\geq 0\}$. 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 un 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

L'automate

Un automate à piles intégrées (EPDA) est une structure $(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{F},Z_{0})$, où

• $Q$ est un ensemble fini d'états, $q_{0}\in Q$ est l'état initial et $Q_{F}\subseteq Q$ est l'ensemble des états terminaux.
• $\Gamma$ est l'alphabet de pile, et $Z_{0}\in \Gamma$ est le symbole de fond de pile.
• $\Sigma$ est l'alphabet d'entrée.
• $\delta :Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \to {\mathfrak {P}}_{f}(Q\times \Upsilon ^{*}\times \Gamma ^{*}\times \Upsilon ^{*})$ est la fonction de transition

où ${\mathfrak {P}}_{f}$ dénote les parties finies et $\Upsilon =\Gamma ^{*}$ sert à décrire les mots de pile.

Configuration

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

$(q,s,w_{1},w_{2})$

élément de $Q\times \Gamma ^{*}\times \Sigma ^{*}\times \Sigma ^{*}$ composé de l’état courant q, , du contenu de la pile de piles $s\in Y^{*}$, de la partie $w_{1}$ déjà lue du mot d'entrée et de la partie $w_{2}$ 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 $\ddagger$. Ainsi, la suite $(Y_{1},\ldots ,Y_{m})$ des contenus des piles peut s'écrire comme un seul mot $Y_{1}\ddagger \cdots \ddagger Y_{m}$. Par convention, la pile du haut de la pile principale est le dernier mot $Y_{m}$, et l'élément de haut de la dernière pile est la dernière lettre de $Y_{m}$. La configuration initiale d'un EPDA et

$(q_{0},\ddagger Z_{0},\varepsilon ,w)$

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

Transitions

Pour une règle $(p,\alpha _{1},\gamma ,\alpha _{2})\in \delta (q,a,Z)$, une transition signifie que lorsque la pile principale s'écrit $Y_{1}\ddagger \cdots \ddagger Y_{m}$ et le mot $Y_{m}=YZ$ se termine par $Z$, la pile principale est remplacée par $Y_{1}\ddagger \cdots \ddagger Y_{m-1}\alpha _{1}\ddagger Y\gamma \alpha _{2}$, pourvu que $Y\gamma \neq \varepsilon$; en d'autres termes, des piles décrites par $\alpha _{1}$ sont insérée avant la dernière pile $Y_{m}$ remplacée par $Y\gamma$ et elle-même suivie de piles $\alpha _{2}$. Si en revanche $Y\gamma =\varepsilon$, la pile $Y_{1}\ddagger \cdots \ddagger Y_{m}$ où on a donc $Y_{m}=Z$ est remplacée par $Y_{1}\ddagger \cdots \ddagger Y_{m-1}\alpha _{1}\alpha _{2}$.

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

Voici la description formelle de l’automate pour l'exemple esquissé plus haut Il comporte 4 états $Q=\{q_{0},q_{1},q_{2},q_{3}\}$, pas d'état final parce qu'il reconnaît par pile vide, l'alphabet d'entrée est $\Sigma =\{a,b,c,d\}$, l'alphabet de pile est $\Gamma =\{Z_{0},B,C,D\}$, où $Z_{0}$ est le symbole de fond de pile. La fonction de transition \delta est la suivante :

${\begin{aligned}&(1)\ \delta (q_{0},a,Z_{0})=(q_{0},\ddagger D,B,\varepsilon )\\&(2)\ \delta (q_{0},a,B)=(q_{0},\ddagger D,BB,\varepsilon )\\&(3)\ \delta (q_{0},b,B)=(q_{1},\ddagger C,\varepsilon ,\varepsilon )\\&(4)\ \delta (q_{1},b,B)=(q_{1},\ddagger C,\varepsilon ,\varepsilon )\\&(5)\ \delta (q_{1},c,C)=(q_{2},\varepsilon ,\varepsilon ,\varepsilon )\\&(6)\ \delta (q_{2},c,C)=(q_{2},\varepsilon ,\varepsilon ,\varepsilon )\\&(7)\ \delta (q_{2},d,D)=(q_{3},\varepsilon ,\varepsilon ,\varepsilon )\\&(8)\ \delta (q_{3},d,D)=(q_{3},\varepsilon ,\varepsilon ,\varepsilon )\end{aligned}}$

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

Pour $aaabbbcccddd$, on obtient le calcul suivant :

${\begin{aligned}(q_{0},\ddagger Z_{0},\varepsilon ,aaabbbcccddd)&{\stackrel {(1)}{\vdash }}(q_{0},\ddagger D\ddagger B,a,aabbbcccddd){\stackrel {(2)}{\vdash }}(q_{0},\ddagger D\ddagger D\ddagger BB,aa,abbbcccddd)\\&{\stackrel {(2)}{\vdash }}(q_{0},\ddagger D\ddagger D\ddagger D\ddagger BBB,aaa,bbbcccddd){\stackrel {(3)}{\vdash }}(q_{1},\ddagger D\ddagger D\ddagger D\ddagger C\ddagger BB,aaab,bbcccddd)\\&{\stackrel {(4)}{\vdash }}(q_{1},\ddagger D\ddagger D\ddagger D\ddagger C\ddagger C\ddagger B,aaabb,bcccddd){\stackrel {(4)}{\vdash }}(q_{1},\ddagger D\ddagger D\ddagger D\ddagger C\ddagger C\ddagger C,aaabbb,cccddd)\\&{\stackrel {(5)}{\vdash }}(q_{2},\ddagger D\ddagger D\ddagger D\ddagger C\ddagger C,aaabbbc,ccddd){\stackrel {(6)}{\vdash }}(q_{2},\ddagger D\ddagger D\ddagger D\ddagger C,aaabbbcc,cddd)\\&{\stackrel {(6)}{\vdash }}(q_{2},\ddagger D\ddagger D\ddagger D,aaabbbccc,ddd){\stackrel {(7)}{\vdash }}(q_{3},\ddagger D\ddagger D,aaabbbcccd,dd)\\&{\stackrel {(8)}{\vdash }}(q_{3},\ddagger D,aaabbbcccdd,d){\stackrel {(8)}{\vdash }}(q_{3},\varepsilon ,aaabbbcccddd,\varepsilon )\end{aligned}}$

Automates d'ordre supérieur et hiérarchie de Weir

La notion d'automate à piles intégrés a été étendu par David J. Weir à 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 à pile 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 classes contient strictement la classe précédente :

• la classe de langes d'ordre k contient $\{w^{2^{k-1}}\mid w\in \{a,b\}^{*}\}$, mais pas $\{w^{2^{k-1}+1}\mid w\in \{a,b\}^{*}\}$,
• ou encore $\{a_{1}^{n}\dotso a_{2^{k}}^{n}\mid n\geq 0\}$, mais $\{a_{1}^{n}\dotso a_{2^{k+1}}^{n}\mid n\geq 0\}$.

Notes et références

(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

• (en) Laura Kallmeyer, Parsing Beyond Context-Free Grammars, Heidelberg, Springer Science & Business Media, 2010, 248 p. (ISBN 978-3-642-14846-0, présentation en ligne), chap. 10.1 (« Embedded Push-Down Automata »)
• 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, 1997, p. 69-123.
• David J. Weir, Characterizing mildly context sensitive languages, thèse de doctorat, université de Pennsylvanie, 1988.
• David J. Weir, « A geometric hierarchy beyond context-free languages », Theoretical computer science, vol. 104, n^o 2,‎ 1992, 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, 1987 (présentation en ligne).

Articles liés

• Combinatory categorial grammar (en)