Automate à pile

Un automate à pile (non déterministe) est un 7-uplet $\mathcal{A} = (Q,A,Z, \delta,z_0, q_0,T)\underline{} - Wikipedia Orange$ , où

$Q\underline{} - Wikipedia Orange$ est l'ensemble d'états,
$A\underline{} - Wikipedia Orange$ est l'alphabet d'entrée,
$Z\underline{} - Wikipedia Orange$ est l'alphabet de pile,
$\delta : Q \times(A\cup \{ \varepsilon \}) \times Z \rightarrow \mathcal{P}(Q\times Z^*)$ est la fonction de transition (la notation $\mathcal{P} - Wikipedia Orange$ désigne l'ensemble des parties),
$z_0\in\ Z - Wikipedia Orange$ est le symbole de fond de pile,
$q_0\in Q - Wikipedia Orange$ est l'état initial,
$T \subset Q - Wikipedia Orange$ est l'ensemble des états terminaux.

Au lieu de la fonction $\delta$ , on rencontre fréquemment l'ensemble $\Delta\subset Q \times(A\cup \{ \varepsilon \}) \times Z \times Q\times Z^* - Wikipedia Orange$ défini par

$(q,y,z,p,h)\in\Delta\iff (p,h)\in\delta(q,y,z) - Wikipedia Orange$

Les éléments de $\Delta$ sont les règles de transitions. Lorsque $y=\varepsilon$ , on parle d'une $\varepsilon - Wikipedia Orange$ -règle. Tous les ensembles dans la définition sont finis.

Une configuration interne de l'automate est un couple $(q,h) \in Q \times Z^*$ . Une configuration de l'automate est un triplet $(q,w,h) \in Q \times A^* \times Z^*$ . Un calcul de l'automate sur un mot $w \in A^*$ est une suite de transitions à partir de la configuration initiale $(q_0,w,z_0)$ . Il y a transition de la configuration $(q,yw,zh)$ , où $y\in A\cup{\varepsilon}$ et $z\in Z$ vers la configuration $(q',w,h'h) - Wikipedia Orange$ et on écrit:

$(q,yw,zh) \vdash (q',w,h'h) - Wikipedia Orange$

lorsque $(q',h') \in \delta(q,y,z)$ . Lorsque $y=\varepsilon$ , le mot d'entrée ne change pas. On parle alors d'une $\varepsilon - Wikipedia Orange$ -transition ou d'une transition spontanée. Dans tous les cas, pour qu'une transition soit possible, la pile ne doit pas être vide.

On dit qu'un mot est accepté par l'automate s'il existe une série de transitions qui conduit à une configuration acceptante. Plusieurs modes de reconnaissance existent:

Reconnaissance par pile vide. Les configurations acceptantes sont les configurations de la forme $(q,\varepsilon,\varepsilon)$ où $q \in Q - Wikipedia Orange$ est un état quelconque. Autrement dit, il est possible d'arriver à vider entièrement la pile au moment où on termine la lecture du mot.
Reconnaissance par état final. Les configurations acceptantes sont les configurations de la forme $(t,\varepsilon,h)$ où $t \in T - Wikipedia Orange$ est un état final. La plie n'est donc pas nécessairement vide à la fin de la lecture du mot.
Reconnaissance par pile vide et état final. Les configurations acceptantes sont les configurations de la forme $(t,\varepsilon,\varepsilon)$ où $t \in T - Wikipedia Orange$ est un état final. La pile est vide à la fin de la lecture du mot.

Le langage reconnu par l'automate $\mathcal{A}$ est l'ensemble des mots de $A^* - Wikipedia Orange$ qui sont acceptés.

Les trois modes d'acceptation sont équivalents, au sens que si un langage est reconnu par un automate à pile d'une espèce, on peut construire un automate reconnaissant ce langage, des autres espèces.

Automate à pile déterministe

Un automate à pile est déterministe lorsque la fonction de transition est une fonction partielle vérifiant une condition supplémentaire.

Plus précisément, $\delta$ est une fonction partielle $Q \times(A\cup \{ \epsilon \}) \times Z\rightarrow Q\times Z^*$ . De plus, lorsque $\delta(q,\epsilon,z)$ est définie, alors $\delta(q,a,z)$ n'est défini pour aucune lettre $a \in A - Wikipedia Orange$ . Ainsi, si une transition spontanée est possible, aucune autre transition n'est à partir de cette configuration.

Les modes de reconnaissance, par état final ou par pile vide, ne sont plus équivalents. Un langage algébrique déterministe est un langage algébrique pour lequel il existe un automate à pile déterministe par état final qui le reconnaît. Les automates déterministes avec reconnaissance par pile vide reconnaissent exactement les langages algébriques déterministes qui sont préfixes (aucun mot du langage n'est préfixe d'un autre mot du langage).

Par exemple, le langage $\{a^n b^n \mid n>0\}$ est préfixe, et est reconnu par les deux types d'automates déterministes, mais le langage $a^* - Wikipedia Orange$ ne l'est que par automate déterministe par état final.

Exemples

Reconnaissance du langage $\{a^kb^k | k \ge 1 \} - Wikipedia Orange$

L'automate a les 4 états $q_0, q_1, q_2, q_3$ , état initial $q_0$ , états terminaux $q_0$ et $q_3$ . Le symbole de fond de pile est $\omega$ , de plus il y a deux symboles de pile $A$ et $\underline{A} - Wikipedia Orange$ . Les transitions sont:

(1) $(q_0, a, \omega,q_1, \underline{A}) - Wikipedia Orange$

(2) $(q_1, a, \omega,q_1, A)\, - Wikipedia Orange$

(3) $(q_1, b, A,q_2, \varepsilon)\, - Wikipedia Orange$

(4) $q_1, b, \underline{A},q_3, \varepsilon)\, - Wikipedia Orange$

