Automate à piles intégrées

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

L'exemple qui suit est dans la thèse de Vijay-Shanker[1] - [2]. C'est un EPDA qui accepte le langage ${\displaystyle 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.

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

• ${\displaystyle Q}$ est un ensemble fini d'états, ${\displaystyle q_{0}\in Q}$ est l'état initial et ${\displaystyle Q_{F}\subseteq Q}$ est l'ensemble des états terminaux.
• ${\displaystyle \Gamma }$ est l'alphabet de pile, et ${\displaystyle Z_{0}\in \Gamma }$ est le symbole de fond de pile.
• ${\displaystyle \Sigma }$ est l'alphabet d'entrée.
• ${\displaystyle \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ù ${\displaystyle {\mathfrak {P}}_{f}}$ dénote les parties finies et ${\displaystyle \Upsilon =\Gamma ^{*}}$ sert à décrire les mots de pile.

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

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

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

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

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

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

Voici la description formelle de l’automate pour l'exemple esquissé plus haut Il comporte 4 états ${\displaystyle 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 ${\displaystyle \Sigma =\{a,b,c,d\}}$, l'alphabet de pile est ${\displaystyle \Gamma =\{Z_{0},B,C,D\}}$, où ${\displaystyle Z_{0}}$ est le symbole de fond de pile. La fonction de transition \delta est la suivante :

${\displaystyle {\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 ${\displaystyle aaabbbcccddd}$, on obtient le calcul suivant :

${\displaystyle {\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}}}$