Automate à pile

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un automate à pile est une machine abstraite utilisée en informatique théorique et, plus précisément, en théorie des automates.

Un automate à pile est une généralisation des automates finis : il dispose en plus d'une mémoire infinie organisée en pile (last-in/first-out ou LIFO). Un automate à pile prend en entrée un mot et réalise une série de transitions. Il fait une transition pour chaque lettre du mot, dépendant de la lettre, de l'état de l'automate et du sommet de la pile, et peut aussi changer le contenu de la pile. Selon l'état de l'automate et de la pile à la fin du calcul, le mot est accepté ou refusé.

Les langages acceptés par les automates à piles sont exactement les langages algébriques, c'est-à-dire ceux engendrés par une grammaire algébrique.

L'importance des automates à pile vient de leur emploi en analyse syntaxique des langages de programmation, et plus généralement dans la transformation de définitions ou d'algorithmes récursifs en leur analogues itératifs.

Définition formelle[modifier | modifier le code]

Automate à pile[modifier | modifier le code]

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

  • Q\underline{} est l'ensemble d'états,
  • A\underline{} est l'alphabet d'entrée,
  • Z\underline{} 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} désigne l'ensemble des parties),
  • z_0\in\ Z est le symbole de fond de pile,
  • q_0\in Q est l'état initial,
  • T \subset Q 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^* défini par

(q,y,z,p,h)\in\Delta\iff (p,h)\in\delta(q,y,z)

Les éléments de \Delta sont les règles de transitions. Lorsque y=\varepsilon, on parle d'une \varepsilon-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) et on écrit :

(q,yw,zh) \vdash (q',w,h'h)

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-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)q \in Q 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)t \in T est un état final. La pile 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)t \in T 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^* 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[modifier | modifier le code]

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. 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^* ne l'est que par automate déterministe par état final.

Exemples[modifier | modifier le code]

Reconnaissance du langage \{a^kb^k | k \ge 1 \}

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}. Les transitions sont :

(1) (q_0, a, \omega,q_1, \underline{A})

(2) (q_1, a, \omega,q_1, A)\,

(3) (q_1, b, A,q_2, \varepsilon)\,

(4) (q_1, b, \underline{A},q_3, \varepsilon)\,

(5) (q_2, b, A,q_2, \varepsilon)\,

(6) (q_2, b, \underline{A},q_3, \varepsilon)\,

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{} sans rien empiler.

Automateapile.png

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, 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 (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, le mot est rejeté.

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

Propriétés[modifier | modifier le code]

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) 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 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[modifier | modifier le code]

Modes d'acceptation[modifier | modifier le code]

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\} décrit l'acceptation par pile vide ;
  • l'ensemble T\times Z^* décrit l'acceptation par état final ;
  • l'ensemble T\times\{\varepsilon\} décrit l'acceptation par état final et pile vide.

Automate en temps réel[modifier | modifier le code]

Un automate à pile est en temps réel (realtime en anglais) s'il ne possède pas de \varepsilon-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\}

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

Langage de pile[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

La plupart des langages de programmation sont décrits par une grammaire algébrique. 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. Si la grammaire du langage est une grammaire algébrique deterministe il suffit de construire un automate à pile déterministe. Sinon, on doit construire un automate à pile non-déterministe.

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

Implémentation d'un automate à pile[modifier | modifier le code]

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[modifier | modifier le code]

Références[modifier | modifier le code]

  • 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), p. 1-166 (2001)
  • Géraud Sénizergues, « L(A)=L(B)? A simplified decidability proof », Theoretical Computer Science, vol. 281, no 1-2,‎ 2002, p. 555-608

Articles connexes[modifier | modifier le code]