summaryrefslogtreecommitdiffstats log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
 diff --git a/controle-20200123.tex b/controle-20200123.texindex 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>a.Sb.T>>a.S>>>>+\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+% Sb.T>>a.Sb.T>>>>+\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} %