Automate à pile

automate abstrait disposant d'une mémoire infinie organisée en pile

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

Fig. 1 : Une hiérarchie d'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 effectue pour chaque lettre du mot une transition, dont le choix dépend de la lettre, de l'état de l'automate et du sommet de la pile ; il peut aussi modifier 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 reconnus 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 leurs analogues itératifs.

Un automate à pile. Une unité de contrôle finie agit en lisant la donnée sur la bande d'entrée (input tape), et en utilisant une mémoire auxiliaire en forme de pile (stack).

Définition formelle

modifier

Automate à pile

modifier

Un automate à pile (non déterministe) est un 7-uplet  , où :

  •   est l'ensemble d'états ;
  •   est l'alphabet d'entrée ;
  •   est l'alphabet de pile ;
  •   est la fonction de transition (la notation   désigne l'ensemble des parties) ;
  •   est le symbole de fond de pile ;
  •   est l'état initial ;
  •   est l'ensemble des états terminaux.

Au lieu de la fonction  , on rencontre fréquemment l'ensemble   défini par

 

Les éléments de   sont les règles de transitions. Lorsque  , on parle d'une  -règle. Tous les ensembles dans la définition sont finis.

Une configuration interne de l'automate est un couple  . Une configuration de l'automate est un triplet  . Un calcul de l'automate sur un mot   est une suite de transitions à partir de la configuration initiale  . Il y a transition de la configuration  , où   et   vers la configuration   et on écrit :

 

lorsque  . Lorsque  , le mot d'entrée ne change pas. On parle alors d'une  -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    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    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    est un état final. La pile est vide à la fin de la lecture du mot.

Le langage reconnu par l'automate   est l'ensemble des mots de   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.

Commentaires

modifier

Un automate à pile est composé de deux parties qui interagissent : la partie automate, avec un nombre fini d'états, et une mémoire auxiliaire infinie, organisée en pile. On s'attendrait donc d'avoir deux opérations sur la pile, une pour empiler un symbole, une pour en dépiler un. La définition mathématique adoptée consiste à remplacer ces deux opérations par une seule qui les combine et qui, dans des cas particuliers, donne les opérations d'empilement et de dépilement. En effet, si on applique une règle de transition

 ,

on dépile d'abord le symbole  , puis on empile le mot  , donc   est remplacé par  . Si le mot   est vide, l'opération consiste donc simplement à dépiler ; si le mot   commence par  , donc si  , l'opération revient à empiler, par-dessus  , une autre mot  . Un troisième avantage de cette notation compactée est que l'on peut tester quelle est la nature du symbole en haut de pile, simplement en le lisant et en le remettant.

Dans le formalisme présenté, on ne peut pas tester si la pile est vide, car si la pile est vide, tout calcul (qui doit commencer par un dépilement) est impossible. Une façon de contourner cette difficulté est d'utiliser un symbole spécial de fond de pile que l'on n'enlève pas.

Automate à pile déterministe

modifier

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,   est une fonction partielle  . De plus, lorsque   est définie, alors   n'est définie pour aucune lettre  . Ainsi, si une transition spontanée est possible, aucune autre transition ne l'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   est préfixe, et est reconnu par les deux types d'automates déterministes, mais le langage   ne l'est que par automate déterministe par état final.

Un exemple

modifier
Automate reconnaissant le langage  .

L'automate a deux états   ; l'état   est initial, il n'y a pas d'état terminal. La reconnaissance est par pile vide. Le symbole de fond de pile est  . Il y a un seul symbole de pile supplémentaire, noté  . Les transitions sont :

(1)  
(2)  
(3)  
(4)  

La troisième règle est une  -règle. Elle dit que, de l'état  , on peut passer à l'état   sans rien lire, et sans changer la pile.

 
représentation d'un automate à pile

On commence par lire le premier caractère :

  • si le mot est vide, on a fini et le mot est rejeté car la pile n’est pas vide ;
  • si c'est un  , on remplace le fond de pile par   ;
  • si c'est un  , le mot est rejeté parce qu'aucune règle ne s'applique.

Ensuite, à chaque   lu, on empile un   additionnel par la règle (2). Après avoir lu   lettres   consécutivement, la pile contient  . Si on voit un  , tout en étant dans l'état  , la machine se bloque parce qu'aucune règle ne s'applique.

Dans l'état  , la règle (3) fait passer dans l'état  , sans lecture de lettre ni de modification de la pile. Ensuite, seule la règle (4) s'applique, et on peut l'appliquer tant que la pile n'est pas vide, c'est-à-dire autant de fois que l’on a lu des lettres  . L'acceptation par pile vide signifie que le mot lu est accepté quand la pile est vide, donc quand le mot a la forme  .

L'exemple serait plus compliqué si on voulait éviter la  -règle.

Propriétés

modifier

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 un temps   pour un mot de longueur n, grâce à l'algorithme CYK).

La classe des langages rationnels (reconnus par des automates finis) 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 des automates à pile non déterministes). Par exemple, le langage   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

Modes d'acceptation

modifier

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   décrit l'acceptation par pile vide ;
  • l'ensemble   décrit l'acceptation par état final ;
  • l'ensemble   décrit l'acceptation par état final et pile vide.

Automate en temps réel

modifier

Un automate à pile est dit en temps réel (realtime en anglais) s'il ne possède pas de  -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 propre (c'est-à-dire ne contenant pas le mot vide) 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

 

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

Langage de pile

modifier

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]. La nature du langage de pile – et plus généralement du langage des mémorisations intermédiaires – a été étudiée systématiquement par Oscar H. Ibarra et IanMcQuillan[2].

Automates à deux piles

modifier

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 que 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éterministes

modifier

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

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ées par un compilateur, peut donc être effectuée par un automate à pile. Si la grammaire du langage est une grammaire algébrique déterministe, il suffit de construire un automate à pile déterministe ; sinon, on doit construire un automate à pile non déterministe.

Il existe des outils pour construire automatiquement un automate à pile à partir d'une description de la grammaire d’un langage (par exemple, ANTLR).

Implémentation d'un automate à pile

modifier

Le programme suivant (en langage C) vérifie que l'expression entrée respecte le langage des parenthèses où toute parenthèse ouvrante doit correspondre à 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 : ");
    fgets( &s , 80 , stdin);     // modification pour éviter les débordements de mémoire

    /* État initial 0 mis dans la pile : */
    *(tos++) = 0;

    /* Sortie */
    do
    {
        /* Recherche de l'action correspondant au symbole d'entrée 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ée 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 et références

modifier
  1. a b et c Autebert, Berstel, Boasson (1997), p. 34 : « The fact that any proper context-free language can be generated by a context-free grammar in Greibach normal form implies that realtime pda's, (and even simple pda's), recognize exactly proper context-free languages. ».
  2. Oscar H. Ibarra et Ian McQuillan, « On store languages of language acceptors », Theoretical Computer Science, vol. 745,‎ , p. 114-132 (DOI 10.1016/j.tcs.2018.05.036).

Références

modifier
Références générales
  • Olivier Carton, Langages formels, calculabilité et complexité, [détail de l’édition] (lire en ligne)
  • 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, (ISBN 978-3540604204), p. 111--174
Sur l'équivalence des automates à pile déterministe

Annexes

modifier

Articles connexes

modifier