summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2019-01-28 17:44:28 +0100
committerDavid A. Madore <david+git@madore.org>2019-01-28 17:52:37 +0100
commit2d94ed784a0e32590947a68444ae92b8cae9d37e (patch)
tree6d5661d6e051782c8188dbcb03f1da42da4b14a3
parent79b7a10e9ff4e28617a3381fab09e7dec12a0cef (diff)
downloadinf105-2d94ed784a0e32590947a68444ae92b8cae9d37e.tar.gz
inf105-2d94ed784a0e32590947a68444ae92b8cae9d37e.tar.bz2
inf105-2d94ed784a0e32590947a68444ae92b8cae9d37e.zip
Write answers to exercise on CFGs.
-rw-r--r--controle-20190205.tex212
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}
+
%
%