TD 4 : Langages algébriques

EX 1

1.

S ⟶ a S a ∣ b S b ∣ 𝜀

2.

\begin{matrix} S ⟶ U b ∣ a T \\ T ⟶ a T b ∣ a T ∣ 𝜀 \\ U ⟶ a U b ∣ U b ∣ 𝜀 \end{matrix}

\begin{matrix} S ⟶ a A ∣ B b \\ A ⟶ a A ∣ C \\ B ⟶ B b ∣ C \\ C ⟶ a C b ∣ 𝜀 \end{matrix}

3.

\begin{matrix} S ⟶ A B C ∣ 𝜀 \\ A ⟶ a A b ∣ 𝜀 \\ B ⟶ b B ∣ 𝜀 \\ C ⟶ b C c ∣ 𝜀 \end{matrix}

4.

S ⟶ a S b ∣ a S b b ∣ 𝜀

EX 2

1.

$D_{1}^{*} \subseteq L$ :

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

Si $w = 𝜀$ : immédiat
Sinon, si $S ⟶ a_{1} S \overset{―}{a_{1}} S ⟶^{*} w$ , alors il existe $w_{1}, w_{2}$ tq $S ⟶^{*} w_{1}, S ⟶^{*} w_{2}$ et $w = a_{1} w_{1} \overset{―}{a_{1}} w_{2}$ : on conclut car par hypothèse d’induction : $w_{1}, w_{2} \in D_{1}^{*}$

$L \subseteq D_{1}^{*}$ :

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

Si $w = 𝜀$ : OK
Si $| w | > 0$ :

Comme, par hypothèse,

| w [1] |_{a_{1}} \geq | w [1] |_{\overset{―}{a_{1}}}

alors $w [1] = a_{1}$ , et

w ≝ a_{1} w_{1} \overset{―}{a_{1}} w_{2}

où $a_{1} w_{1} \overset{―}{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} \overset{―}{a_{1}} \in L$
et donc, par suite, que : $w_{2} \in L$ (il a autant de parenthèses ouvrantes que fermantes car c’est le cas de $w$ et de $a_{1} w_{1} \overset{―}{a_{1}}$ , et on vérifie que tous ses préfixes ont plus de parenthèses ouvrantes que fermantes car $a_{1} w_{1} \overset{―}{a_{1}}$ a autant de parenthèses ouvrantes que fermantes)

2.

$D_{n}^{*} \subseteq L$ :

Preuve par induction structurelle :

Si $w = 𝜀$ : OK
Sinon, si $S ⟶ a_{1} S \overset{―}{a_{1}} S ⟶^{*} w$ , alors il existe $w_{1}, w_{2}$ tq $S ⟶^{*} w_{1}, S ⟶^{*} w_{2}$ et $w = a_{i} w_{1} \overset{―}{a_{i}} w_{2}$ ,

\begin{aligned} w & ⟶_{R_{n}} w_{1} w_{2} \\ ⟶_{R_{n}} 𝜀 w_{2} \\ ⟶_{R_{n}} 𝜀 𝜀 \\ ⟶_{R_{n}} 𝜀 \end{aligned}

$L \subseteq D_{n}^{*}$ :

Par induction sur la taille de la dérivation $w ⟶_{R_{n}}^{*} 𝜀$ :

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

