Berry-Sethi en C

Ce TP met en œuvre la construction de l'automate de Glushkov par l'algorithme de Berry-Sethi vue en cours. On y reprend les notations du cours : pour une expression régulière \(e\), \(accv(e)\) indique si \(\epsilon \in \mathop{lang}(e)\), \(P(e)\) et \(S(e)\) sont les ensembles des premières et dernières lettres des mots de \(\mathop{lang}(e)\), et \(N(e)\) l'ensemble des facteurs de longueur 2 qui n'apparaissent dans aucun mot de \(\mathop{lang}(e)\).

On considère des expressions régulières représentées sous forme de chaînes de caractères de manière postfixe avec :

le caractère '\0' comme terminateur de la chaîne ;
des constantes pour les opérations (PLUS représente l'union, notée \(|\) dans le cours, et EPSILON l'expression \(\epsilon\)) :
```
char ETOILE = '*';
char PLUS = '+';
char POINT = '.';
char EPSILON = '~';
```
les lettres minuscules entre 'a' et 'z' forment l'alphabet.

Il n'y a pas de symbole pour \(\emptyset\) : comme dans le cours, on suppose que les expressions ne contiennent pas \(\emptyset\).

Exemple

L'expression régulière \((ac)^* | b\) sera définie par :

char s[] = "ac.*b+";

Question 1. Représenter \(b^*(a|a^*b)\).

Corrigé

"b*aa*b.+." : on écrit \(b^*\), puis \(a\), puis \(a^*b\) ("a*b."), on fait l'union des deux derniers ('+') et enfin la concaténation avec \(b^*\) ('.').

On va calculer les ensembles \(P,S\) et \(\Sigma^2 \backslash N\) associés à une expression régulière en représentant une partie de \(\Sigma\) par un tableau de 26 booléens et une partie de \(\Sigma^2\) par un tableau de \(26^2\) booléens (une matrice à plat).

On regroupe ces informations dans une structure :

#define NL 26 // nombre de lettres

struct infos {
    bool vide;         // l'expression reconnaît-elle le mot vide ?
    bool p[NL];        // P(e)
    bool s[NL];        // S(e)
    bool f[NL * NL];   // Σ² \ N(e) : f[26 * a + b] pour le facteur ab
};
typedef struct infos infos;

Question 2. Écrire une fonction infos calcule(char *es) qui calcule \(accv(e)\), \(P(e)\), \(S(e)\) et \(\Sigma^2 \backslash N(e)\) pour l'expression postfixe es, à l'aide des formules inductives du cours.

Indication : comme pour l'évaluation d'une expression postfixe (voir le TP sur les piles), on utilise une pile de infos : une lettre ou EPSILON empile ses informations, une opération dépile ses arguments et empile le résultat. Pour \(\Sigma^2 \backslash N\), les formules du cours donnent, en passant au complémentaire :

\[ \Sigma^2 \backslash N(e_1|e_2) = (\Sigma^2 \backslash N(e_1)) \cup (\Sigma^2 \backslash N(e_2)) \]

\[ \Sigma^2 \backslash N(e_1e_2) = (\Sigma^2 \backslash N(e_1)) \cup (\Sigma^2 \backslash N(e_2)) \cup S(e_1)P(e_2) \qquad \Sigma^2 \backslash N(e^*) = (\Sigma^2 \backslash N(e)) \cup S(e)P(e) \]

Corrigé