(5) $(q_2, b, A,q_2, \varepsilon)\, - Wikipedia Orange$

(6) $(q_2, b, \underline{A},q_3, \varepsilon)\, - Wikipedia Orange$

Par exemple, la troisième règle dit que, dans l'état $q_1\underline{}$ , si on lit un $b\underline{}$ et que l'on dépile un $A\underline{}$ , on passe dans l'état $q_2\underline{} - Wikipedia Orange$ sans rien empiler.

On commence par lire le premier caractère : Si le mot est vide on a fini et le mot est accepté car $q_0$ est un état final. Si c'est un $a$ , on empile $\underline{A}$ (1) (il marque le fond de la pile), et on passe à l'état $q_1$ . Si c'est un $b - Wikipedia Orange$ , le mot est rejeté parce qu'aucune règle s'applique.

Dans l'état $q_1$ , à chaque $a$ lu, on empile $A$ (2). Si on lit un $b$ , deux possibilités : - Si on n'a empilé qu'un seul $\underline{A}$ on passe à l'état $q_3$ en dépilant le $\underline{A}$ (4). - Si on a empilé un ou plus $A$ , on passe à l'état $q_2$ en dépilant un $A - Wikipedia Orange$ (3).

Dans l'état $q_2$ , si on lit un $b$ , soit on dépile un $A$ et on reste dans cet état (5), soit on dépile un $\underline{A}$ (fond de la pile) et on passe dans l'état $q_3$ (6). Si on lit un $a - Wikipedia Orange$ , le mot est rejeté.

Dans l'état $q_3$ , le mot lu est accepté car $q_3\in T - Wikipedia Orange$ , aucune nouvelle lecture de caractère n'est possible.

Propriétés

Chaque langage défini par une grammaire algébrique est reconnu par un automate à pile et réciproquement.

