Correction de l’exercice 1

Question 1 : Calcul des R_{i} définis par :

\{ \begin{matrix}R_{0} & = & \{f/∃u ∈ C, uf ∈ C\} \\ R_{i} & = & \{f/∃u ∈ R_{i−1}, uf ∈ C\} ∪ \{f/∃u ∈ C, uf ∈ R_{i−1}\} \end{matrix}

\begin{aligned}C & = \{001, 101, 00101, 0110, 1101, 1001, 00111\} \\ R_{0} & = \{01, 11\} \\ R_{1} & = \{10, 01\} ∪ \{\} \\ R_{2} & = \{1, 01, 10\} ∪ \{\} \\ R_{3} & = \{01, 101, 001, 10, 1\} ∪ \{\} \end{aligned}

Cette application ne définit pas un code car : R_{3} ∩ C = {001, 101}. Une preuve directe : (qui utilise la construction précédente). ϕ^{−1}(001 01 10 1 001) = {adf, cba} et ϕ^{−1}(001 01 10 1 101) = {ade, cbb} Question 2 :

\begin{aligned}C & = \{001, 1010, 001010, 0110, 1101, 1001, 111\} \\ R_{0} & = \{010\} \\ R_{1} & = \{\} ∪ \{\} \\ R_{i} & = ∅ pour i > 0 \end{aligned}

Cette application définit un code car : ∀i, R_{i} ∩ C = ∅. Le code est à delai borné car : ∀i > 1, R_{i} = ∅. Question 3 :

Figure 1: automate avec sortie pour décoder ϕ

Question 4 : Un programme lex possible pour decoder ϕ.

%option noyywrap
%{
%}
%%
001/(011|00|1|m) {printf("a");}
1010             {printf("b");}
001010           {printf("c");}
0110             {printf("d");}
1101             {printf("e");}
1001             {printf("f");}
111              {printf("g");}
m                {printf("\n");return;}
.                {printf("Error");}
%%
main()
{
  yylex();
}

Correction de l’exercice 2

Question 2.1 Rappels :

null(X) : les non-terminaux qui engendrent le mot vide.

premier(X) : les terminaux qui commencent les chaines dérivées de X.

suivant(X) : les terminaux qui apparaissent à droite de X.

Non terminaux Null(X)

S_{0} ⇒ aS m F aux
S ⇒ T U  V rai
T ⇒ aT b|ϵ  V rai
U ⇒ b|ϵ  V rai
premier(X) : P (X)  suivant(X) : S(X)
S_{0}  {a}  {a}  ∅  ∅
S P (T) ∪ P (U) {a, b}  {m}  {m}
T  {a}  {a} P (U) ∪ S(S) ∪ {b} {b, m}
U  {b}  {b}  S(S)  {m}

Question 2.2 Rappel : LL(1) ⟺ ∀X, X ⟶ α|β ⇒ premier(αsuivant(X)) ∩ premier(βsuivant(X)) = ∅

\begin{aligned}T : premier(aT b suivant(T)) ∩ premier(ϵ suivant(T)) & = \{a\} ∩ \{b, m\} = ∅ \\ U : premier(b suivant(U)) ∩ premier(ϵ suivant(U)) & = \{b\} ∩ \{m\} = ∅ \end{aligned}

La grammaire est donc LL(1).

Question 2.3 La table d’analyse :

a  b  m
So S → aSm
S S → T U S → T U S → T U
T T → aT b T → ϵ T → ϵ
U  U → b U → ϵ

Question 2.4 Le langage engendré :

S_{0} ⇒ a S m
⇒ a T U m
⇒^{∗} a (a T b)^{∗} U m
⇒ a (a b)^{∗} U m
⇒ a (a b)^{∗} b m ∪ a (a b)^{∗} m
⇒ {a^{n+1}b^{n+1}m, n ≥ 0} ∪ {a^{n+1}b^{n}m, n ≥ 0}
⇒ {a^{n}b^{n}m, n ≥ 1} ∪ {a^{n+1}b^{n}m, n ≥ 0}

Question 2.5 Une grammaire LL(1) reconnaissant le langage.

{a^{n}b^{n}m, n ≥ 0} ∪ {a^{n+1}b^{n}m, n ≥ 0} ∪ {a^{n}b^{n+1}m, n ≥ 0}

\begin{aligned}S_{0} & → & a S m | b m | m \\ S & → & T U \\ T & → & a T b | ϵ \\ U & → & b V | ϵ \\ V & → & b | ϵ \end{aligned}

Explication : la grammaire :

\begin{aligned}S_{0} & → & a S m \\ S & → & T U \\ T & → & a T b | ϵ \\ U & → & b V | ϵ \\ V & → & b | ϵ \end{aligned}

reconnait {a^{n}b^{n}m, n ≥ 1} ∪ {a^{n+1}b^{n}m, n ≥ 0} ∪ {a^{n+1}b^{n+2}m, n ≥ 0} Il faut donc ajouter les mots {m, bm} ce qui est fait avec S_{0}.