diff options
Diffstat (limited to 'controle-20200123.tex')
| -rw-r--r-- | controle-20200123.tex | 105 |
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} % |