TP 4 : Algorithme CYK (Cocke-Younger-Kasami)

Solution

type grammaire = {
    n_variables : int;
    regles1 : (int * char) list;
    regles2 : (int * int * int) list;
    epsilon : bool
}

(* 6 *)
let g0 = { 
    n_variables = 5;
    regles1 = [(0, 'b'); (1, 'a'); (2, 'b'); (4, 'a')];
    regles2 = [(0, 1, 2); (0, 2, 1); (0, 3, 1); (1, 1, 4); (3, 1, 2)];
    epsilon = false
}

let init g u =
    let n = String.length u in
    let k = g.n_variables in
    let t = Array.make (n+1) [||] in
    for i = 0 to n do
        t.(i) <- Array.make_matrix n k false
    done;
    if g.epsilon then t.(0).(0).(0) <- true;

    let rec aux = function
        | [] -> ()
        | (i, a)::q ->
            for d = 0 to n - 1 do
                if u.[d] = a then t.(1).(d).(i) <- true
            done;
            aux q
    in
    aux g.regles1;
    t

(* 7 *)
let cyk g u =
    let t = init g u in
    let n = String.length u in

    for l = 2 to n do
        for d = 0 to n - l do
            let rec aux = function
                | [] -> ()
                | (i, j, k)::q ->
                    for p = 1 to l - 1 do
                        if d + p < n && t.(p).(d).(j) && t.(l-p).(d+p).(k) 
                        then t.(l).(d).(i) <- true
                    done;
                    aux q
            in
            aux g.regles2
        done
    done;
    t.(n).(0).(0);;

(* 8 *)
cyk g0 "aab";;
cyk g0 "aabb";;
cyk g0 "abaa";;
cyk g0 "aababa";;

(* 9 *)
type arbre = Vide | Un of int * char | Deux of int * arbre * arbre

let arbre_derivation g u : arbre option =
    let n = String.length u in
    let k = g.n_variables in
    let t = Array.make (n+1) [||] in
    for i = 0 to n do
        t.(i) <- Array.make_matrix n k None
    done;
    if g.epsilon then t.(0).(0).(0) <- Some Vide;
    let rec aux = function
        | [] -> ()
        | (i, a)::q ->
            for d = 0 to n - 1 do
                if u.[d] = a then t.(1).(d).(i) <- Some (Un (i, a))
            done;
            aux q
    in
    aux g.regles1;

    for l = 2 to n do
        for d = 0 to n - l do
            let rec aux = function
                | [] -> ()
                | (i, j, k)::q ->
                    for p = 1 to l - 1 do
                        if d + p < n
                        then match t.(p).(d).(j), t.(l-p).(d+p).(k) with
                        | Some a1, Some a2 -> t.(l).(d).(i) <- Some (Deux (i, a1, a2))
                        | _ -> ()
                    done;
                    aux q
            in
            aux g.regles2
        done
    done;
    t.(n).(0).(0);;

(* 10 *)

arbre_derivation g0 "aab";;

L'algorithme CYK permet de déterminer, par programmation dynamique, si un mot est généré par une grammaire non contextuelle.
Il permet aussi de trouver un arbre de dérivation pour ce mot, par analyse syntaxique ascendante (bottom-up : des feuilles à la racine).

L'algorithme prend en entrée une grammaire $G = (\Sigma, V, R, S)$ en forme normale de Chomsky, c'est-à-dire que toutes les règles sont de la forme $X \to YZ$ ou $X \to a$ ou $S \to \epsilon$, où $X, Y, Z \in V$, $Y \neq S, Z\neq S$ et $a \in \Sigma$.
On note $V =\{X_0, X_1, \ldots, X_{k-1}\}$ les variables, où $S = X_0$.

Équation de récurrence

Cette partie est à faire sur papier.

Soit $u = u_0 \ldots u_{n-1} \in \Sigma^*$. On veut savoir si $u \in L(G)$. Pour cela, on va calculer, pour $l \in \{0, \ldots, n\}$, $d \in \{0, \ldots, n - 1\}$ et $i \in \{0, \ldots, k-1\}$ :

$$\begin{align*} t[l][d][i] &= \text{ vrai si } X_i \Rightarrow^* u_{d} \ldots u_{d + l - 1}\\ t[l][d][i] &= \text{ faux sinon } \end{align*}$$