En conséquence, le problème de l'appartenance d'un mot à un langage algébrique est décidable : il existe un algorithme qui, étant donnés la description d'une grammaire non contextuelle et un mot, répond en temps fini à la question de l'appartenance de ce mot au langage défini par cette grammaire (plus précisément, on peut le tester en temps $O(n^3) - Wikipedia Orange$ pour un mot de longueur n, grâce à l'algorithme CYK).

La classe des langages rationnels (reconnus par automate fini) est strictement incluse dans la classe des langages algébriques déterministes (reconnus par automate à pile déterministe par état final), elle même strictement incluse dans la classe des langages algébriques (reconnus par automate à pile non déterministe). Par exemple, le langage $a^n b^n - Wikipedia Orange$ est algébrique déterministe mais non rationnel, et le langage des mots palindromes est algébrique mais pas algébrique déterministe.

Restrictions et extensions

Modes d'acceptation

D'autres variantes d'acceptation existent. C'est pourquoi on rencontre parfois une formulation qui sépare la définition en deux: d'une part, une machine à pile est définie sans préciser le mode d'acceptation. D'autre part, une automate est spécifié par la donnée des configurations internes d'acceptation. Par exemple:

l'ensemble $Q\times\{\varepsilon\} - Wikipedia Orange$ décrit l'acceptation par pile vide;
l'ensemble $T\times Z^* - Wikipedia Orange$ décrit l'acceptation par état final;
l'ensemble $T\times\{\varepsilon\} - Wikipedia Orange$ décrit l'acceptation par état final et pile vide.

Automate en temps réel

Un automate à pile est en temps réel (realtime en anglais) s'il ne possède pas de $\varepsilon - Wikipedia Orange$ -règles. Un automate à pile est simple s'il ne possède qu'un seul état. On peut montrer^[1] que tout langage algébrique peut être reconnu par un automate à pile en temps réel et simple.

En revanche, tout langage déterministe ne peut pas être reconnu par un automate à pile déterministe en temps réel. Par exemple, le langage

$\{a^nb^pca^n\mid n,p>0\}\cup \{a^nb^pdb^p\mid n,p>0\} - Wikipedia Orange$

est algébrique déterministe, mais ne peut être reconnu par un automate à pile déterministe en temps réel^[1].

Langage de pile

Le langage de pile d'un automate à pile est l'ensemble des mots qui apparaissent sur la pile lors d'un calcul réussi, c'est-à-dire dans une configuration d'une suite de transitions à partir de la configuration initiale vers une configuration acceptante. Pour tout automate à pile, et quel que soit le mode d'acceptation, le langage de pile est un langage rationnel^[1].

Automates à deux piles

Un automate à deux piles ou plus a la même puissance de calcul qu'une machine de Turing. En effet, les automates à deux piles sont une généralisation des machines à deux compteurs, elles mêmes équivalentes aux machines de Turing. On peut aussi le démontrer de manière plus directe : un automate à deux piles peut simuler une machine de Turing, en faisant en sorte que la partie du ruban située à gauche de la tête de lecture soit enregistrée dans la première pile, et la partie du ruban située à droite de la tête de lecture soit enregistrée sur la seconde.

L'équivalence des automates à pile déterministe

Géraud Sénizergues a prouvé, en 2001, que l'équivalence de deux automates à pile déterministes est décidable. Ce problème était ouvert depuis la définition des automates déterministes dans les années 1970. Géraud Sénizergues a obtenu le Prix Gödel pour cette preuve.

Applications

La plupart des langages de programmation sont décrits par une grammaire non contextuelle. L'analyse syntaxique d'un programme, qui est une des premières opérations effectuée par un compilateur, peut donc être effectuée par un automate à pile.

Il existe des outils automatiques pour construire l'automate à pile à partir d'une description de la grammaire du langage (par exemple Lex et Yacc en C).

Implémentation d'un automate à pile

Le programme source suivant en langage C permet de vérifier que l'expression entrée respecte le langage des parenthèses où toute parenthèse ouvrante doit correspondre avec une parenthèse fermante :

```
#include <stdlib.h>
```
```
#include <stdio.h>
```
```
 
```

#define POP       -1  /* Dépiler l'état               */

#define ACCEPT    -2  /* Accepter l'expression entrée */

#define ERROR     -3  /* Refuser l'expression entrée  */

```
 
```
```
#define ALPHABET 3    /* Grandeur*/
```
```
 
```
```
/*
```
```
    Push-down automation
```
```
 
```
```
    Symbol   | (       | )        | \0
```

    ---------+---------+--------+-----------

    State 0  | PUSH 1  | ERROR  | ACCEPT

    State 1  | PUSH 1  | POP    | ERROR

```
*/
```
```
 
```
```
int states[2][ALPHABET*2] =
```
```
{
```

    /* Valeur d'entrée    Action     */

```
    {
```

            '(',          1 /* PUSH 1 */,

```
            ')',          ERROR,
```
```
            '\0',         ACCEPT
```
```
    },
```
```
    {
```

            '(',          1 /* PUSH 1 */,

```
            ')',          POP,
```
```
            '\0',         ERROR
```
```
    }
```
```
};
```
```
 
```
```
int main( int argc, char** argv )
```
```
{
```
```
    int    stack[100]  = { 0 };
```
```
    int    i           = 0;
```
```
    int    action      = 0;
```
```
    int*   tos         = stack;
```
```
    char   s[80+1];
```
```
    char*  p           = s;
```
```
 
```
```
    /* Chaine de donnée */
```
```
    printf("Entrez l'expression: ");
```
```
    gets( &s );
```
```
 
```

    /* État initial 0 mis dans la pile : */

```
    *(tos++) = 0;
```
```
 
```
```
    /* Sortie */
```
```
    do
```
```
    {
```

        /* Recherche de l'action correspondant au symbole d'entré courant... */

        action = ERROR; /* Action par défaut si le symbole n'est pas trouvé. */

        for( i = 0; i < ALPHABET; i++ )

```
        {
```

            if( states[*(tos-1)][i*2] == *p )

```
            {
```

                /* Caractère entré trouvé */

                action = states[*(tos-1)][i*2+1];

```
                break;
```
```
            }
```
```
        }
```
```
 
```

        /* Effectuer l'action associée au symbole d'entré courant... */

```
        if( action == ERROR )
```
```
        {
```

            printf("Erreur inattendue à la position %d", p-s);

```
            break;
```
```
        }
```
```
        else if( action == ACCEPT )
```

            printf("Sortie acceptée!");

```
        else if( action == POP )
```

            tos--;             /* Dépiler l'état */

```
        else
```

            *(tos++) = action; /* Empiler l'état spécifié */

```
 
```

        /* Données supplémentaires... */

```
        p++;
```
```
    }
```
```
    while( action != ACCEPT );
```
```
 
```
```
    getchar();
```
```
    return 0;
```
```
}
```

Notes

↑ ^{a, b et c} Autebert, Berstel, Boasson (1997)

Références

Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008 (ISBN 978-2-7117-2077-4)

Jean-Michel Autebert, Jean Berstel et Luc Boasson, « Context-free languages and pushdown automata », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag, 1997 (ISBN 978-3540604204)

Géraud Sénizergues: L(A)=L(B)? decidability results from complete formal systems. Theoretical Computer Science 251(1-2): 1-166 (2001)

Géraud Sénizergues, « L(A)=L(B)? A simplified decidability proof », dans Theoretical Computer Science, vol. 281, n^o 1-2, 2002, p. 555-608

Voir aussi

Portail de l'informatique théorique

[ABB-0] {a, b et c} Autebert, Berstel, Boasson (1997)

[1]

encyclopédie par wikipédia

Affichages

Automate à pile

Sommaire

Définition formelle

Automate à pile

Automate à pile déterministe

Exemples

Propriétés

Restrictions et extensions

Modes d'acceptation

Automate en temps réel

Langage de pile

Automates à deux piles

L'équivalence des automates à pile déterministe

Applications

Implémentation d'un automate à pile

Notes

Références

Voir aussi

dernières news sur Orange.fr