TD 4 : Langages algébriques

Énoncé

EX 1

1.

\[S ⟶ a S a \mid b S b \mid 𝜀\]

2.

\[S ⟶ Ub \mid aT \\ T ⟶ aTb \mid aT \mid 𝜀\\ U ⟶ aUb \mid Ub \mid 𝜀\]
\[S ⟶ aA \mid Bb \\ A ⟶ aA \mid C\\ B ⟶ Bb \mid C\\ C ⟶ aCb \mid 𝜀\]

3.

\[S ⟶ ABC \mid 𝜀\\ A ⟶ aAb \mid 𝜀\\ B ⟶ bB \mid 𝜀\\ C ⟶ bCc \mid 𝜀\]

4.

\[S ⟶ aSb \mid aSbb \mid 𝜀\]

EX 2

1.

$D_1^\ast ⊆ L$ :

Vu en prépa : on montre par induction structurelle (i.e : par induction structurelle sur la longueur minimale d’une dérivation $S ⟶^\ast_{G_1} 𝜀$) que : tout préfixe de $w ∈ D_1^\ast$ a plus de parenthèses ouvrantes que de parenthèses fermantes.

  • Si $w =𝜀$ : immédiat
  • Sinon, si $S⟶ a_1 S \overline{a_1} S ⟶^\ast w$, alors il existe $w_1, w_2$ tq $S⟶^\ast w_1, S⟶^\ast w_2$ et $w = a_1 w_1 \overline{a_1} w_2$ : on conclut car par hypothèse d’induction : $w_1, w_2∈D_1^\ast$

$L ⊆ D_1^\ast$ :

Si $w∈L$, par induction sur la taille de $w$ :

  • Si $w=𝜀$ : OK
  • Si $\vert w \vert > 0$ :

Comme, par hypothèse,

\[\vert w[1] \vert_{a_1} ≥ \vert w[1] \vert_{\overline{a_1}}\]

alors $w[1]=a_1$, et

\[w ≝ a_1 w_1 \overline{a_1} w_2\]

où $a_1 w_1 \overline{a_1}$ est le plus petit préfixe ayant autant de parenthèses ouvrantes que fermantes.

On vérifie aisément que

  • $a_1 w_1 \overline{a_1} ∈ L$

  • et donc, par suite, que : $w_2∈L$ (il a autant de parenthèses ouvrantes que fermantes car c’est le cas de $w$ et de $a_1 w_1 \overline{a_1}$, et on vérifie que tous ses préfixes ont plus de parenthèses ouvrantes que fermantes car $a_1 w_1 \overline{a_1}$ a autant de parenthèses ouvrantes que fermantes)

2.

$D_n^\ast ⊆ L$ :

Preuve par induction structurelle :

  • Si $w=𝜀$ : OK
  • Sinon, si $S⟶ a_1 S \overline{a_1} S ⟶^\ast w$, alors il existe $w_1, w_2$ tq $S⟶^\ast w_1, S⟶^\ast w_2$ et $w = a_i w_1 \overline{a_i} w_2$,
\[\begin{align*} w &⟶_{R_n} w_1 w_2 \\ &⟶_{R_n} 𝜀 w_2 \\ &⟶_{R_n} 𝜀 𝜀 \\ &⟶_{R_n} 𝜀 \end{align*}\]

$L ⊆ D_n^\ast$ :

Par induction sur la taille de la dérivation $w ⟶^\ast_{R_n} 𝜀$ :

  • Si $w=𝜀$ : OK

  • Si $w ⟶{R_n} a_i \overline{a_i} ⟶^\ast{R_n} 𝜀$ :

$w ≝ w’ a_i w’’ \overline{a_i} w’’’$ , où

$w’, w’’, w’’’ ∈ D_n^\ast$ par hypothèse d’induction.

Or, il vient par définition de la grammaire que

\[a_i w'' \overline{a_i} w''' ∈ D_n^\ast\]

Et comme $w’∈D_n^\ast$, il vient que

\[w ≝ w' a_i w'' \overline{a_i} w'''∈ D_n^\ast\]

(on montre aisément que $D_n^\ast$ est clos par concaténation)

EX 3

1.

\[G_1 ≝ ⟨N_1, 𝛴_1, P_1, S_1⟩ \\ G_2 ≝ ⟨N_2, 𝛴_2, P_2, S_2⟩\]

On indice les symboles non terminaux de la première (resp. la deuxième) grammaire par $1$ (resp. $2$), et on ajoute la règle :

