Automate à piles emboîtées

En théorie des automates, un automate à piles emboîtées est un automate fini qui utilise comme mémoire auxiliaire une pile dont les éléments peuvent eux-mêmes être des piles^[1]. Mais contrairement à un automate à pile usuel, un automate à piles emboîtées peut se déplacer en avant et en arrière sur la « pile », qui est donc plutôt structurée en liste ; de plus, l'automate peut insérer une nouvelle pile, opérer sur elle, la détruire, et continuer à travailler sur l'ancienne pile. Ce mode opératoire peut être emboîté récursivement à une profondeur arbitraire ; toutefois, l'automate manipule toujours la pile la plus interne.

Un automate à piles emboîtées opère comme un automate à pile, mais il peut de plus, empiler et dépiler des piles.

Un automate à piles emboîtées est capable de reconnaître un langage indexé, et de fait les langages indexés sont exactement les langages reconnus par les automates à piles emboîtées non déterministes^[2],[1],[3].

Les automates à piles emboîtées diffèrent des automates à piles embarquées qui sont moins puissants puisque pour ces derniers, la mémoire auxiliaire, toujours organisée récursivement, n'est accessible que par le haut de pile. Les automates à pile embarquée reconnaissent exactement les langages engendrés par les grammaires d'arbres adjoints^[4].

Description informelle

Un automate à piles emboîtées lit ses données sur une bande d'entrée ; le mot d'entrée n'est pas modifiable, il est délimité par deux marqueurs, et dans le cas bidirectionnel, la tête de lecture peut se déplacer sur la bande d'entrée en avant et en arrière ; pour des automates emboîtés unidirectionnels, la tête de lecture du mot d'entrée ne peut pas revenir en arrière.

L'automate est composé d'ensembles

• ${\displaystyle Q,\Sigma }$, et ${\displaystyle \Gamma }$ qui sont des ensembles finis respectivement d'états, de symboles d'entrée et de symboles de pile ;
• de marqueurs, notés ${\displaystyle \$}$, ${\displaystyle {\text{¢}}}$, et ${\displaystyle \#}$ ; ce sont des symboles additionnels, utilisés comme marqueurs de début ou de fin de mots de pile;
• d'un ensemble de règles de transition qui permettent des déplacements de la tête de lecture sur la bande d'entrée, et de la tête de lecture et écriture sur la pile.

La mémoire auxiliaire, appelée pile (« stack ») est en fait une structure linéaire où la tête de pile peut se déplacer dans les deux sens. La pile est un codage d'une structure arborescente : ses éléments sont soit des symboles de l'alphabet de pile ${\displaystyle \Gamma }$, soit des piles elles-mêmes, représentées linéairement à l'aide de marqueurs de début et fin de pile. Les sous-piles peuvent elles-mêmes contenir des piles. Une pile peut se présenter typiquement sous la forme linéaire suivante :

${\displaystyle \$\,a\,b\,\$\,k\,{\text{¢}}\,{\underline {\$\,p}}{\text{¢}}\,{\text{¢}}\,c\,{\text{¢}}\#}$

Si, pour plus de lisibilité, on remplace les marqueurs ${\displaystyle \$}$, ${\displaystyle {\text{¢}}}$ par des parenthèses ouvrante et fermante et qu'on omet marqueur ${\displaystyle \#}$, on obtient l'écriture :

${\displaystyle \,(\,a\,b\,(\,k\,)\,{\underline {(\,p}}\,)\,c\,)}$

La pile contient les éléments ${\displaystyle a,b}$ de l’alphabet de pile, puis une sous-pile réduite à l'élément ${\displaystyle k}$ suivie d'une deuxième sous-pile composée de ${\displaystyle p}$ et enfin la lettre ${\displaystyle c}$. La tête de lecture-écriture est positionnée en début de la sous-pile ${\displaystyle (p)}$, ce qui est représenté par un soulignement.

Exemple

Voici une séquence d'opérations et leur effet sur la pile. À l'étape 2, une pile est créée à l'intérieur de la sous-pile ${\displaystyle (p)}$ ; cette sous-sous-pile est ${\displaystyle (rs)}$. Elle est ensuite progressivement vidée, puis détruite à l’étape 5. À l'étape 8, la tête d'écriture sur la pile se retrouve au niveau du début et une insertion simple ajoute les symboles ${\displaystyle n,o}$.

n°	action	pile
1:		${\displaystyle \,(\,a\,b\,(\,k\,)\,{\underline {(\,p}}\,)\,c\,)}$
2:	création de sous-pile	${\displaystyle \,(\,a\,b\,(\,k\,)\,(\,p\,{\underline {(\,r}}\,s\,)\,)\,c)}$
3:	pop	${\displaystyle (\,a\,b\,(\,k\,)\,(\,p\,{\underline {(\,s}}\,)\,)\,c\,)}$
4:	pop	${\displaystyle (\,a\,b\,(\,k\,)\,(\,p\,{\underline {(}}\,)\,)\,c)}$
5:	destruction de sous-pile	${\displaystyle (\,a\,b\,(\,k\,)\,(\,p\,{\underline {)}}\,c\,)}$
6:	descente	${\displaystyle (\,a\,b\,(\,k\,)\,(\,p\,)\,{\underline {c}}\,)}$
7:	montée	${\displaystyle (\,a\,b\,(\,k\,)\,(\,p\,{\underline {)}}\,c\,)}$
8:	montée	${\displaystyle \,(\,a\,b\,(\,k\,)\,{\underline {(\,p}}\,)\,c\,)}$
9:	push	${\displaystyle \,(\,a\,b\,(\,k\,)\,{\underline {(\,n}}\,o\,p\,)\,c\,)}$

La description formelle des règles de transition est complexe, puisqu'elle doit tenir compte des symboles de pile et de la structure arborescente de la pile.

Propriétés

On peut définir des automates bidirectionnels à piles emboîtées, et on peut montrer que cela n'augmente pas la puissance de calcul par rapport aux automates à pile bidirectionnels ordinaires^[5].

Robert Gilman et Michael Shapiro ont utilisé des automates à piles emboîtées pour résoudre le problème du motdans certains groupes certain groups^[6].

Notes et références

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

1. Alfred Aho, « Nested stack automata », Journal of the ACM, vol. 16, n^o 3,‎ 1969, p. 383–406 (DOI 10.1145/321526.321529, lire en ligne)
2. Barbara Parteea, Alice ter Meulen et Robert E. Wall, Mathematical Methods in Linguistics, Kluwer Academic Publishers, 1990, 666 p. (ISBN 978-90-277-2245-4, présentation en ligne).
3. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979, 418 p. (ISBN 978-0-201-02988-8). Dans ce livre, à la page 390.
4. Laura Kallmeyer, Parsing Beyond Context-Free Grammars, Springer, 2010, xii+247 (ISBN 978-3-642-14845-3, DOI 10.1007/978-3-642-14846-0).
5. C. Beeri, « Two-Way Nested Stack Automata Are Equivalent to Two-Way Stack Automata », J. Comp. and System Sciences, vol. 10,‎ 1975, p. 317–339 (DOI 10.1016/s0022-0000(75)80004-3, lire en ligne)
6. Robert Gilman, Michael Shapiro, « On Groups Whose Word Problem is Solved by a Nested Stack Automaton », - pages=16,‎ 1998 (arXiv 9812028v1.pdf, lire en ligne)

• Portail de la linguistique
• Portail de l'informatique théorique