diff options
| -rw-r--r-- | exercices3.tex | 86 | ||||
| -rw-r--r-- | figs/ex3pt1.dot | 22 |
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; +} |