\[S ⟶ S_1S_2\] \[G ≝ ⟨N_1 \sqcup N_2 \sqcup \lbrace S \rbrace, 𝛴_1 \sqcup 𝛴_2, P_1 ∪ P_2 ∪ \lbrace S ⟶ S_1 S_2 \rbrace, S⟩\]

2.

\[S ⟶ S S_1 \mid 𝜀\] \[G ≝ ⟨N_1 \sqcup \lbrace S \rbrace, 𝛴_1, P_1 ∪ \lbrace S ⟶ S S_1, S⟶𝜀 \rbrace, S⟩\]

3.

\[S ⟶ S_1 \mid S_2\] \[G ≝ ⟨N_1 \sqcup N_2 \sqcup \lbrace S \rbrace, 𝛴_1 \cup 𝛴_2, P_1 ∪ P_2 ∪ \lbrace S ⟶ S_1, S ⟶ S_2 \rbrace, S⟩\]

4.

\[G ≝ ⟨N_1, 𝛴_1, \widetilde{P_1}, S_1⟩\]

où

\[\widetilde{P_1} = \lbrace X ⟶ \widetilde{𝛼} \mid X ⟶ 𝛼 ∈ P \rbrace\]

5.

Pour $a∈𝛴$, soit

\[G_a ≝ ⟨N_a, 𝛴', P_a, S_a⟩\]

une grammaire qui reconnaît $𝜎(a)$

\[G ≝ ⟨N, 𝛴, P, S⟩\]

pour $L$

\[G' = \Bigg\langle N \sqcup \bigsqcup\limits_{a∈𝛴} N_a \sqcup 𝛴, 𝛴', P'∪ \bigcup\limits_{a∈A} P_a ∪ \lbrace a ⟶ Sa \rbrace, S \Bigg\rangle\]

EX 4

Soit $C$ un ensemble de clauses de HORN.

On construit $G ≝ ⟨N,𝛴, P, S⟩$ tq :

\[C \text{ satisfaisable } ⟺ L(G)=∅\]

À chaque clause

\[B_1 ∧ ⋯ ∧ B_n ⟶ A\]

Soit

\[C' ≝ \lbrace X ⟵ X_1 ∩ ⋯ ∩ X_n ∈ C \mid X ≠ \bot \rbrace \\ ∪ \lbrace S ⟵ X_1 ∩ ⋯ ∩ X_n \mid \bot ⟵ X_1 ∩ ⋯ ∩ X_n \rbrace \\ ∪ \lbrace \bot ⟵ S \rbrace\]
  • $N ≝ V∪ \lbrace S \rbrace$
  • $𝛴 ≝ ∅$
  • $P ≝ \lbrace X ⟶ X_1 ⋯ X_n \mid X ⟵ X_1 ∩ ⋯ ∩ X_n ∈ C’ \rbrace$

Supposons que $L(G) = ∅$ :

Soit

\[𝜈 : X \mapsto \begin{cases} 1 \text{ si } X ⟶^\ast 𝜀 \\ 0 \text{ sinon} \end{cases}\]
Montrons que $𝜈 \vDash C’$ :

  • $𝜈 \vDash \bot ⟵ S$ car $L(G)≠∅$

  • Soit $X ⟵ X_1 ∩ ⋯ ∩ X_n∈C’$

    • Si $∃i; 𝜈(X_i) = 0, 𝜈 \vDash X ⟵ X_1 ∩ ⋯ ∩ X_n$

    • Sinon : $X_i ⟶^\ast_{G}𝜀$ pour tout $i$

      Donc $X ⟶ X_1 ⋯ X_n ⟶^\ast 𝜀$ et on conclut

Supposons que $C$ est sastisfaisable

Soit $𝜈$ tq $𝜈 \vDash C$.

Mq pour tout $X$ tq $X⟶^\ast_{G} 𝜀$, $𝜈(X)=1$

Par réc sur la longueur minimale d’une dérivation $X ⟶^\ast 𝜀$

  • Si $X⟶𝜀$, alors $X∈C’$

  • Sinon $X⟶X_1 ⋯ X_n⟶^\ast 𝜀$

    Donc pour tout $i$, $X_i⟶^\ast 𝜀$ et par HR:

    • $𝜈(X_i) = 1$
    • $𝜈 \vDash X_1 ∩ ⋯ ∩ X_n$ et $𝜈 \vDash X ← X_1 ∩ ⋯ ∩ X_n$, donc $𝜈(X)=1$

Donc on ne peut pas avoir $L(G)≠∅$ car sinon $S⟶^\ast 𝜀$ (d’où $𝜈(S)=1$), et $L(G)=∅$

Leave a comment