// calcule les informations de l'expression postfixe es
infos calcule(char *es)
{
    int n = strlen(es);
    infos *pile = malloc(n * sizeof(infos));
    int sommet = 0; // nombre d'éléments dans la pile
    for (int i = 0; i < n; i++)
    {
        char c = es[i];
        infos r;
        if ('a' <= c && c <= 'z')
        {
            memset(&r, 0, sizeof(infos)); // tout à false
            r.p[c - 'a'] = true;
            r.s[c - 'a'] = true;
        }
        else if (c == EPSILON)
        {
            memset(&r, 0, sizeof(infos));
            r.vide = true;
        }
        else if (c == ETOILE)
        {
            assert(sommet >= 1);
            r = pile[sommet - 1];
            sommet--;
            r.vide = true;
            for (int a = 0; a < NL; a++)
                for (int b = 0; b < NL; b++)
                    if (r.s[a] && r.p[b])
                        r.f[NL * a + b] = true;
        }
        else
        {
            assert(sommet >= 2 && (c == PLUS || c == POINT));
            infos e1 = pile[sommet - 2];
            infos e2 = pile[sommet - 1];
            sommet -= 2;
            for (int k = 0; k < NL * NL; k++)
                r.f[k] = e1.f[k] || e2.f[k];
            if (c == PLUS)
            {
                r.vide = e1.vide || e2.vide;
                for (int a = 0; a < NL; a++)
                {
                    r.p[a] = e1.p[a] || e2.p[a];
                    r.s[a] = e1.s[a] || e2.s[a];
                }
            }
            else
            {
                r.vide = e1.vide && e2.vide;
                for (int a = 0; a < NL; a++)
                {
                    r.p[a] = e1.p[a] || (e1.vide && e2.p[a]);
                    r.s[a] = e2.s[a] || (e2.vide && e1.s[a]);
                }
                for (int a = 0; a < NL; a++)
                    for (int b = 0; b < NL; b++)
                        if (e1.s[a] && e2.p[b])
                            r.f[NL * a + b] = true;
            }
        }
        pile[sommet] = r;
        sommet++;
    }
    assert(sommet == 1); // expression bien formée
    infos res = pile[0];
    free(pile);
    return res;
}

Pour "ac.*b+", on obtient \(accv = \top\), \(P = \{a, b\}\), \(S = \{b, c\}\) et \(\Sigma^2 \backslash N = \{ac, ca\}\).

D'après le théorème de caractérisation du cours, si \(e\) est linéaire (chaque lettre y apparaît au plus une fois), \(\mathop{lang}(e)\) est local et \(\mathop{lang}(e) \backslash \{\epsilon\} = (P\Sigma^* \cap \Sigma^* S) \backslash \Sigma^* N \Sigma^*\).

Question 3. Écrire une fonction bool reconnait_local(infos *inf, char *w) qui teste si le mot w appartient au langage local défini par ces ensembles (et par \(accv\) pour le mot vide). Vérifier sur des exemples qu'elle reconnaît \(\mathop{lang}(e)\) quand \(e\) est linéaire, et trouver une expression non linéaire pour laquelle ce n'est pas le cas.

Corrigé

// teste si w est dans le langage local défini par inf
bool reconnait_local(infos *inf, char *w)
{
    int n = strlen(w);
    if (n == 0)
        return inf->vide;
    if (!inf->p[w[0] - 'a'] || !inf->s[w[n - 1] - 'a'])
        return false;
    for (int i = 0; i + 1 < n; i++)
        if (!inf->f[NL * (w[i] - 'a') + (w[i + 1] - 'a')])
            return false;
    return true;
}

Pour \(e = a(aa)^*\), c'est-à-dire "aaa.*.", on obtient \(P = S = \{a\}\) et \(\Sigma^2 \backslash N = \{aa\}\) : le mot \(aa\) est accepté alors qu'il n'est pas dans \(\mathop{lang}(e)\), qui n'est pas local.

