summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-30 15:16:54 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-30 15:16:54 (GMT)
commitd24301940a99a1321d088a01819dfe1a51634e2f (patch)
tree87664cdbe3064451b10665422e828f37dc0d3164
parent56f7f6f0e632baeffcc6116b4cd0a91b5e29c3ad (diff)
downloadinf105-d24301940a99a1321d088a01819dfe1a51634e2f.zip
inf105-d24301940a99a1321d088a01819dfe1a51634e2f.tar.gz
inf105-d24301940a99a1321d088a01819dfe1a51634e2f.tar.bz2
Another exercise on context-free grammars.
-rw-r--r--exercices3.tex86
-rw-r--r--figs/ex3pt1.dot22
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;
+}