1. À quelle condition a t-on $u \in L(G)$ ?
2. Que vaut $t[0][d][i]$ ?
3. Que vaut $t[1][d][i]$ ?

Pour avoir $X_i \Rightarrow^* u_{d} \ldots u_{d + l - 1}$, il faut que $X_i \to X_j X_k$ avec $X_j \Rightarrow^* u_{d} \ldots u_{d + p - 1}$ et $X_k \Rightarrow^* u_{d + p} \ldots u_{d + l - 1}$.

4. En déduire une équation de récurrence pour $t[l][d][i]$.

Solution (pour vérifier votre réponse)

$$t[l][d][i] = {\bigvee_{\substack{X_i \rightarrow X_j X_k}} \bigvee_{p = 1}^{l-1} t[p][d][j] \land t[l-p]\underbrace{[d+m]}_{\text{si }d + p < n}[k]}$$

5. En déduire un algorithme en pseudo-code pour remplir le tableau $t$. Quelle est sa complexité ?

Implémentation

On définit le type suivant :

type grammaire = {
    n_variables : int;
    regles1 : (int * char) list;
    regles2 : (int * int * int) list;
    epsilon : bool
}

Les variables sont numérotées de 0 à n_variables - 1 (int) et les lettres sont des caractères (char).
regles1 contient un couple $(i, a)$ pour chaque règle $X_i \to a$ et regles2 contient un triplet $(i, j, k)$ pour chaque règle $X_i \to X_j X_k$.
epsilon est vrai si $\epsilon \in L(G)$.

6. Définir une variable g0 représentant la grammaire suivante :

$$\begin{align*} S &\to b \mid X_1 X_2 \mid X_2 X_1 \mid X_3 X_1 \\ X_1 &\to a \mid X_1 X_4 \\ X_2 &\to b \\ X_3 &\to X_1 X_2 \\ X_4 &\to a \end{align*}$$

7. Écrire une fonction init : grammaire -> string -> bool array array array qui prend en argument une grammaire et un mot et renvoie un tableau t initialisé pour les cas de base $l = 0$ et $l = 1$.

init g0 "aba";;
- : bool array array array =
[|[|[|false; false; false; false; false|];
    [|false; false; false; false; false|];
    [|false; false; false; false; false|]|];
  [|[|false; true; false; false; true|]; 
    [|true; false; true; false; false|];
    [|false; true; false; false; true|]|];
  [|[|false; false; false; false; false|];
    [|false; false; false; false; false|];
    [|false; false; false; false; false|]|];
  [|[|false; false; false; false; false|];
    [|false; false; false; false; false|];
    [|false; false; false; false; false|]|]|]

8. Écrire une fonction cyk : grammaire -> string -> bool qui prend en argument une grammaire et un mot et renvoie vrai si le mot est dans le langage de la grammaire, en utilisant l'algorithme CYK décrit en première partie.

9. Justifier que g0 engendre le langage $a^* b a^*$ et tester la fonction cyk sur quelques exemples.

cyk g0 "aab";;
- : bool = true
cyk g0 "aabb";;
- : bool = false
cyk g0 "abaa";;
- : bool = true
cyk g0 "aababa";;
- : bool = false

Arbre de dérivation

On définit le type suivant pour modéliser un arbre de dérivation :

type arbre = Vide | Un of int * char | Deux of int * arbre * arbre

où :

• Vide correspond à une dérivation $S \to \epsilon$,
• Un (i, a) correspond à une dérivation $X_i \to a$,
• Deux (i, j, k) correspond à une dérivation $X_i \to X_j X_k$.

On rappelle que le type option est défini nativement en OCaml par :

type 'a option = None | Some of 'a

On adapte alors l'algorithme CYK avec t : arbre option array array array où t[l][d][i] contient un arbre de dérivation pour $X_i \Rightarrow^* u_{d} \ldots u_{d + l - 1}$ s'il en existe un, None sinon.

10. Écrire une fonction arbre_derivation : grammaire -> string -> arbre option qui prend en argument une grammaire et un mot et renvoie un arbre de dérivation pour ce mot si celui-ci est dans le langage de la grammaire ou None sinon.