From eaf01f87a735b97f1f8cdbdb48b06b62ee57aa9b Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sat, 4 Jun 2022 20:39:42 +0200
Subject: Re-read exam.
---
controle-20220616.tex | 54 +++++++++++++++++++++++++++------------------------
1 file changed, 29 insertions(+), 25 deletions(-)
diff --git a/controle-20220616.tex b/controle-20220616.tex
index 1ecbd0a..b1be47e 100644
--- a/controle-20220616.tex
+++ b/controle-20220616.tex
@@ -84,9 +84,11 @@
\noindent\textbf{Consignes.}
-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.
+Les exercices sont totalement indépendants (le premier teste
+l'application d'algorithmes vus en cours, le second est de nature plus
+théorique). 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.
\medbreak
@@ -99,12 +101,12 @@ L'usage des appareils électroniques est interdit.
Durée : 1h30
-Barème \emph{indicatif} : \textcolor{red}{à remplir}.
+Barème \emph{indicatif} : 10 points par exercice.
\ifcorrige
-Ce corrigé comporte \textcolor{red}{à remplir} pages (page de garde incluse).
+Ce corrigé comporte 9 pages (page de garde incluse).
\else
-Cet énoncé comporte \textcolor{red}{à remplir} pages (page de garde incluse).
+Cet énoncé comporte 4 pages (page de garde incluse).
\fi
\vfill
@@ -249,8 +251,8 @@ suivant :
(4) Donner de même l'automate minimal $\mathscr{A}_4$ du langage $L'
:= L(r')$ dénoté par l'expression rationnelle $r' := b{*}a{*}b{*}$.
-Comme ce langage, et donc cet automate, est simplement obtenu en
-échangeant $a$ et $b$ par rapport à ce qui précède, on donnera
+Comme cette expression, et donc cet automate, sont simplement obtenus
+en échangeant $a$ et $b$ par rapport à ce qui précède, on donnera
directement l'automate sans passer par les questions intermédiaires.
\begin{corrige}
@@ -408,7 +410,7 @@ un unique état final sans transition qui en parte :
\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
\draw[->] (q2a) -- node[auto]{$b$} (q3a);
\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a);
-\draw[->] (q2a) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q2a) -- node[auto,below]{$\varepsilon$} (qT);
\draw[->] (q3a) -- node[auto]{$\varepsilon$} (qT);
\draw[->] (q2) to[loop below] node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto,below]{$a$} (q3);
@@ -456,13 +458,14 @@ d'élimination des états).
\exercice
-Les parties (A), (B) et (C) de cet exercice sont indépendantes.
+Les parties (A), (B) et (C) de cet exercice sont indépendantes. On ne
+demande pas de justifications très longues.
\medskip
\textbf{(A)} On se propose de montrer que la question de savoir si
-(pour un alphabet $\Sigma$ fixé) une grammaire hors contexte $G$
-vérifie $L(G) \neq \varnothing$, est décidable. Autrement dit, on
+une grammaire hors contexte $G$ (sur un alphabet $\Sigma$ fixé)
+vérifie $L(G) \neq \varnothing$ est décidable. Autrement dit, on
veut montrer qu'il existe un algorithme qui prend en entrée une
grammaire hors contexte $G$, termine toujours en temps fini, et
renvoie « vrai » si $L(G) \neq \varnothing$ et « faux » si $L(G) =
@@ -515,13 +518,13 @@ pour $G$ tout court).
(3) Montrer que, quels que soient les entiers naturels $k$ et $m$, il
n'y a qu'un nombre fini d'arbres (finis enracinés ordonnés) de
-valence $\leq k$ à chaque sommet (c'est-à-dire que chaque sommet ait
-au plus $k$ fils), dont les sommets sont étiquetés par des étiquettes
-prises dans un ensemble $\{Z_1,\ldots,Z_m\}$ de cardinal $m$, et
-vérifiant la propriété ($\dagger$) de la question précédente. Plus
-précisément, on pourra montrer que le nombre de tels arbres est donné
-par $N(k,m)$ défini par la récurrence $N(k,m) = m \, \sum_{r=0}^k
-N(k,m-1)^r$ en considérant l'étiquette de la racine (parmi $m$
+valence $\leq k$ (ceci signifie que chaque sommet a au plus $k$ fils),
+dont les sommets sont étiquetés par des étiquettes prises dans un
+ensemble $\{Z_1,\ldots,Z_m\}$ de cardinal $m$, et vérifiant la
+propriété ($\dagger$) de la question précédente. Plus précisément, on
+pourra montrer que le nombre de tels arbres est donné par $N(k,m)$
+défini par la récurrence $N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$ (et
+$N(k,0) = 0$) en considérant l'étiquette de la racine (parmi $m$
possibles) et les $r \leq k$ sous-arbres qui partent de ses fils.
\begin{corrige}
@@ -542,9 +545,9 @@ $N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$.
\textit{Indication}\quad Si $k$ est la longueur maximale d'une
production de la grammaire $G$, on pourra chercher à construire tous
les arbres (finis enracinés ordonnés) de valence $\leq k$, étiquetés
-par des terminaux ou nonterminaux ou $\varepsilon$, et vérifiant la
-propriété ($\dagger$), et regarder s'il y a un arbre d'analyse parmi
-eux.
+par des terminaux ou nonterminaux ou $\varepsilon$, vérifiant de plus
+la propriété ($\dagger$), et regarder s'il y a un arbre d'analyse
+parmi eux.
\begin{corrige}
Si $k$ est la longueur maximale d'une production de la grammaire $G$
@@ -557,9 +560,10 @@ effectif avec la récursion évidente sur $m$). Il suffit ensuite de
tester tous ces arbres concevables et de vérifie si, à chaque nœud,
les contraintes imposées à un arbre d'analyse sont vérifiées. Soit on
trouve un arbre d'analyse pour $G$, auquel cas on a montré $L(G) \neq
-\varnothing$, soit il n'y a aucun arbre d'analyse pour $G$
-vérifiant ($\dagger$), donc aucun d'arbre d'analyse pour $G$ d'après
-la question (2), donc $L(G) = \varnothing$ d'après (1).
+\varnothing$ et on peut répondre « vrai » ; soit il n'y a aucun arbre
+d'analyse pour $G$ vérifiant ($\dagger$), donc aucun d'arbre d'analyse
+pour $G$ d'après la question (2), donc $L(G) = \varnothing$
+d'après (1) et on peut répondre « faux ».
\end{corrige}
\medbreak
--
cgit v1.2.3