Cours 4 : Langages algébriques, suite

Non-Contextualité

Lemme fondamental (Non-contextualité) :

Soient $k, n∈ℕ, 𝛼_1, ⋯, 𝛼_k, 𝛽 ∈ (ℕ∪𝛴)^\ast$ :

Si $𝛼_1 ⋯ 𝛼_k ⟹^n 𝛽$ dans une grammaire algébrique

alors $∃n_1, ⋯, n_k∈ℕ, 𝛽_1, ⋯, 𝛽_k ∈ (N∪𝛴)^\ast$ tq

\[\begin{cases} \sum\limits_{ i=1 }^n n_i = n \\ 𝛽_1 ⋯ 𝛽_k = 𝛽 \\ ∀i∈⟦1,k⟧, 𝛼_i ⟹^{n_i} 𝛽_i \end{cases}\] 
  digraph {
    rankdir=TB;
    ⋯1[label="⋯"];
    ⋯2[label="⋯"];
    ⋯3[label="⋯"];
    ⋯4[label="⋯"];
    ⋯5[label="⋯"];
    subgraph cluster_1 {
      label = "𝛽";
      𝛽_1, 𝛽_k;
    }

    𝛼_1 -> {⋯, ⋯1, ⋯2};
    ⋯ -> 𝛽_1;
    ⋯1 -> 𝛽_1;   
    ⋯2 -> 𝛽_1;
    𝛼_k -> {⋯5, ⋯3, ⋯4};
    ⋯3 -> 𝛽_k;
    ⋯4 -> 𝛽_k;   
    ⋯5 -> 𝛽_k;  
  }

