Automate à pile

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, chacune consistant à lire une lettre du mot ou à réaliser des opérations sur la pile. Les transitions effectuées dépendent des lettres du mot, de l'état de l'automate et du sommet de la pile. Selon l'état de l'automate et de la pile à la fin du calcul, le mot peut être 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 compilation, et plus généralement dans la transformation de définitions ou d'algorithmes récursifs en leur analogues itératifs.

Sommaire

1 Définition formelle
- 1.1 Automate à pile
- 1.2 Automate à pile déterministe
2 Exemples
3 Propriétés
4 Restrictions et extensions
5 L'équivalence des automates à pile déterministe
6 Applications
7 Implémentation d'un automate à pile
8 Notes
9 Références
10 Voir aussi

Définition formelle

Automate à pile

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 $δ$ , 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 $Δ$ sont les règles de transitions. Lorsque $y = ε$ , on parle d'une $ε$ -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, y w, z h)$ , 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 = ε$ , 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 $(q,ε,ε)$ où $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,ε, h)$ où $t \in T$ 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,ε,ε)$ où $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

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 $Q \times(A\cup \{ \epsilon \}) \times Z\rightarrow Q\times Z^*$ . De plus, lorsque $\delta(q,\epsilon,z)$ est définie, alors $δ(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 une 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 di 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

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

L'automate a les 3 é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 $ω$ , 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.

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

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

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

Un automate à pile est 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 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

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

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Automate à pile de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Automate a pile — Automate à pile 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 semblable à un automate fini non déterministe mais il dispose également d une… … Wikipédia en Français
Automate À Pile — 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 semblable à un automate fini non déterministe mais il dispose également d une pile qui peut… … Wikipédia en Français
Automate Fini — Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate déterministe à états fini — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate fini déterministe — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate fini non déterministe — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate fini non déterministe généralisé — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate fini — Pour les articles homonymes, voir Automate. Fig. 1 : Automate fini reconnaissant les écritures binaires des multiples de 3. Un automate fini (on dit parfois, par une traduction littér … Wikipédia en Français
Automate sur les mots infinis — En informatique théorique, et spécialement en théorie des automates un automate sur les mots infinis ou ω automate est un automate fini, déterministe ou non, qui accepte des mots infins. Comme un tel automate ne s arrête pas, les conditions d… … Wikipédia en Français
Automate cellulaire — À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe) de l application répétée de cette règle… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

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

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

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

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link