summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2019-01-24 15:04:32 (GMT)
committerDavid A. Madore <david+git@madore.org>2019-01-24 15:04:32 (GMT)
commitd6dcbb677acf5faefe40ce6a13d8859a4926cd19 (patch)
treec9224b5a7d5a8b0ead3b0347d9e46216c693c873
parent759fe9dbf1a3a59929b3f4762938c46a6d7ab2ab (diff)
downloadinf105-d6dcbb677acf5faefe40ce6a13d8859a4926cd19.zip
inf105-d6dcbb677acf5faefe40ce6a13d8859a4926cd19.tar.gz
inf105-d6dcbb677acf5faefe40ce6a13d8859a4926cd19.tar.bz2
Add an exercise on CFGs.
-rw-r--r--controle-20190205.tex79
1 files changed, 78 insertions, 1 deletions
diff --git a/controle-20190205.tex b/controle-20190205.tex
index 166bb33..3802f51 100644
--- a/controle-20190205.tex
+++ b/controle-20190205.tex
@@ -96,6 +96,15 @@ Les exercices sont totalement indépendants. Ils pourront être traités
dans un ordre quelconque, mais on demande de faire apparaître de façon
très visible dans les copies où commence chaque exercice.
+Dans l'exercice \ref{exercise-on-finite-automata}, les différentes
+questions dépendent les unes des autres : il est donc impératif de les
+traiter dans l'ordre, et il est conseillé de vérifier soigneusement
+chaque réponse avant de passer à la suite. Dans
+l'exercice \ref{exercise-on-context-free-grammars}, les questions
+dépendent également les unes des autres, mais l'énoncé fournit toutes
+les informations nécessaires pour permettre de traiter la suite si on
+ne parvient pas à résoudre une question donnée.
+
\medbreak
L'usage de tous les documents (notes de cours manuscrites ou
@@ -122,7 +131,7 @@ Cet énoncé comporte \textcolor{red}{à remplir} (page de garde incluse)
%
%
-\exercice
+\exercice\label{exercise-on-finite-automata}
Dans cet exercice, on pose $\Sigma = \{a,b\}$.
@@ -371,6 +380,74 @@ On pouvait aussi donner, entre autres choses :
%
%
+\exercice\label{exercise-on-context-free-grammars}
+
+On considère la grammaire hors-contexte $G$ d'axiome $S$ sur
+l'alphabet $\Sigma = \{a,b\}$ donnée par
+\[
+\begin{aligned}
+S &\rightarrow SaSbS\\
+S &\rightarrow \varepsilon\\
+\end{aligned}
+\]
+
+(1) Montrer que cette $G$ est ambiguë : pour cela, on exhibera deux
+arbres d'analyse différents du mot $abab$.
+
+\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\}$).
+
+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$
+\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
+y a égalité).
+
+(2) Expliquer \emph{brièvement} pourquoi, si $w,w',w'' \in \Sigma^*$,
+alors tout préfixe du mot $waw'bw''$ est d'une des trois formes
+suivantes : (i) $u$ pour $u$ un préfixe de $w$, (ii) $wau'$ pour
+$u'$ un préfixe de $w'$, ou (iii) $waw'bu''$ pour $u''$ un préfixe
+de $w''$. (On rappelle que le mot vide et le mot tout entier comptent
+pour préfixes d'un mot.)
+
+(3) Si $w,w',w'' \in \Sigma^*$ vérifient tous les trois la
+propriété (A) ci-dessus, montrer que c'est encore le cas
+de $waw'bw''$. Si $w,w',w'' \in \Sigma^*$ vérifient tous les trois la
+propriété (B) ci-dessus, montrer que c'est encore le cas
+de $waw'bw''$ (on utilisera pour cela la question (2)).
+
+(4) Déduire de la question (3) que tout mot de $L$ vérifie (A) et (B).
+(Autrement dit, on vient de montrer : $L \subseteq M$.)
+
+(5) 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).
+
+(6) Déduire de la question (5) que tout mot vérifiant (A) et (B)
+appartient à $L$. (Autrement dit, on vient de montrer : $M \subseteq
+L$. On a donc $L = M$.)
+
+(7) 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 ?
+
+(8) Le langage $L$ est-il rationnel ?
+
+
+%
+%
+%
+
\exercice
On rappelle la définition du problème de l'arrêt : c'est l'ensemble