Pour une expression quelconque, on la linéarise en numérotant les occurrences de lettres de \(0\) à \(n-1\) (dans l'ordre de la chaîne) : ce sont les positions. On calcule alors \(P\), \(S\) et \(\Sigma^2 \backslash N\) sur l'alphabet des positions, avec des tableaux de taille \(n\) et \(n^2\) alloués dynamiquement. L'automate de Glushkov a pour états un état initial et les \(n\) positions ; il a une transition de l'état initial vers \(i \in P\) et de \(i\) vers \(j\) pour \(ij \in \Sigma^2 \backslash N\), étiquetées par la lettre de la position d'arrivée ; ses états finals sont les positions de \(S\), et l'état initial si \(accv(e)\).

Question 4. Écrire une fonction glushkov linearise(char *es) qui calcule ces informations, puis une fonction bool reconnait(glushkov *g, char *w) qui teste si w est reconnu par l'automate de Glushkov, en simulant l'automate non déterministe par l'ensemble des états atteints.

Corrigé

Comme les positions de deux sous-expressions sont disjointes, on peut remplir un unique tableau global de facteurs au fur et à mesure.

struct glushkov {
    int n;          // nombre de positions (occurrences de lettres)
    char *lettre;   // lettre[i] : lettre de la position i
    bool vide;
    bool *p;        // p[i] : la position i est dans P
    bool *s;        // s[i] : la position i est dans S
    bool *f;        // f[n * i + j] : le facteur ij est possible
};
typedef struct glushkov glushkov;

// informations sur une sous-expression, pour des positions
// stockées dans des tableaux de taille n alloués dynamiquement
struct infos_pos {
    bool vide;
    bool *p;
    bool *s;
};
typedef struct infos_pos infos_pos;

glushkov linearise(char *es)
{
    int m = strlen(es);
    glushkov g;
    // on numérote les occurrences de lettres : c'est la linéarisation
    g.n = 0;
    for (int i = 0; i < m; i++)
        if ('a' <= es[i] && es[i] <= 'z')
            g.n++;
    int n = g.n;
    g.lettre = malloc(n * sizeof(char));
    g.f = calloc(n * n + 1, sizeof(bool));
    infos_pos *pile = malloc(m * sizeof(infos_pos));
    int sommet = 0;
    int pos = 0; // prochaine position à attribuer
    for (int i = 0; i < m; i++)
    {
        char c = es[i];
        infos_pos r;
        if (c == ETOILE)
        {
            r = pile[--sommet];
            r.vide = true;
            for (int a = 0; a < n; a++)
                for (int b = 0; b < n; b++)
                    if (r.s[a] && r.p[b])
                        g.f[n * a + b] = true;
        }
        else if (c == PLUS || c == POINT)
        {
            infos_pos e2 = pile[--sommet];
            infos_pos e1 = pile[--sommet];
            // les ensembles de positions de e1 et e2 sont disjoints :
            // on peut calculer les facteurs dans un tableau global
            if (c == POINT)
                for (int a = 0; a < n; a++)
                    for (int b = 0; b < n; b++)
                        if (e1.s[a] && e2.p[b])
                            g.f[n * a + b] = true;
            r.p = e1.p;
            r.s = e1.s;
            for (int a = 0; a < n; a++)
            {
                if (c == PLUS)
                {
                    r.p[a] = e1.p[a] || e2.p[a];
                    r.s[a] = e1.s[a] || e2.s[a];
                }
                else
                {
                    r.p[a] = e1.p[a] || (e1.vide && e2.p[a]);
                    r.s[a] = e2.s[a] || (e2.vide && e1.s[a]);
                }
            }
            r.vide = (c == PLUS) ? (e1.vide || e2.vide) : (e1.vide && e2.vide);
            free(e2.p);
            free(e2.s);
        }
        else
        {
            r.p = calloc(n + 1, sizeof(bool));
            r.s = calloc(n + 1, sizeof(bool));
            r.vide = (c == EPSILON);
            if (c != EPSILON)
            {
                g.lettre[pos] = c;
                r.p[pos] = true;
                r.s[pos] = true;
                pos++;
            }
        }
        pile[sommet++] = r;
    }
    assert(sommet == 1);
    g.vide = pile[0].vide;
    g.p = pile[0].p;
    g.s = pile[0].s;
    free(pile);
    return g;
}

void libere_glushkov(glushkov *g)
{
    free(g->lettre);
    free(g->p);
    free(g->s);
    free(g->f);
}

// Automate de Glushkov : un état initial et un état par position.
// On simule l'automate non déterministe en maintenant l'ensemble
// des positions atteintes (l'état initial n'est actif qu'au départ).
bool reconnait(glushkov *g, char *w)
{
    int n = g->n;
    int m = strlen(w);
    if (m == 0)
        return g->vide;
    bool *cour = malloc((n + 1) * sizeof(bool));
    bool *suiv = malloc((n + 1) * sizeof(bool));
    for (int i = 0; i < n; i++)
        cour[i] = g->p[i] && g->lettre[i] == w[0];
    for (int k = 1; k < m; k++)
    {
        for (int j = 0; j < n; j++)
        {
            suiv[j] = false;
            if (g->lettre[j] == w[k])
                for (int i = 0; i < n && !suiv[j]; i++)
                    suiv[j] = cour[i] && g->f[n * i + j];
        }
        bool *t = cour; cour = suiv; suiv = t;
    }
    bool res = false;
    for (int i = 0; i < n; i++)
        res = res || (cour[i] && g->s[i]);
    free(cour);
    free(suiv);
    return res;
}

On a testé ces fonctions en comparant, pour des milliers d'expressions aléatoires sur \(\{a,b,c\}\) et tous les mots de longueur au plus 5, le résultat de reconnait avec un filtrage naïf sur l'arbre de l'expression.