Automate à piles emboîtées

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.

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.

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].