diff options
| -rw-r--r-- | controle-20190205.tex | 212 |
1 files changed, 204 insertions, 8 deletions
diff --git a/controle-20190205.tex b/controle-20190205.tex index a3e6f08..9cda4c2 100644 --- a/controle-20190205.tex +++ b/controle-20190205.tex @@ -393,19 +393,67 @@ S &\rightarrow \varepsilon\\ (1) Montrer que cette $G$ est ambiguë : pour cela, on exhibera deux arbres d'analyse différents du mot $abab$. +\begin{corrige} + +On peut proposer les arbres d'analyse suivants :\\ +% S<S<e.>a.S<e.>b.S<S<e.>a.S<e.>b.S<e.>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (48.000bp,0.000bp) [draw=none] {$S$}; +\node (S1) at (0.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (e0) at (0.000bp,-50.000bp) [draw=none] {$\varepsilon$}; \draw (S1) -- (e0); +\node (a0) at (20.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S2) at (40.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S2); +\node (e1) at (40.000bp,-50.000bp) [draw=none] {$\varepsilon$}; \draw (S2) -- (e1); +\node (b0) at (60.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (S3) at (120.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S3); +\node (S4) at (80.000bp,-60.000bp) [draw=none] {$S$}; \draw (S3) -- (S4); +\node (e2) at (80.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S4) -- (e2); +\node (a1) at (100.000bp,-60.000bp) [draw=none] {$a$}; \draw (S3) -- (a1); +\node (S5) at (120.000bp,-60.000bp) [draw=none] {$S$}; \draw (S3) -- (S5); +\node (e3) at (120.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S5) -- (e3); +\node (b1) at (140.000bp,-60.000bp) [draw=none] {$b$}; \draw (S3) -- (b1); +\node (S6) at (160.000bp,-60.000bp) [draw=none] {$S$}; \draw (S3) -- (S6); +\node (e4) at (160.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S6) -- (e4); +\end{tikzpicture} +d'une part,\hfill et +% S<S<S<e.>a.S<e.>b.S<e.>>a.S<e.>b.S<e.>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (112.000bp,0.000bp) [draw=none] {$S$}; +\node (S1) at (40.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (S2) at (0.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (e0) at (0.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S2) -- (e0); +\node (a0) at (20.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a0); +\node (S3) at (40.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S3); +\node (e1) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S3) -- (e1); +\node (b0) at (60.000bp,-60.000bp) [draw=none] {$b$}; \draw (S1) -- (b0); +\node (S4) at (80.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S4); +\node (e2) at (80.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S4) -- (e2); +\node (a1) at (100.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a1); +\node (S5) at (120.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S5); +\node (e3) at (120.000bp,-50.000bp) [draw=none] {$\varepsilon$}; \draw (S5) -- (e3); +\node (b1) at (140.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b1); +\node (S6) at (160.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S6); +\node (e4) at (160.000bp,-50.000bp) [draw=none] {$\varepsilon$}; \draw (S6) -- (e4); +\end{tikzpicture} +d'autre part\\ +(en fait, on peut se convaincre que ce sont les seuls possibles). +La grammaire $G$ est donc ambiguë. +\end{corrige} \emph{Notation :} Si $w \in \Sigma^*$, on notera $|w|_a$ le nombre total d'occurrences de la lettre $a$ dans le mot $w$, et de façon analogue $|w|_b$ le nombre total d'occurrences de la lettre $b$ (on a -bien sûr $|w| = |w|_a + |w|_b$ puisque $\Sigma = \{a,b\}$). +bien sûr $|w| = |w|_a + |w|_b$ puisque $\Sigma = \{a,b\}$ ; on a par +ailleurs $|vv'|_a = |v|_a + |v'|_a$ et $|vv'|_b = |v|_b + |v'|_b$ pour +tous mots $v,v' \in \Sigma^*$). On se propose, dans les quelques questions suivantes, de montrer que le langage $L := L(G)$ engendré par la grammaire $G$ est l'ensemble $M$ des mots $w \in \Sigma^*$ vérifiant les deux propriétés suivantes : \begin{itemize} -\item[(A)] $|w|_b = |w|_a$, et -\item[(B)] $|u|_b \leq |u|_a$ pour tout préfixe $u$ de $w$ +\item[\quad(A)] $|w|_b = |w|_a$, et +\item[\quad(B)] $|u|_b \leq |u|_a$ pour tout préfixe $u$ de $w$ \end{itemize} (autrement dit, le nombre de $b$ de n'importe quel préfixe de $w$ est inférieur ou égal au nombre de $a$, et pour le mot $w$ tout entier il @@ -414,40 +462,188 @@ y a égalité). (2) Expliquer pourquoi un mot $w \in \Sigma^*$ appartient à $L$ si et seulement si $w = \varepsilon$ \emph{ou bien} $w$ s'écrit sous la forme $w_1 a w_2 b w_3$ où $w_1,w_2,w_3$ appartiennent à $L$. (On -pourra, par exemple, raisonner sur les arbres d'analyse.) +pourra raisonner sur les arbres d'analyse.) + +\begin{corrige} +Si $w \in L$, considérons un arbre d'analyse $\mathscr{T}$ de $w$ +pour $G$ : sa racine, étiquetée $S$, doit avoir des fils étiquetés +selon l'une des deux règles de la grammaire, soit $S\rightarrow +\varepsilon$ ou bien $S\rightarrow SaSbS$, autrement dit, soit elle a +un unique fils étiqueté $\varepsilon$, soit elle a cinq fils étiquetés +respectivement $S,a,S,b,S$. Dans le premier cas, le mot $w$ est +simplement $\varepsilon$ ; dans le second, les sous-arbres +$\mathscr{T}_1, \mathscr{T}_2, \mathscr{T}_3$ ayant pour racine les +trois fils étiquetés $S$ sont encore des arbres d'analyse pour $G$, et +si on appelle $w_1,w_2,w_3$ les mots dont ils sont des arbres +d'analyse (c'est-à-dire que $w_i$ est obtenu en lisant les feuilles de +$\mathscr{T}_i$ par ordre de profondeur), alors on a $w = w_1 a w_2 b +w_3$ et $w_1,w_2,w_3\in L$ (puisqu'ils ont des arbres d'analyse +pour $G$). + +La réciproque est analogue : le mot $\varepsilon$ appartient +trivialement à $L$, et si $w_1,w_2,w_3\in L$, ils ont des arbres +d'analyse $\mathscr{T}_1, \mathscr{T}_2, \mathscr{T}_3$ pour $G$, et +on peut fabriquer un arbre d'analyse pour $w := w_1 a w_2 b w_3$ qui a +une racine étiquetée $S$ ayant cinq fils étiquetés $S,a,S,b,S$, les +trois étiquetés $S$ ayant pour descendants des sous-arbres donnés par +$\mathscr{T}_1, \mathscr{T}_2, \mathscr{T}_3$ dans cet ordre. +\end{corrige} -(3) Expliquer \emph{brièvement} pourquoi, si $w_1, w_2, w_3 \in +(3) Expliquer brièvement pourquoi, si $w_1, w_2, w_3 \in \Sigma^*$, alors tout préfixe du mot $w_1 a w_2 b w_3$ est d'une des trois formes suivantes : (i) $u_1$ pour $u_1$ un préfixe de $w_1$, (ii) $w_1 a u_2$ pour $u_2$ un préfixe de $w_2$, ou (iii) $w_1 a w_2 b u_3$ pour $u_3$ un préfixe de $w_3$. (On rappelle que le mot vide et le mot tout entier comptent pour préfixes d'un mot.) +\begin{corrige} +Remarquons qu'un préfixe d'une concaténation $v v'$ est soit un +préfixe $u$ de $v$ soit de la forme $v u'$ avec $u'$ préfixe de $v'$ +(cela se voit immédiatement en écrivant, disons, $v = x_1 \cdots x_m$ +et $v' = y_1 \cdots y_n$ où $x_1,\ldots,x_m$ et $y_1,\ldots,y_n$ sont +les lettres de $v$ et $v'$ respectivement : un préfixe de $x_1 \cdots +x_m y_1 \cdots y_n$ est soit de la forme $x_1 \cdots x_r$ soit de la +forme $x_1 \cdots x_m y_1 \cdots y_s$). + +En appliquant cette remarque au produit quintuple $w_1 a w_2 b w_3$ et +en notant qu'un préfixe du mot (d'une lettre) $a$ est simplement +$\varepsilon$ ou $a$, on a les différents cas signalés. +\end{corrige} + (4) Si $w_1, w_2, w_3 \in \Sigma^*$ vérifient tous les trois la propriété (A) ci-dessus, montrer que c'est encore le cas de $w_1 a w_2 b w_3$. Si $w_1, w_2, w_3 \in \Sigma^*$ vérifient tous les trois la propriété (B) ci-dessus, montrer que c'est encore le cas de $w_1 a w_2 b w_3$ (on utilisera pour cela la question (3)). +\begin{corrige} +Si $w_1, w_2, w_3$ vérifient (A) (c'est-à-dire $|w_i|_b = |w_i|_a$), +alors $|w_1 a w_2 b w_3|_a = |w_1|_a + |w_2|_a + |w_3|_a + 1$ et alors +$|w_1 a w_2 b w_3|_b = |w_1|_b + |w_2|_b + |w_3|_b + 1$ donc ces deux +quantités sont égales et $w_1 a w_2 b w_3$ vérifie (A). + +Si $w_1, w_2, w_3$ vérifient (B) (c'est-à-dire $|u|_b \leq |u|_a$ pour +tout préfixe $u$ d'un des $w_i$), alors en notant $u_i$ un préfixe +quelconque du $w_i$ correspondant, on a (i) $|u_1|_b \leq |u_1|_a$, +(ii) $|w_1 a u_2|_b = |w_1|_b + |u_2|_b + 1 \leq |w_1|_a + |u_2|_a + 1 += |w_1 a u_2|_a$ et (iii) $|w_1 a w_2 b u_3|_b \leq |w_1|_b + |w_2|_b ++ |u_3|_b + 1 \leq |w_1|_a + |w_2|_a + |u_3|_a + 1 = |w_1 a w_2 b +u_3|_a$. D'après la question (3), on peut en conclure que tout +préfixe $u$ de $w_1 a w_2 b w_3$ vérifie $|u|_b \leq |u|_a$, +c'est-à-dire que $w_1 a w_2 b w_3$ vérifie (B). +\end{corrige} + (5) Déduire des questions (2) et (4) que tout mot de $L$ vérifie (A) et (B). (Autrement dit, on vient de montrer : $L \subseteq M$.) +\begin{corrige} +On procède par récurrence sur la longueur du mot $w$ de $L$ pour +montrer que $w$ vérifie (A) et (B). Si $|w|=0$, on a $w = \varepsilon$ +qui vérifie manifestement (A) et (B). Si $w\neq\varepsilon$, +d'après (2), on peut écrire $w = w_1 a w_2 b w_3$ où $w_1,w_2,w_3$ +sont dans $L$, et comme ils sont de longueur strictement plus petite +que $w$, d'après l'hypothèse de récurrence ils vérifient (A) et (B), +si bien que $w$ vérifie aussi (A) et (B) d'après la question (4). +\end{corrige} + (6) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B) : montrer qu'on peut écrire $w = av$ pour un certain $v \in \Sigma^*$ ; si $w'$ -est le plus long préfixe de $v$ vérifiant (B), montrer que $w = -aw'bw''$ où $w'$ et $w''$ vérifient tous les deux (A) et (B). +est le plus long préfixe de $v$ vérifiant (B)\footnote{Autrement dit, + le plus long préfixe $w'$ de $v$ tel que pour tout préfixe $u'$ + de $w'$ (y compris $w'$ lui-même) on ait $|u'|_b\leq |u'|_a$.}, +montrer qu'on a $w = aw'bw''$ pour un certain $w'' \in \Sigma^*$ ; +puis montrer que $w'$ vérifie (B), puis qu'il vérifie (A), et enfin +que $w''$ vérifie (A) et (B). + +\begin{corrige} +Comme $w$ est un mot non vide, on peut parler de sa première +lettre $x$, qui en est un préfixe (de longueur $1$), et qui doit +vérifier $|x|_b \leq |x|_a$ d'après (B), ce qui n'est évidemment +possible que pour $x=a$. On a donc $w = av$ où $v$ est le suffixe +correspondant à $a$. + +Remarquons que $|v|_b = |w|_b = |w|_a = 1 + |v|_a$ donc $|v|_b > +|v|_a$, et en particulier, $v$ \emph{ne} vérifie \emph{pas} (B). Si +maintenant $w'$ est le plus long préfixe de $v$ vérifiant (B), la +remarque qu'on vient de faire montre que $w' \neq v$, donc il y a au +moins une lettre qui suit $w'$ dans $v$ ; et cette lettre ne peut pas +être $a$ car si $v$ vérifie (B) alors $va$ le vérifie aussi (le seul +préfixe de $va$ qui n'était pas dans $v$ étant $va$ lui-même, qui +vérifie $|va|_b = |v|_b \leq |v|_a < |va|_a$) : on peut donc écrire $v += w'bw''$ pour un certain $w''\in\Sigma^*$, c'est-à-dire $w = +aw'bw''$. + +Le mot $w'$ vérifie (B) : en effet, si $u'$ est préfixe de $w'$ alors +$au'$ en est un de $w$, et on a $|u'|_b = |au'|_b \leq |au'|_a = +1+|u'|_a$. Montrons par l'absurde que $w'$ vérifie (A) : si ce n'est +pas le cas, comme $|w'|_b \leq |w'|_a$ (par (B), qu'on vient de +montrer), on a $|w'|_b < |w'|_a$, mais alors $|w'b|_b = |w'|_b + 1 +\leq |w'|_a = |w'b|_a$ donc $w'b$ vérifie encore (B), ce qui contredit +le fait que $w'$ était \emph{le plus long} préfixe de $v$ +vérifiant (B). Le mot $w''$ vérifie (A) : en effet, on a $|w|_b = +|w|_a$ (puisque $w$ vérifie (A)), c'est-à-dire $|w'|_b + |w''|_b + 1 = +|w'|_a + |w''|_a + 1$, et comme on vient de voir que $|w'|_b = +|w'|_a$, on a aussi $|w''|_b = |w''|_a$. Enfin, le mot $w''$ +vérifie (B) : en effet, si $u''$ est un préfixe de $w''$ alors +$aw'bu''$ est un préfixe de $w = aw'bw''$ donc (puisque $w$ +vérifie (B)) on a $|aw'bu''|_b \leq |aw'bu''|_a$, c'est-à-dire $|w'|_b ++ |u''|_b + 1 \leq |w'|_a + |u''|_a + 1$ donc (toujours puisque +$|w'|_b = |w'|_a$ qu'on vient de voir) $|u''|_b \leq |u''|_a$ comme +annoncé. +\end{corrige} (7) Déduire des questions (2) et (6) que tout mot vérifiant (A) et (B) appartient à $L$. (Autrement dit, on vient de montrer : $M \subseteq L$. On a donc $L = M$.) +\begin{corrige} +On procède par récurrence sur la longueur du mot $w$ vérifiant +(A) et (B) pour montrer que $w$ appartient à $L$. Si $|w|=0$, on a $w += \varepsilon$ qui appartient manifestement à $L$. Si +$w\neq\varepsilon$, d'après (6), on peut écrire $w = aw'bw''$ où +$w',w''$ vérifient (A) et (B), et comme ils sont de longueur +strictement plus petite que $w$, d'après l'hypothèse de récurrence ils +appartiennent à $L$, si bien que $w$ appartient aussi à $L$ d'après la +question (4). + +\emph{Remarque :} On a en fait montré que $L = L(G)$ coïncide avec le +langage $L'$ engendré par la grammaire $S \rightarrow \varepsilon\;|\; +aSbS$ ; en effet, la question (7) montre que $M\subseteq L'$, la +question (5) montre que $L\subseteq M$, et on a évidemment +$L'\subseteq L$ : donc $L=L'=M$. +\end{corrige} + (8) En notant $N = \{a^i b^j : i,j\in\mathbb{N}\}$ le langage défini par l'expression rationnelle $a{*}b{*}$, et en utilisant la description qu'on vient de trouver pour $L$ (comme l'ensemble des mots -vérifiant (A) et (B)), déterminer $L \cap N$. Est-il rationnel ? +vérifiant (A) et (B)), déterminer $L \cap N$, et observer qu'il n'est +pas rationnel. + +\begin{corrige} +Montrons que $L\cap N = \{a^k b^k : k\in\mathbb{N}\}$ : si $w \in +L\cap N$, alors $w$ s'écrit sous la forme $a^i b^j$ puisque $w\in N$, +et comme $w\in L$ vérifie (A) d'après la question (5), on a $j = |w|_b += |w|_a = i$, c'est-à-dire que $w$ est de la forme $a^k b^k$ ; +réciproquement, si $w$ est de la forme $a^k b^k$ alors $w \in N$ et il +vérifie manifestement (A), et par ailleurs, tout préfixe $u$ de $w$ +est de la forme $a^\ell$ ou bien $a^k b^\ell$ où $0\leq \ell\leq k$ et +dans les deux cas vérifie $|u|_b \leq |u|_a$, c'est-à-dire que $w$ +vérifie (B), donc $w\in L$ d'après la question (7), bref $w \in L\cap +N$. + +On sait (comme application vue en cours du lemme de pompage) que le +langage $\{a^k b^k : k\in\mathbb{N}\}$ n'est pas rationnel. +\end{corrige} (9) Le langage $L$ est-il rationnel ? +\begin{corrige} +Si le langage $L$ était rationnel, alors son intersection $L\cap N$ +avec le langage rationnel $N$ serait aussi rationnelle, mais on vient +de voir que $L\cap N$ n'est pas rationnel ; c'est donc que $L$ n'est +pas rationnel. +\end{corrige} + % % |