summaryrefslogtreecommitdiffstats log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
Diffstat (limited to 'controle-20190205.tex')
-rw-r--r--controle-20190205.tex212
1 files changed, 204 insertions, 8 deletions
 diff --git a/controle-20190205.tex b/controle-20190205.texindex 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 :\\+% Sa.Sb.Sa.Sb.S>>+\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+% Sa.Sb.S>a.Sb.S>+\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}+ % %