Write answer to exercise on CFGs.

1 files changed, 100 insertions, 5 deletions

diff --git a/controle-20200123.tex b/controle-20200123.tex
index e719177..9f4635e 100644
--- a/controle-20200123.tex
+++ b/controle-20200123.tex
@@ -506,11 +506,106 @@ démontrer.)
 (1) Donner les arbres d'analyse (= de dérivation) des mots suivants :
 $cacbcac$ et $cbcacbc$.
 
-(2) Expliquer pourquoi le langage $L := L(G)$ engendré par $G$ est, en
-fait, rationnel et donner une expression rationnelle qui le dénote.
-(On pourra commencer par décrire le langage $L' := L(G,T) := \{w \in
-\Sigma^* : T \mathrel{\Rightarrow^*_G} w\}$ des mots qui dérivent
-de $T$ selon $G$.)
+\begin{corrige}
+On obtient les arbres d'analyse suivants :
+
+\hbox to\hsize{
+% S<T<U<c.>>a.S<T<U<c.>b.T<U<c.>>>a.S<T<U<c.>>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (37.778bp,0.000bp) [draw=none] {$S$};
+\node (T0) at (0.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T0);
+\node (U0) at (0.000bp,-50.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (c0) at (0.000bp,-70.000bp) [draw=none] {$c$};  \draw (U0) -- (c0);
+\node (a0) at (20.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (S1) at (93.333bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (T1) at (60.000bp,-60.000bp) [draw=none] {$T$};  \draw (S1) -- (T1);
+\node (U1) at (40.000bp,-90.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (c1) at (40.000bp,-110.000bp) [draw=none] {$c$};  \draw (U1) -- (c1);
+\node (b0) at (60.000bp,-90.000bp) [draw=none] {$b$};  \draw (T1) -- (b0);
+\node (T2) at (80.000bp,-90.000bp) [draw=none] {$T$};  \draw (T1) -- (T2);
+\node (U2) at (80.000bp,-110.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (c2) at (80.000bp,-130.000bp) [draw=none] {$c$};  \draw (U2) -- (c2);
+\node (a1) at (100.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
+\node (S2) at (120.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (T3) at (120.000bp,-80.000bp) [draw=none] {$T$};  \draw (S2) -- (T3);
+\node (U3) at (120.000bp,-100.000bp) [draw=none] {$U$};  \draw (T3) -- (U3);
+\node (c3) at (120.000bp,-120.000bp) [draw=none] {$c$};  \draw (U3) -- (c3);
+\end{tikzpicture}
+\hss et\hss
+% S<T<U<c.>b.T<U<c.>>>a.S<T<U<c.>b.T<U<c.>>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (60.000bp,0.000bp) [draw=none] {$S$};
+\node (T0) at (20.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T0);
+\node (U0) at (0.000bp,-60.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (c0) at (0.000bp,-80.000bp) [draw=none] {$c$};  \draw (U0) -- (c0);
+\node (b0) at (20.000bp,-60.000bp) [draw=none] {$b$};  \draw (T0) -- (b0);
+\node (T1) at (40.000bp,-60.000bp) [draw=none] {$T$};  \draw (T0) -- (T1);
+\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (c1) at (40.000bp,-100.000bp) [draw=none] {$c$};  \draw (U1) -- (c1);
+\node (a0) at (60.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (S1) at (100.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (T2) at (100.000bp,-50.000bp) [draw=none] {$T$};  \draw (S1) -- (T2);
+\node (U2) at (80.000bp,-80.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (c2) at (80.000bp,-100.000bp) [draw=none] {$c$};  \draw (U2) -- (c2);
+\node (b1) at (100.000bp,-80.000bp) [draw=none] {$b$};  \draw (T2) -- (b1);
+\node (T3) at (120.000bp,-80.000bp) [draw=none] {$T$};  \draw (T2) -- (T3);
+\node (U3) at (120.000bp,-100.000bp) [draw=none] {$U$};  \draw (T3) -- (U3);
+\node (c3) at (120.000bp,-120.000bp) [draw=none] {$c$};  \draw (U3) -- (c3);
+\end{tikzpicture}
+}
+
+(On les trouve plus facilement si on se convainc d'abord que la
+grammaire peut être vue comme décrivant une expression de termes $c$
+reliés par deux opérations binaires $a$ et $b$, toutes les deux
+associatives à droite, et l'opération $b$ étant prioritaire sur $a$.
+Autrement dit, l'expression dérivant de $S$ est coupée d'abord au
+niveau des $a$ en des sous-expressions dérivant de $T$, elles-mêmes
+coupées au niveau des $b$.)
+\end{corrige}
+
+(2) Le langage $L := L(G)$ engendré par $G$ est, en fait, rationnel :
+expliquer brièvement pourquoi et donner une expression rationnelle qui
+le dénote.  (On pourra commencer par décrire le langage $L' := L(G,T)
+:= \{w \in \Sigma^* : T \mathrel{\Rightarrow^*_G} w\}$ des mots qui
+dérivent de $T$ selon $G$.)
+
+\begin{corrige}
+Le langage $L' = L(G,T)$ est celui décrit par la grammaire $T
+\rightarrow c \;|\; cbT$ d'axiome $T$ (le nonterminal $U$ est
+visiblement inutile et peut être directement remplacé par $c$ pour y
+voir plus clair).  Il s'agit visiblement du langage dénoté par
+l'expression rationnelle $(cb){*}c$ (ceci se démontre par exemple en
+remarquant que ses dérivations sont toutes de la forme $T \Rightarrow
+cbT \Rightarrow \cdots \Rightarrow (cb)^k T \Rightarrow (cb)^k c$, ou
+en raisonnant sur les arbres d'analyse qui sont formés en empilant des
+$T$ ayant pour fils gauche $c$ et $b$ et pour fils droite un autre $T$
+jusqu'à un dernier $T$ qui a pour seul fils $c$ ; on peut aussi
+remarquer qu'il s'agit essentiellement d'une grammaire régulière) : si
+on préfère, $L'$ est le plus petit langage tel que $L' = \{c\} \cup
+(\{c\}\{b\}L')$, ce que dénote justement $(cb){*}c$.  Bref, un mot de
+$L'$ est une succession de $c$ séparés par des $b$, ce que dénote
+justement $(cb){*}c$.
+
+Le langage $L = L(G,S)$ est construit selon exactement le même modèle
+à partir de $L'$ que $L'$ à partir de $c$ : si on préfère, $L$ est le
+plus petit langage tel que $L = L' \cup (L'\{a\}L)$, donc on s'attend
+à avoir ce qu'il soit dénoté par $((cb){*}ca){*}(cb){*}c$.  On peut
+par exemple raisonner sur les arbres d'analyse : ils sont formés en
+empilant des $S$ ayant pour fils gauche $T$ et $a$ et pour fils droite
+un autre $S$ jusqu'à un dernier $S$ qui a pour seul fils $T$, et enfin
+en insérant un arbre d'analyse d'un mot de $L'$ comme descendance de
+chaque $T$.  Bref, un mot de $L$ est une succession de mots de $L'$
+séparés par des $a$, ce que dénote justement $((cb){*}ca){*}(cb){*}c$.
+
+Tout ceci étant dit, en fait, le langage $L$ est dénoté par une
+expression rationnelle plus simple, à savoir $(c(a|b)){*}c$ (ou encore
+$c((a|b)c){*}$ ou encore $c(ac|bc){*}$ ou toutes sortes d'autres
+variantes), puisqu'il s'agit d'une succession de $c$ séparés
+indifféremment par des $a$ ou des $b$.  Cette expression rationnelle
+perd le découpage en deux niveaux (d'abord par $a$ puis par $b$)
+effectué par la grammaire $G$, mais est correcte comme description du
+langage.
+\end{corrige}
 
 
 %