Preuve : Par induction sur $n$.

  • $n=0$ : alors $𝛼_i ⋯ 𝛼_k = 𝛽$ et $n_1 = ⋯ = n_k = 0$ et $𝛽_i = 𝛼_i ∀i$ conviennent.

  • $n>0$ :

    $∃j ∈⟦1,k⟧$ tq

    \[𝛼_j = 𝛼_1 ⋯ 𝛼_j' A 𝛼_j'' ⋯ 𝛼_k ⟹ 𝛼_j = 𝛼_1 ⋯ 𝛼_j' 𝛾 𝛼_j'' ⋯ 𝛼_k ⟹^{n-1} 𝛽\]

    Par une règle $A ⟶ 𝛾 ∈P$.

    Soit

    \[𝛾_i ≝ \begin{cases} 𝛼_i \text{ si } i≠j \\ 𝛼'_j 𝛾 𝛼''_j \text{ sinon} \end{cases}\]

    Par HR,

    \[𝛾_1 ⋯ 𝛾_k ⟹^{n-1} 𝛽\]

    implique qu’il existe $n_1, ⋯, n_k, 𝛽_i, ⋯, 𝛽_k$ tq

    \[\begin{cases} \sum\limits_{ i=1 }^k n_i = n-1 \\ 𝛽_1 ⋯ 𝛽_k = 𝛽 \\ ∀i∈⟦1,n⟧, 𝛾_i ⟹^{n_i} 𝛽_i \end{cases}\]

    Alors

    $𝛼_i= 𝛾_i 𝛼’_j A 𝛼’‘_j$ pour $i≠j$

    et

    \[𝛼_j = 𝛼'_j A 𝛼''_j ⟹ 𝛼'_j 𝛾 𝛼''_j = 𝛾_j ⟹^{n_j} 𝛽_j\]

    donc

    \[n'_i ≝ \begin{cases} n_i \text{ si } i≠j \\ n_{j+1} \text{ sinon} \end{cases}\]

    et

    $𝛽_1, ⋯, 𝛽_k$ conviennent.

Formes normales

Degré d’une grammaire $G ≝ ⟨N, 𝛴, P, S⟩$ :

c’est $m ≝ \max_{A⟶𝛼∈P} \vert 𝛼 \vert$

Forme normale algébrique est sous forme normale quadratique :

si son degré est au plus 2.

Lemme : Soit $G ≝ ⟨N, 𝛴, P, S⟩$ une grammaire.

On peut construire en temps $O(\vert G\vert)$ une grammaire sous forme quadratique $G’ ≝ ⟨N’, 𝛴, P’, S⟩$ tq

\[\begin{cases} N ⊆ N' \\ ∀X∈(N∪𝛴), L_{G'}(X) = L_G(X) \end{cases}\]

Intuition :

\[A ⟶ [BC] [DE] \\ [BC] ⟶ BC \\ [DE] ⟶ DE\]

Preuve :

On définit

\[N' ≝ \lbrace [𝛽] \mid ∃ A ⟶ 𝛼𝛽 ∈ P, \vert 𝛼 \vert>0,\vert 𝛽 \vert>0 \rbrace ∪ N \\ P' ≝ \lbrace A ⟶ X [𝛽] \mid ∃ A ⟶ X𝛽 ∈ P, 𝛽∈ (N∪𝛴)^+ \rbrace (⊛)\\ ∪ \lbrace A ⟶ 𝛼∈P \mid \vert 𝛼 \vert < 2 \rbrace (⊛⊛)\\ ∪ \lbrace [X𝛽] ⟶ X [𝛽] \mid [X𝛽] ∈ N', \vert 𝛽 \vert> 0 \rbrace (⊛⊛⊛)\\ ∪ \lbrace [X] ⟶ X \mid X ∈ (N∪𝛴)\rbrace (⊛⊛⊛⊛)\] \[\vert G' \vert∈ O(\vert G \vert)\]

$L_G(X)⊆ L_{G’}(X)$ :

sens trivial

$L_{G’}(X)⊆L_G(X)$ :

$∀w∈𝛴^\ast, ∀X∈(N∪𝛴)$,

  1. $X⟹^n_{G’} w$ implique $X⟹^\ast_{G} w$

  2. $[𝛽] ⟹^n_{G’} w$ implique $[𝛽] ⟹^\ast_{G} w$

par induction sur $n$

  • $n=0$ : $X, w∈𝛴, X=w$

  • $n=1$ (1) :

    $X∈N, X⟶w$ avec $\vert w \vert<2$, cas $(⊛⊛)$, et alors $X ⟶w∈ P$ aussi.

  • $n=1$ (2) :

    $[𝛽] ⟹{G’} w$ implique $𝛽∈𝛴$ et $𝛽=w$ (cas $(⊛⊛⊛⊛)$) et $[𝛽] ⟹^0{G} w$

  • $n>0$ (1) :

$X= A∈N$

$(⊛)$ :

\[A ⟹_{G'} Y[𝛽] ⟹^{n-1}_{G'} w\]

pour $A ⟶ Y𝛽 ∈P$

Par le lemme fondamental,

  • $Y ⟹^{n-1}_{G’} w_1$
  • $[𝛽] ⟹^{n_1}_{G’} w_2$

avec $n_1 + n_2 = n-1$ et $w_1 w_2 = w$

Par HR (1), puisque $n_1 <n$ :

\[Y ⟹^\ast_G w_1\]

et par HR (2) puisque $n_2<n$ :

\[[𝛽] ⟹^{\ast}_{G} w_2\]

D’où la dérivation dans $G$ =

\[A⟹_G Y 𝛽 ⟹^\ast_G w_1 𝛽 ⟹^\ast_G w_1 w_2 = w\]

$(⊛⊛)$ :

\[A ⟹_{G'} B ⟹^{n-1}_{G'} w\]

avec $A ⟶ B∈P, B∈N$

par HR (1), $B ⟹^\ast_{G} w$ et donc $A ⟹^\ast_{G} w$

$(⊛⊛⊛)$ :

\[[X𝛽] ⟹_{G'} X [𝛽] ⟹^{n-1}_{G'} w\]

par le lemme fondamental,

  • par HR (1) : $X ⟹^\ast_G w_1$
  • HR (2) : $𝛽 ⟹^\ast_G w_2$

avec $w_1 w_2 = w$, et donc

\[X𝛽 ⟹^\ast_{G} w_1w_2 =w\]

$(⊛⊛⊛⊛)$ :

\[[X] ⟹_{G'} X ⟹^{n-1}_{G'} w\]

par HR (1) :

\[X ⟹^\ast_{G} w\]
Grammaire algébrique sans $𝜀$ :

si $∀A⟶𝛼∈P$, $S$ n’apparaît pas dans $𝛼$ et ( $\vert 𝛼 \vert>0$ ou $A=S$ )

NB : Seul l’axiome peut donner $𝜀$, toutes les autres dérivations ne contiennent pas $𝜀$.

Lemme : Soit $G$ une grammaire algébrique de degré $m$. On peut construire en $O(2^m \vert G\vert)$ une grammaire $G’ =⟨N’, 𝛴, P’, S’⟩$ sans $𝜀$ tq :

  • $N ⊆ N’$
  • $∀X∈N∪𝛴, L_{G’}(X) = L_G(X)\backslash \lbrace 𝜀 \rbrace$
  • $L(G) = L(G’)$

Problème du mot vide :

  • entrée : $G = ⟨N, 𝛴, P, S⟩$
  • question : $𝜀∈L(G)$

Ce problème est P-difficile :

Par ex, réduction du langage non vide : il suffit de remplacer tous les terminaux par $𝜀$ (en LOGSPACE) :

\[L(G)≠∅ ⟺ L(G = \lbrace 𝜀 \rbrace\]

En temps linéaire : P-facile.

$𝜀∈L_G(A)$ ssi

  • soit $A ⟶ 𝜀 ∈P$
  • soit $A⟶ B_1 ⋯ B_m ∈P$ et $∀1 ≤i ≤m$, $𝜀∈L_G(B_i)$

Pa réduction à HORNSAT avec les clauses :

$𝒞 ≝ \lbrace A ⟵ B_1 ∧ ⋯ ∧ B_m \mid A ⟶ B_1 ⋯ B_m ∈P, B_i ∈ N\rbrace$

On a alors $𝜀∈L_G(A)$ ssi $𝒞 ∪ \lbrace \bot ⟵ A \rbrace$ instatisfaisable.

On peut calculer l’ens. des

symboles annulables :

$W ≝ \lbrace A∈N \mid 𝜀∈L_G(A) \rbrace$

en temps $O(\vert G\vert)$

Ex:

\[S ⟶ B_1 ⋯ B_n \\ B_i ⟶ b_i B_{i+1} \mid B_{i+1}B_{i+1} ∀i∈⟦1,n⟧ \\ B_n ⟶ 𝜀\] \[W = \lbrace S, B_1, ⋯, B_n \rbrace\]
\[S' ⟶ 𝜀 \\ S' ⟶ S \\ B_i ⟶ b_i \mid b_i B_{i+1} \mid B_{i+1}B_{i+1} \mid B_{i+1} ∀i∈⟦1,n⟧ \\ B_n ⟶ b_n \\ S ⟶ B_{i_1} ⋯ B_{i_k} ∀k, i_1, ⋯, i_k∈⟦1,n⟧\]

Preuve :

I. On calcule $W$ en temps $O(\vert G \vert)$.

II. On pose $N’ ≝ N \sqcup \lbrace S’ \rbrace$

\[P' ≝ \lbrace S'⟶𝜀 \mid S∈w \rbrace ∪ \lbrace S' ⟶ S \rbrace\\ ∪ \lbrace A⟶ 𝛼_0 ⋯ 𝛼_k \mid A ⟶ 𝛼_0 B_1 𝛼_1 ⋯ 𝛼_{k-1} B_k 𝛼_k ∈ P \text{ pour } 𝛼_0, ⋯, 𝛼_k∈ (𝛴∪N)^\ast \text{ tq } \vert 𝛼_1 ⋯ 𝛼_k \vert > 0, B_1 ⋯ B_k ∈ W\rbrace\]

Se calcule en $O(2^ \vert G \vert)$.

Mq $L_G(X) \backslash \lbrace 𝜀 \rbrace ⊆ L_{G’}(X) ∀X∈N∪𝛴$

Par induction sur $n$,

\[∀X∈N∪𝛴, ∀w∈𝛴^+, \text{ si } X ⟹^n_{G} w \text{ alors } X ⟹^\ast_{G'} w\]

  • Cas de base $n=0$ :

    $X=w∈𝛴$

  • $n>0$ :

    $X=A∈N$

    \[A⟹_{G} X_1 ⋯ X_k ⟹^{n-1}_G w\]

    pour $A⟶ X_1 ⋯ X_k ∈ P$

    Par le lemme fondamental, $∃ n_1, ⋯ , n_k ∈ ℕ$ et $w_1, ⋯, w_k ∈𝛴^\ast$ tq

    \[\begin{cases} \sum\limits_{ i=1 }^k n_i = n_1 \\ w_1 ⋯ w_k= w \end{cases}\]

    et

    $X_i ⟹^{n_i}_G w_i ∀1≤ i≤k$

    On indentifie les $i$ tq $w_i = 𝜀$ :

    Soit \(I ≝ \lbrace 1 ≤ i ≤ k \mid w_i=𝜀 \rbrace \\ J ≝ \lbrace 1, ⋯, k \rbrace \backslash J\)

    Par HR, $∀j ∈ J, w_j ∈ 𝛴^+$ et $n_j < n$ donc

    \[X_j ⟹^\ast_{G'} w_j\]

    De plus, $∀i∈ I, X_i ⟹^{n_i}_{G} w_i = 𝜀$ indique $X_i ∈ W$.

    Donc la règle $A⟶X_{j_1} ⋯ X_{j_l}$ pour $J = {j_1 < ⋯ < j_l}$ est une règle de $P’$.

    D’où la dérivation dans $G’$ :

    \[A ⟹_{G'} X_{j_1} ⋯ X_{j_l} ⟹^\ast_{G'} w_{j_1} ⋯ w_{j_l} = w\]

Mq $L_{G’}(X)⊆ L_G(X) \backslash \lbrace 𝜀 \rbrace$ (facile)

Puisque \(L_G(S)\backslash \lbrace 𝜀 \rbrace = L_{G'}(S)\)

alors $L(G)=L_(G’)$

Théorème de Bar-Hillel

TH (Bar-Hillel) : Soit $G = ⟨N,𝛴, P,S⟩$ algébrique de degré $n$ et $𝒜 ≝ ⟨Q, 𝛴, 𝛿, I, F⟩$ un automate fini (non dét. sans $𝜀$).

Alors on peut construire en $O(\vert G \vert \cdot \vert Q \vert^{m+1})$ une grammaire $G’$ tq $L(G’) = L(G)∩L(𝒜)$

Corollaire 1 : les langages algébriques sont fermés par intersection avec les langages rationnels.

Corollaire 2 : Le problème du mot

  • entrée : $G$ algébrique sur $𝛴$ et $w∈𝛴^\ast$
  • question : $w∈L(G)$ ?

est en $O(\vert G \vert \cdot \vert w \vert ^3)$

Donc il est P-complet.

  digraph {
    rankdir=TB;
    q_n1[label="q_{n-1}"];
    ⋯1[label="⋯"];
    ⋯2[label="⋯"];

    subgraph cluster_1 {
      label = "Automate";
      q_0,q_1,q_n1,q_n, ⋯;
    }

    S -> {⋯1, ⋯2};
    ⋯1 -> A;   
    A -> {q_1, ⋯};

  q_0 -> q_1;
  q_1 -> ⋯:
  ⋯ -> q_n1;
  q_n1 -> q_n;
  }

On définit

\[G'≝ ⟨Q × (N∪𝛴) × Q \sqcup \lbrace S' \rbrace, 𝛴, P', S'⟩\]

Un triplet $(q, X, q’)$ va reconnaître exactement

\[L_G(X) ∩ L_{q,q'}(𝒜)\] \[P'≝ \lbrace S'⟶ (q, S, q') \mid q∈I, q'∈F \rbrace \\ ∪ \lbrace (q, a, q') ⟶ a \mid (q,a,q') ∈𝛿 \rbrace \\ ∪ \lbrace (q_0, A, q_m) ⟶ (q_0, X_1, q_1) ⋯ (q_{m-1}, X_m, q_m),m>0, A ⟶ X_1 ⋯ X_m ∈P, X_1, ⋯, X_m ∈ (N∪𝛴), q_0, ⋯, q_m∈Q \rbrace \\ ∪ \lbrace (q, A,q)⟶ 𝜀 \mid q∈Q, A ⟶ 𝜀∈P \rbrace\]

Cardinaux dans l’ordre :

  • $\vert I \vert × \vert F \vert ≤ \vert Q \vert^2$
  • $\vert 𝒜 \vert ≤ \vert Q \vert^2 × \vert 𝛴 \vert$
  • $\vert G \vert ×\vert Q \vert^{m+1}$
  • $\vert Q \vert × \vert G \vert$

Donc

\[G' ∈ O(\vert G \vert \cdot \vert Q \vert^{m+1})\]

Par induction sur $n+ \vert w \vert$ :

pour tous $X∈N∪𝛴$ et $q, q’∈Q$ :

\[(q,X, q') ⟹^{n+\vert w \vert}_{G'} w\]

ssi

\[X⟹^n_G w \text{ et } q⟶^w_𝒜 q'\]

  • $n=0, \vert w \vert=1$ : $X = w =a ∈𝛴$

    \((q, a, q') ⟹^{\vert a \vert}_{G'} a\) ssi

    • $a ⟹^0_G a$ pour (b)

    • et $q ⟶^a_𝒜 q’$

  • $w=𝜀, n=1$ :

    $X = A ∈ N, q=q’$ :

    \[(q, A, q)⟹_{G'} 𝜀\]

    ssi

    • $A⟹_G 𝜀$
    • et $q=q’$

  • Induction :

    (b) : $X= A∈N$

    \[(q_0, A, q_m) ⟹_{G'} (q_0, X_1, q_1) ⋯ (q_{m-1}, X_m , q_m) \\ ⟹^{n-1+\vert w \vert}_{G'} w\]

    alors par le lemme fondamental :

    \[(q_i, X_i, q_{i+1}) ⟹^{n_i}_{G'} w_i\]

    avec

    • $n-1+ \vert w \vert = \sum\limits_{ i } n_i$
    • et $w = w_1 ⋯ w_m$

    NB : si $X⟹^k_{G’} w$ alors $k≥ \vert w \vert$, donc $∀i, n_i = n’_i + \vert w_i \vert$

    Par HR sur $n’_i < n$ et $\vert w_i \vert ≤ \vert w \vert$ :

    • $X_i ⟹^{n’_i}_G w_i$

    • et $q_i ⟶^{w_i}𝒜 q{i+1}$

    Donc

    \[A⟹_G X_1 ⋯ X_m \\ ⟹^{\sum\limits_{ n'_i }}_G w_1 ⋯ w_m = w\]

    et

    \[q_0 ⟶^{w_1}_𝒜 q_1 ⟶^{w_2}_𝒜 q_2 ⟶^{w_3}_𝒜 ⋯ q_{m-1} ⟶^{w_m}_𝒜 q_m\]

    i.e :

    \[q_0 ⟶^{w}_𝒜 q_m\]
Algorithme CYK :

calcul au vol des non-terminaux $(q, X, q’)$ co-accessibles de $G’$

⟶ Multiplication de matrices booléennes $m×n$ en $O(n^𝜔)$, où

\[2 ≤ 𝜔 ≤ 2, 376\]

Th de VALLANT : Problème du mot en $O(n^𝜔)$

Th : Si problème du mot en $O(n^c)$ alors

\[𝜔 ≤ c + 𝜀\]

Leave a comment