diff options
| -rw-r--r-- | controle-20220616.tex | 54 |
1 files 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 |