diff options
| -rw-r--r-- | controle-20180322.tex | 636 |
1 files changed, 636 insertions, 0 deletions
diff --git a/controle-20180322.tex b/controle-20180322.tex new file mode 100644 index 0000000..221991e --- /dev/null +++ b/controle-20180322.tex @@ -0,0 +1,636 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +\usepackage{hyperref} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +\newenvironment{commentaire}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}} +{{\hbox{}\nobreak\hfill\maltese}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% NOTE: compile dot files with +% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} +\ifcorrige +\title{INF105\\Contrôle de rattrapage — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de rattrapage\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{22 mars 2018} +\maketitle + +%% {\footnotesize +%% \immediate\write18{sh ./vc > vcline.tex} +%% \begin{center} +%% Git: \input{vcline.tex} +%% \end{center} +%% \immediate\write18{echo ' (stale)' >> vcline.tex} +%% \par} + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\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. + +\medbreak + +L'usage de tous les documents (notes de cours manuscrites ou +imprimées, feuilles d'exercices, livres) est autorisé. + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 1h30 + +Barème \emph{indicatif} : $7+8+5$ points. + +(La longueur de l'exercice 3 ne doit pas effrayer : les réponses +attendues sont plus courtes que les questions puisqu'il s'agit de lire +et de commenter des raisonnements déjà écrits.) + +\ifcorrige +Ce corrigé comporte 8 pages (page de garde incluse) +\else +Cet énoncé comporte 4 pages (page de garde incluse) +\fi + +\pagebreak + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b,c\}$. On appelle $L$ le +langage des mots sur $\Sigma$ qui ont $abc$ comme sous-mot, +c'est-à-dire, qui contiennent un $a$, un $b$ et un $c$ dans cet ordre +mais non nécessairement consécutivement (à titre d'exemple, $abac \in +L$). + +(1) Proposer un automate non-déterministe (NFA), sans transition +spontanée, $\mathscr{A}_1$ qui reconnaît le langage $L$. On +justifiera rapidement pourquoi l'automate proposé convient. + +\begin{corrige} +On peut proposer l'automate $\mathscr{A}_1$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3$}; +\draw [->] (q0) to[loop below] node[auto] {$a,b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,b,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b,c$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +Pour se convaincre qu'il convient, on remarque qu'un chemin de +l'unique état initial ($0$) à l'unique état final ($3$) dans cet +automate est formé par trois transitions $0\to 1$, $1\to 2$ et $2\to +3$, étiquetées par les lettres $a$, $b$ et $c$ respectivement, +intercalées d'un nombre quelconque de transitions d'un état vers +lui-même, étiquetées par une lettre quelconque : la lecture de ses +étiquettes donne bien un mot ayant $abc$ comme sous-mot ; et +réciproquement, tout tel mot étiquette un chemin de $0$ à $3$ (une +fois choisies les lettres $a,b,c$ dans l'ordre qui correspondront aux +transitions changeant d'état). + +\emph{Remarque :} il est correct de donner directement l'automate +déterministe $\mathscr{A}_2$ représenté ci-dessous (puisque tout DFA +est, en particulier, un NFA), à condition de justifier proprement +qu'il convient. +\end{corrige} + +(2) Déterminiser (si nécessaire) l'automate $\mathscr{A}_1$ trouvé +en (1) ; on appellera $\mathscr{A}_2$ l'automate résultant. + +\begin{corrige} +En notant $0':=\{0\}$, $1' := \{0,1\}$, $2' := \{0,1,2\}$ et $3' := +\{0,1,2,3\}$ les états de l'automate déterministe $\mathscr{A}_2$ qui +correspondent aux ensembles d'états de l'automate $\mathscr{A}_1$ +qu'on vient d'indiquer, la déterminisation conduit à l'automate +$\mathscr{A}_2$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$}; +\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3'$}; +\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(3) Minimiser (si nécessaire) l'automate $\mathscr{A}_2$ obtenu +en (2) ; on appellera $\mathscr{A}_3$ l'automate minimal (=canonique) +résultant. + +\begin{corrige} +On part bien d'un automate $\mathscr{A}_2$ déterministe complet sans +état inaccessible. La première étape de l'algorithme de minimisation +sépare deux classes d'états : $0',1',2'$ (non finaux) d'une part et +$3'$ (final) de l'autre. Ensuite on sépare $0',1'$ d'une part et $2'$ +de l'autre (car les premiers ne conduisent qu'à des états non finaux, +tandis que $2'$ conduit à un état final par la transition +étiquetée $c$). L'étape suivante sépare $0'$ et $1'$ (car le premier +ne conduit qu'à un état de la classe $\{0',1'\}$ de l'étape +précédente, tandis que $1'$ conduit à un état de la classe $\{2'\}$ +par la transition étiquetée $b$). On a donc séparé tous les états, ce +qui montre que $\mathscr{A}_3 = \mathscr{A}_2$ est minimal. + +\emph{Remarque :} on pouvait aussi invoquer l'argument suivant : +puisque le mot $abc$ doit être accepté et qu'aucun de ses sous-mots +stricts ne l'est (ce qui exclut qu'il y ait une boucle dans le chemin +d'acceptation), il faut au moins $|abc|+1 = 4$ états dans n'importe +quel automate reconnaissant $L$. Comme $\mathscr{A}_2$ a +effectivement $4$ états, il est forcément minimal. +\end{corrige} + +(4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M +:= \Sigma^*\setminus L$ complémentaire de $L$. + +\begin{corrige} +On obtient $\mathscr{A}_4$ en échangeant états finaux et non finaux +dans $\mathscr{A}_3 = \mathscr{A}_2$, c'est-à-dire l'automate +$\mathscr{A}_3$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state,final,accepting above] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state,final,accepting above] {$2'$}; +\node (q3) at (210bp,0bp) [draw,circle,state] {$3'$}; +\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(5) En appliquant à $\mathscr{A}_4$ la méthode d'élimination des +états, déterminer une expression rationnelle dénotant le langage $M$. +(Si on souhaite obtenir une expression plus compacte, il est +recommandé de commencer l'élimination des états par ceux qui sont +le plus loin de l'état initial.) + +\begin{corrige} +On va manipuler des automates finis à transitions étiquetées par des +expressions rationnelles (ou « RNFA »). Dans un premier temps, on +donne à l'automate un unique état final $F$ en faisant pointer vers +lui une transition spontanée (i.e., étiquetée +par $\underline{\varepsilon}$) depuis tout état qui était final, et un +unique état initial $I$ depuis lequel on fait partir une transition +spontanée vers $0'$. L'état $3'$ peut être éliminé d'emblée puisqu'il +est inutile (il n'est pas co-accessible : c'est un puits !). Par +ailleurs, deux transitions entre les mêmes états sont remplacées par +une seule étiquetée par la disjonction des étiquettes (par exemple, +les deux transitions $0'\to 0'$ étiquetées $b$ et $c$ sont remplacées +par une seule étiquetée $b|c$). On a donc affaire à l'automate +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a|b$} (q2); +\draw [->] (q2) -- node[auto] {$\underline{\varepsilon}$} (qF); +\draw [->] (q1) to[out=45,in=135] node[auto] {$\underline{\varepsilon}$} (qF); +\draw [->] (q0) to[out=90,in=180] (70bp,60bp) to node[auto] {$\underline{\varepsilon}$} (140bp,60bp) to[out=0,in=90] (qF); +\end{tikzpicture} +\end{center} +On élimine maintenant l'état $2'$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1); +\draw [->] (q1) -- node[auto] {$\underline{\varepsilon}|b(a|b){*}$} (qF); +\draw [->] (q0) to[out=90,in=180] (70bp,40bp) to node[auto] {$\underline{\varepsilon}$} (140bp,40bp) to[out=0,in=90] (qF); +\end{tikzpicture} +\end{center} +(on a fait usage du fait évident que l'expression rationnelle +$r\underline{\varepsilon}$ est équivalente à $r$). On élimine +ensuite l'état $1'$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$\underline{\varepsilon}|a(a|c){*}(\underline{\varepsilon}|b(a|b){*})$} (qF); +\end{tikzpicture} +\end{center} +Enfin, l'élimination de l'état $0'$ conduit au RNFA ayant seulement +deux états $I$ et $F$ reliés par une transition étiquetée par +\[ +(b|c){*}\Big(\underline{\varepsilon}|a(a|c){*}\big(\underline{\varepsilon}|b(a|b){*}\big)\Big) +\] +qui est l'expression rationnelle recherchée (dénotant $M$). + +L'élimination des états dans l'ordre $0',1',2'$ conduirait à +l'expression rationnelle moins compacte +\[ +\underline{\varepsilon}\;|\;(b|c){*}\;|\;(b|c){*}a(a|c){*}\;|\;(b|c){*}a(a|c){*}b(a|b){*} +\] +qui est cependant sans doute plus lisible. + +\emph{Remarque :} le langage $M$ est aussi dénoté par l'expression +rationnelle plus simple $(b|c){*}\,(a|c){*}\,(a|b){*}$, mais celle-ci +ne répond pas à la question car elle ne peut pas s'obtenir par +élimination des états à partir de $\mathscr{A}_4$. +\end{corrige} + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On appelle $L = L(G)$ +le langage défini par la grammaire hors-contexte $G$ d'axiome $S$ et de +nonterminaux $N = \{S\}$ sur l'alphabet $\Sigma$ donnée par +\[ +\begin{aligned} +S &\rightarrow aSbS \;|\; aS \;|\; \varepsilon\\ +\end{aligned} +\] + +Les questions de cet exercice sont essentiellement indépendantes, si +ce n'est que la question (6) fait appel à la conclusion (énoncée) des +questions (2) à (5). + +\smallskip + +(1) Donner deux arbres d'analyse (pour $G$) différents du mot $aab$. +Que peut-on dire de la grammaire $G$ ? + +\begin{corrige} +On peut proposer les arbres d'analyse suivants :\\ +% S<a.S<a.S<e.>>b.S<e.>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (42.500bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S1) at (30.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a1); +\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S2) -- (e0); +\node (b0) at (60.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (S3) at (80.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S3); +\node (e1) at (80.000bp,-50.000bp) [draw=none] {$\varepsilon$}; \draw (S3) -- (e1); +\end{tikzpicture} +d'une part,\hfill et +% S<a.S<a.S<e.>b.S<e.>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (25.000bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S1) at (50.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a1); +\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S2) -- (e0); +\node (b0) at (60.000bp,-60.000bp) [draw=none] {$b$}; \draw (S1) -- (b0); +\node (S3) at (80.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S3); +\node (e1) at (80.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S3) -- (e1); +\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} + +L'objet des questions suivantes est de montrer que $L$ n'est pas +rationnel. + +Soit $M$ le langage $\{a^i b^j : i,j\in\mathbb{N}\}$ constitué des +mots de la forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels +quelconques. + +(2) Donner une expression rationnelle qui dénote $M$. + +\begin{corrige} +Le langage $M$ est dénoté par l'expression rationnelle $a{*}b{*}$. +\end{corrige} + +Soit $P$ le langage $\{a^i b^j : i\geq j\}$ constitué des mots de la +forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels vérifiant $i\geq +j$ (autrement dit, les mots de $M$ qui ont au moins autant de $a$ que +de $b$). + +(3) Montrer que $P \subseteq L$. + +\begin{corrige} +Soient $i\geq j$ deux entiers naturels : on va expliquer comment +produire le mot $a^i b^j$ selon les règles de $G$. À partir de +l'axiome $S$, on commence par appliquer $i-j$ fois la règle $a +\rightarrow aS$, ce qui donne $a \Rightarrow aS \Rightarrow aaS +\Rightarrow \cdots \Rightarrow a^{i-j} S$. Appliquons maintenant $j$ +fois la règle $S\rightarrow aSbS$, suivie à chaque fois de +$S\rightarrow\varepsilon$ sur le $S$ de droite : on obtient ainsi +$a^{i-j} S \Rightarrow a^{i-j+1} S bS \Rightarrow a^{i-j+1} S b +\Rightarrow a^{i-j+2} S b S b \Rightarrow a^{i-j+2} S bb \Rightarrow +\cdots \Rightarrow a^i S b^j$. Il suffit de terminer par une +application de $S \rightarrow \varepsilon$ : on obtient ainsi une +dérivation $S \mathrel{\Rightarrow^*} a^i b^j$ qui prouve que $a^i b^j +\in L$. +\end{corrige} + +(4) Montrer que $L\cap M \subseteq P$. + +\begin{corrige} +Considérons la propriété « avoir (au total) au moins autant de $a$ que +de $b$ », ou si on veut $|\xi|_a\geq |\xi|_b$, sur un pseudo-mot $\xi$ +(un « pseudo-mot » signifiant, par définition, un mot sur $\Sigma\cup +N = \{a,b,S\}$). Cette propriété est vérifiée par le pseudo-mot $S$. +Elle est préservée si on remplace $S$ par $aSbS$ ou $aS$ ou +$\varepsilon$ puisque dans chacun de ces cas le nombre de $a$ augmente +d'au moins autant que le nombre de $b$. Elle est donc possédée par +tout pseudo-mot, et en particulier tout mot, qui dérive de $S$ +selon $G$. On vient donc de prouver que tout mot de $L$ a au moins +autant de $a$ que de $b$. Notamment, tout mot de $L\cap M$ est un mot +de la forme $a^i b^j$ (par définition de $M$), et qui vérifie $i\geq +j$ (c'est ce qu'on vient de prouver). Il est donc dans $P$. +\end{corrige} + +(5) Montrer que $P$ n'est pas rationnel. + +\begin{corrige} +Supposons par l'absurde que $P = \{a^i b^j : i\geq j\}$ soit +rationnel. Appliquons le lemme de pompage pour les langages +rationnels au langage $P$ : appelons $k$ l'entier dont le lemme de +pompage garantit l'existence. Considérons le mot $t := a^k b^k$ (qui +appartient bien à $P$ et est bien de longueur $\geq k$) : il doit +alors exister une factorisation $t = uvw$ (avec $u,v,w \in \Sigma^*$, +non nécessairement dans $P$) pour laquelle on a +(i) $|v|\geq 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in P$ pour +tout $i\geq 0$. La propriété (ii) assure que $uv$ est formé d'un +certain nombre de répétitions de la lettre $a$ (car tout préfixe de +longueur $\leq k$ de $a^k b^k$ est de cette forme) ; disons $u = +a^\ell$ et $v = a^m$, si bien que $w = a^{k-\ell-m} b^k$. La +propriété (i) donne $m\geq 1$. Enfin, la propriété (iii) affirme que +le mot $uv^iw = a^{k+(i-1)m} b^k$ appartient à $P$ ; or pour $i=0$, +ceci est faux puisque $a^{k-m} b^k$ vérifie $k-m < k$. On a donc +abouti à une contradiction, et c'est que $P$ n'est pas rationnel. +\end{corrige} + +(6) Déduire des questions (2) à (5) que $L$ n'est pas rationnel (on +explicitera très soigneusement le raisonnement). + +\begin{corrige} +On a vu à la question (3) que $P \subseteq L$ ; il est par ailleurs +trivial que $P \subseteq M$, et on a donc $P \subseteq L\cap M$. Mais +on a vu à la question (4) que $L\cap M \subseteq P$ : on a donc $L\cap +M = P$. Le langage $M$ est rationnel d'après la question (2). Si le +langage $L$ était lui aussi rationnel, le langage $L\cap M$ +(c'est-à-dire $P$) le serait car l'intersection de deux langages +rationnels est rationnelle. Or on a vu à la question (5) que $P$ +n'est pas rationnel. C'est donc que $L$ ne l'est pas. +\end{corrige} + + +% +% +% + +\exercice + +Dans cet exercice, on s'intéresse au langage $L$ formé des +programmes $e$ (codés, dans une formalisation quelconque de la +calculabilité\footnote{Par exemple, un langage de programmation + (Turing-complet) quelconque.}, comme des entiers naturels ou comme +des mots sur un alphabet fixé sans importance) qui, quel que soit le +paramètre $n$ qu'on leur fournit en entrée, terminent en temps fini et +retournent la valeur $0$ : soit $L = \{e : (\forall n) +{\varphi_e(n)\downarrow} = 0\}$. Si l'on préfère, $L$ est l'ensemble +de toutes les façons de coder la fonction constante égale à $0$. On +appellera aussi $M$ le complémentaire de $L$. On se demande si $L$ ou +$M$ sont semi-décidables. + +\smallskip + +(1) Thésée et Hippolyte se disputent pour savoir si $L$ est +semi-décidable. Thésée pense qu'il l'est, et il tient le raisonnement +suivant pour l'expliquer : + +{\narrower + +Pour savoir si un programme $e$ est dans l'ensemble $L$, il suffit de +l'examiner pour vérifier que toutes les instructions qui mettent fin +au programme renvoient la valeur $0$ : si c'est le cas, on termine en +répondait « oui » (c'est-à-dire $e\in L$) ; sinon, on rentre dans une +boucle infinie. Ceci fournit un algorithme qui semi-décide $L$. + +\par} + +\smallskip + +\noindent Hippolyte, elle, pense que $L$ n'est pas semi-décidable. Son +argument est le suivant : + +{\narrower + +Si $L$ était semi-décidable, je pourrais m'en servir pour résoudre le +problème de l'arrêt. En effet, donné un programme $e'$ et une +entrée $m$ sur laquelle je cherche à tester l'arrêt de $e'$, je peux +fabriquer le programme $e$ qui prend une entrée $n$, lance l'exécution +de $e'$ sur l'entrée $m$ pendant au plus $n$ étapes et à la fin +renvoie $1$ si ces $n$ étapes ont suffi à terminer l'exécution +de $e'$, et $0$ sinon. Dire que $e \in L$ signifie que $e'$ ne +termine jamais sur $m$, donc pouvoir semi-décider $L$ permet de +résoudre algorithmiquement le problème de l'arrêt, ce qui est +impossible. + +\par} + +\smallskip + +\noindent Qui a raison ? Expliquer précisément quelle est l'erreur +(ou les erreurs) commise(s) par le raisonnement incorrect, et +détailler les éventuels passages incomplets dans le raisonnement +correct. + +\begin{corrige} +C'est Hippolyte qui a raison ($L$ n'est pas semi-décidable). + +L'argument de Thésée est stupide : une instruction mettant fin au +programme avec une valeur autre que $0$ pourrait ne jamais être +atteinte, et réciproquement, même si toutes les instructions mettant +fin au programme renvoyaient $0$, il pourrait aussi ne jamais +terminer. (Au passage, l'argument de Thésée semblerait même montrer +que $L$ est décidable, pas juste semi-décidable.) + +L'argument d'Hippolyte, lui, est correct : il montre que si $L$ était +semi-décidable, le complémentaire du problème de l'arrêt (l'ensemble +des $e'$ qui ne terminent jamais) serait semi-décidable, ce qui n'est +pas le cas. (Le complémentaire du problème de l'arrêt n'est pas +semi-décidable, car s'il l'était, le problème de l'arrêt serait +décidable, vu qu'il est déjà semi-décidable.) Parmi les points qui +méritent éventuellement d'être précisés, on peut mentionner : le fait +que $e$ se déduise algorithmiquement de $e'$ et $m$ ; et le fait qu'il +est algorithmiquement possible de lancer l'exécution d'un programme +sur $n$ étapes (peu importe la définition exacte de « étape » tant que +chacune termine à coup sûr en temps fini) et tester si elle est bien +finie au bout de ce temps. +\end{corrige} + +\medskip + +(2) Achille et Patrocle se disputent pour savoir si $M$ (le +complémentaire de $L$) est semi-décidable. Achille pense qu'il l'est, +et il tient le raisonnement suivant pour l'expliquer : + +{\narrower + +Pour savoir si un programme $e$ est dans l'ensemble $M$, il suffit de +tester successivement les valeurs $\varphi_e(n)$ pour tous les $n$ +possibles : si l'on rencontre un $n$ tel que $\varphi_e(n)$ n'est +pas $0$, alors on termine en répondant « oui » (c'est-à-dire $e\in +M$) ; sinon, on ne va jamais terminer, et cela signifie que $e\not\in +M$. Ceci fournit un algorithme qui semi-décide $M$. + +\par} + +\smallskip + +\noindent Patrocle, lui, pense que $M$ n'est pas semi-décidable. Son +argument est le suivant : + +{\narrower + +Si $M$ était semi-décidable, je pourrais m'en servir pour résoudre le +problème de l'arrêt. En effet, donné un programme $e'$ et une +entrée $m$ sur laquelle je cherche à tester l'arrêt de $e'$, je peux +fabriquer le programme $e$ qui prend une entrée $n$, l'ignore purement +et simplement, exécute $e'$ sur l'entrée $m$ et à la fin renvoie $0$. +Dire que $e\in M$ signifie que $e'$ ne termine pas sur $m$, donc +pouvoir semi-décider $M$ permet de résoudre algorithmiquement le +problème de l'arrêt, ce qui est impossible. + +\par} + +\smallskip + +\noindent Qui a raison ? Expliquer précisément quelle est l'erreur +(ou les erreurs) commise(s) par le raisonnement incorrect, et +détailler les éventuels passages incomplets dans le raisonnement +correct. + +\begin{corrige} +C'est Patrocle qui a raison ($M$ n'est pas semi-décidable). + +Le raisonnement d'Achille se fonde sur l'idée que le complémentaire de +« l'ensemble des programmes qui renvoient toujours la valeur $0$ » est +« l'ensemble des programmes qui renvoient parfois une valeur autre +que $0$ », ce qui oublie la possibilité que le programme ne termine +pas. C'est là la principale erreur (le reste est globalement +correct). + +L'argument de Patrocle, lui, est correct : il montre que si $M$ était +semi-décidable, le complémentaire du problème de l'arrêt (l'ensemble +des $e'$ qui ne terminent jamais) serait semi-décidable, ce qui n'est +pas le cas. (Le complémentaire du problème de l'arrêt n'est pas +semi-décidable, car s'il l'était, le problème de l'arrêt serait +décidable, vu qu'il est déjà semi-décidable.) On fait appel à des +fonctions constantes, et qui ne peuvent renvoyer que $0$ ou ne pas +terminer, mais ce n'est pas spécialement problématique. Parmi les +points qui méritent éventuellement d'être précisés, on peut mentionner +le fait que $e$ se déduise algorithmiquement de $e'$ et $m$. +\end{corrige} + +% +% +% +\end{document} |