Another exercise on context-free grammars.

2 files changed, 108 insertions, 0 deletions

diff --git a/exercices3.tex b/exercices3.tex
index a2fa873..9774b3a 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -515,6 +515,92 @@ camouflé sous forme d'analyseur par descente récursive.)
 \end{corrige}
 
 
+%
+%
+%
+
+\exercice
+
+On considère la grammaire hors contexte $G$ suivante (d'axiome $S$)
+sur l'alphabet $\Sigma = \{a,b\}$ :
+\[
+S \rightarrow SaS \;|\; b
+\]
+Soit $L = L(G)$ le langage algébrique qu'elle engendre.
+
+(0) Donner quelques exemples de mots dans $L$.
+
+(1) Cette grammaire $G$ est-elle ambiguë ?
+
+(2) Décrire simplement le langage $L$.
+
+(3) Donner une grammaire inambiguë engendrant le même langage $L$
+que $G$.
+
+\begin{corrige}
+(0) Quelques exemples de mots dans $L$ sont $b$, $bab$, $babab$, et
+  ainsi de suite (cf. (2)).
+
+(1) La grammaire $G$ est ambiguë : le mot $babab$ a deux arbres
+  d'analyse différents, à savoir
+\begin{center}
+\tikzstyle{automaton}=[scale=0.5]
+%%% begin ex3pt1 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (S3) at (27bp,90bp) [draw,draw=none] {$S$};
+  \node (S2) at (243bp,162bp) [draw,draw=none] {$S$};
+  \node (S1) at (99bp,162bp) [draw,draw=none] {$S$};
+  \node (S0) at (171bp,234bp) [draw,draw=none] {$S$};
+  \node (S4) at (171bp,90bp) [draw,draw=none] {$S$};
+  \node (a1) at (99bp,90bp) [draw,draw=none] {$a$};
+  \node (a0) at (171bp,162bp) [draw,draw=none] {$a$};
+  \node (b0) at (243bp,90bp) [draw,draw=none] {$b$};
+  \node (b1) at (27bp,18bp) [draw,draw=none] {$b$};
+  \node (b2) at (171bp,18bp) [draw,draw=none] {$b$};
+  \draw [] (S1) ..controls (70.042bp,132.85bp) and (55.714bp,118.92bp)  .. (S3);
+  \draw [] (S0) ..controls (142.04bp,204.85bp) and (127.71bp,190.92bp)  .. (S1);
+  \draw [] (S0) ..controls (171bp,204.85bp) and (171bp,190.92bp)  .. (a0);
+  \draw [] (S2) ..controls (243bp,132.85bp) and (243bp,118.92bp)  .. (b0);
+  \draw [] (S1) ..controls (99bp,132.85bp) and (99bp,118.92bp)  .. (a1);
+  \draw [] (S0) ..controls (199.96bp,204.85bp) and (214.29bp,190.92bp)  .. (S2);
+  \draw [] (S3) ..controls (27bp,60.846bp) and (27bp,46.917bp)  .. (b1);
+  \draw [] (S4) ..controls (171bp,60.846bp) and (171bp,46.917bp)  .. (b2);
+  \draw [] (S1) ..controls (127.96bp,132.85bp) and (142.29bp,118.92bp)  .. (S4);
+%
+\end{tikzpicture}
+
+%%% end ex3pt1 %%%
+\end{center}
+et son symétrique par rapport à l'axe vertical.
+
+(2) Montrons que $L$ est égal au langage $L_{(ba){*}b}$ dénoté par
+l'expression rationnelle $(ba){*}b$ comme la question (0) le laisse
+entrevoir.  Pour cela, il suffit de voir que l'ensemble des
+pseudo-mots (:= mots sur l'ensemble des terminaux et des nonterminaux)
+qu'on peut dériver de $S$ dans $G$ est le langage $((S|b)a){*}(S|b)$
+constitué des pseudo-mots de la forme $xaxax\cdots ax$ où chaque $x$
+est soit un $S$ soit un $b$, indépendamment les uns des autres.  Or il
+est clair que remplacer un $x$ (et notamment, remplacer un $S$) par
+$SaS$ (qui est de la forme $xax$) dans un pseudo-mot de cette forme
+donne encore un pseudo-mot de cette forme : ceci montre qu'une
+dérivation de $G$, quelle que soit l'application faite de la règle
+$S\rightarrow SaS$, donne des pseudo-mots de cette forme, donc tout
+pseudo-mot obtenu par dérivation de $S$ dans la grammaire $G$ est de
+la forme qu'on vient de dire ; et réciproquement, il est facile de
+produire n'importe quel nombre $n$ de répéritions du motif $aS$ en
+appliquant $n$ fois la règle $S\rightarrow SaS$ à partir de $S$, et on
+peut ensuite librement transformer certains $S$ en $b$.
+
+(3) La grammaire $G'$ donnée par $S \rightarrow baS\,|\,b$ engendre le
+même langage que $G$ d'après la question précédente ; et il est
+évident que cette grammaire est inambiguë : toutes les dérivations
+sont de la forme $S \Rightarrow baS \Rightarrow babaS \Rightarrow
+(ba)^n S$ suivie éventuellement de $\Rightarrow (ba)^n b$.
+\end{corrige}
+
+
 
 %
 %
diff --git a/figs/ex3pt1.dot b/figs/ex3pt1.dot
new file mode 100644
index 0000000..1628103
--- /dev/null
+++ b/figs/ex3pt1.dot
@@ -0,0 +1,22 @@
+graph ex3pt1 {
+	node [texmode="math",shape="none"];
+	S0 [label="S"];
+	S1 [label="S"];
+	a0 [label="a"];
+	S2 [label="S"];
+	S3 [label="S"];
+	a1 [label="a"];
+	S4 [label="S"];
+	b0 [label="b"];
+	b1 [label="b"];
+	b2 [label="b"];
+	S0 -- S1;
+	S0 -- a0;
+	S0 -- S2;
+	S1 -- S3;
+	S1 -- a1;
+	S1 -- S4;
+	S2 -- b0;
+	S3 -- b1;
+	S4 -- b2;
+}