summaryrefslogtreecommitdiffstats log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiff
-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.texindex 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.dotnew file mode 100644index 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;+}