Automate à pile

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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 être utilisée pour stocker des informations pertinentes. La puissance de calcul des automates à piles correspond aux langages non-contextuels soit ceux qui peuvent être décrits par une grammaire hors-contexte.

[modifier] Utilisation

Les automates à pile utilisent une zone de mémoire organisée en pile, qui permet de sauver des informations.

Le choix d'une transition peut dépendre de la valeur au sommet de la pile (pop)
Une transition peut entraîner un ou plusieurs empilements (push).

[modifier] Définitions formelles

Un automate à pile est un 7-uplet $(E,\Sigma,\Phi, F,\omega, i,T)\underline{}$ , où

$E\underline{}$ est l'ensemble d'états,
$\Sigma\underline{}$ est l'alphabet d'entrée,
$\Phi\underline{}$ est l'alphabet de pile,
$F : E\times(\Sigma\cup \{ \epsilon \}) \times ( \Phi \cup \{ \epsilon \} ) \rightarrow P(E\times\Phi^*)$ est la relation de transition,
$\omega\underline{}$ est le symbole de pile vide,
$i\in E$ est l'état initial,
$T \subset E$ est l'ensemble des états terminaux.

[modifier] Exemples

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

On peut utiliser l'automate $M = (\{q_0, q_1, q_2, q_3\}, \{a, b\}, \{A,\underline{A}\}, \delta, \omega, q_0, \{q_0, q_3\} ),$

où les transitions sont définies par :

$\delta(q_0, a, \epsilon) = \{(q_1, \underline{A})\}$

$\delta(q_1, a, \epsilon) = \{(q_1, A)\}\underline{}$

$\delta(q_1, b, A) = \{(q_2, \epsilon)\}\underline{}$

$\delta(q_1, b, \underline{A}) = \{(q_3, \epsilon)\}$

$\delta(q_2, b, A) = \{(q_2, \epsilon)\}\underline{}$

$\delta(q_2, b, \underline{A}) = \{(q_3, \epsilon)\}$

$\delta(q, \theta, \rho) = \empty$ pour les autres valeurs de $(q, \theta, \rho)\underline{}$

Par exemple, 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.

[modifier] Propriétés

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

En conséquence, le problème de l'appartenance d'un mot à un langage non contextuelle 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.

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

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

#define POP     -1
#define ACCEPT  -2
#define ERROR   -3

#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] =
{
        {
                '(',    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 );

        /*Pile poussée*/
        *(tos++) = 0;

        /* Sortie */
        do
        {
                /* Boucle*/
                action = ERROR;
                for( i = 0; i < ALPHABET; i++ )
                {                       
                        if( states[*(tos-1)][i*2] == *p )
                        {
                                action = states[*(tos-1)][i*2+1];
                                break;
                        }
                }

                /* Actions*/
                if( action == ERROR )
                {
                        printf("Erreur innatendue à la position %d", p-s);
                        break;
                }
                else if( action == ACCEPT )
                        printf("Sortie acceptée!");
                else if( action == POP )
                        tos--;
                else
                        *(tos++) = action;

                /* Données supplémentaires... */
                p++;
        }
        while( action != ACCEPT );

        getchar();
        return 0;
}