$w ≝ w^{'} a_{i} w^{″} \overset{―}{a_{i}} w^{‴}$ , où

$w^{'}, w^{″}, w^{‴} \in D_{n}^{*}$ par hypothèse d’induction.

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

a_{i} w^{″} \overset{―}{a_{i}} w^{‴} \in D_{n}^{*}

Et comme $w^{'} \in D_{n}^{*}$ , il vient que

w ≝ w^{'} a_{i} w^{″} \overset{―}{a_{i}} w^{‴} \in D_{n}^{*}

(on montre aisément que $D_{n}^{*}$ est clos par concaténation)

EX 3

1.

\begin{matrix} G_{1} ≝ ⟨ N_{1}, 𝛴_{1}, P_{1}, S_{1} ⟩ \\ G_{2} ≝ ⟨ N_{2}, 𝛴_{2}, P_{2}, S_{2} ⟩ \end{matrix}

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_{1} S_{2}

G ≝ ⟨ N_{1} ⊔ N_{2} ⊔ {S}, 𝛴_{1} ⊔ 𝛴_{2}, P_{1} \cup P_{2} \cup {S ⟶ S_{1} S_{2}}, S ⟩

2.

S ⟶ S S_{1} ∣ 𝜀

G ≝ ⟨ N_{1} ⊔ {S}, 𝛴_{1}, P_{1} \cup {S ⟶ S S_{1}, S ⟶ 𝜀}, S ⟩

3.

S ⟶ S_{1} ∣ S_{2}

G ≝ ⟨ N_{1} ⊔ N_{2} ⊔ {S}, 𝛴_{1} \cup 𝛴_{2}, P_{1} \cup P_{2} \cup {S ⟶ S_{1}, S ⟶ S_{2}}, S ⟩

4.

G ≝ ⟨ N_{1}, 𝛴_{1}, \tilde{P_{1}}, S_{1} ⟩

où

\tilde{P_{1}} = {X ⟶ \tilde{𝛼} ∣ X ⟶ 𝛼 \in P}

5.

Pour $a \in 𝛴$ , soit

G_{a} ≝ ⟨ N_{a}, 𝛴^{'}, P_{a}, S_{a} ⟩

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

G ≝ ⟨ N, 𝛴, P, S ⟩

pour $L$

G^{'} = ⟨ N ⊔ ⨆_{a \in 𝛴} N_{a} ⊔ 𝛴, 𝛴^{'}, P^{'} \cup ⋃_{a \in A} P_{a} \cup {a ⟶ S a}, S ⟩

EX 4

Soit $C$ un ensemble de clauses de HORN.

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

C satisfaisable ⟺ L (G) = \emptyset

À chaque clause

B_{1} \land \dots \land B_{n} ⟶ A

Soit

\begin{matrix} C^{'} ≝ {X ⟵ X_{1} \cap \dots \cap X_{n} \in C ∣ X \neq ⊥} \\ \cup {S ⟵ X_{1} \cap \dots \cap X_{n} ∣ ⊥ ⟵ X_{1} \cap \dots \cap X_{n}} \\ \cup {⊥ ⟵ S} \end{matrix}

$N ≝ V \cup {S}$
$𝛴 ≝ \emptyset$
$P ≝ {X ⟶ X_{1} \dots X_{n} ∣ X ⟵ X_{1} \cap \dots \cap X_{n} \in C^{'}}$

Supposons que $L (G) = \emptyset$ :

Soit

𝜈 : X \mapsto {\begin{cases} 1 si X ⟶^{*} 𝜀 \\ 0 sinon \end{cases}

Montrons que $𝜈 ⊨ C^{'}$ :

$𝜈 ⊨ ⊥ ⟵ S$ car $L (G) \neq \emptyset$
Soit $X ⟵ X_{1} \cap \dots \cap X_{n} \in C^{'}$
- Si $\exists i; 𝜈 (X_{i}) = 0, 𝜈 ⊨ X ⟵ X_{1} \cap \dots \cap X_{n}$
- Sinon : $X_{i} ⟶_{G}^{*} 𝜀$ pour tout $i$
  
  Donc $X ⟶ X_{1} \dots X_{n} ⟶^{*} 𝜀$ et on conclut

Supposons que $C$ est sastisfaisable

Soit $𝜈$ tq $𝜈 ⊨ C$ .

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

Par réc sur la longueur minimale d’une dérivation $X ⟶^{*} 𝜀$

Si $X ⟶ 𝜀$ , alors $X \in C^{'}$
Sinon $X ⟶ X_{1} \dots X_{n} ⟶^{*} 𝜀$

Donc pour tout $i$ , $X_{i} ⟶^{*} 𝜀$ et par HR:
- $𝜈 (X_{i}) = 1$
- $𝜈 ⊨ X_{1} \cap \dots \cap X_{n}$ et $𝜈 ⊨ X \leftarrow X_{1} \cap \dots \cap X_{n}$ , donc $𝜈 (X) = 1$

Donc on ne peut pas avoir $L (G) \neq \emptyset$ car sinon $S ⟶^{*} 𝜀$ (d’où $𝜈 (S) = 1$ ), et $L (G) = \emptyset$

Share on

Twitter Facebook Google+ LinkedIn