diff options
Diffstat (limited to 'controle-20230615.tex')
| -rw-r--r-- | controle-20230615.tex | 870 |
1 files changed, 870 insertions, 0 deletions
diff --git a/controle-20230615.tex b/controle-20230615.tex new file mode 100644 index 0000000..d9bc00d --- /dev/null +++ b/controle-20230615.tex @@ -0,0 +1,870 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\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 connaissances — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{15 juin 2023} +\maketitle + +\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} et \emph{approximatif} : exercice 1 : +(a) $1.5$, (b) $1.5$, (c) $1$, (d) $4$, (e) $3$, (f) $3$ (soit au +total $14$) ; exercice 2 : (a) $1$, (b) $2$, (c) $1$, (d) $2$ (soit au +total $6$). + +\ifcorrige +Ce corrigé comporte 8 pages (page de garde incluse). +\else +Cet énoncé comporte 4 pages (page de garde incluse). +\fi + +\vfill + +{\tiny\noindent +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On considère les huit +automates suivants +($A_{\mathrm{s}},A_{\mathrm{t}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{w}},A_{\mathrm{x}},A_{\mathrm{y}},A_{\mathrm{z}}$) +sur l'alphabet $\Sigma$ : + +\begin{center} +\begin{tabular}{|c|c|} +\hline +$A_{\mathrm{s}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{t}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{u}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{v}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{w}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0); +\draw[->] (q1) to[loop above] node[auto]{$a,b$} (q1); +\draw[->] (q2) to[loop above] node[auto]{$a,b$} (q2); +\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3); +\draw[->] (q4) to[loop above] node[auto]{$a,b$} (q4); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{x}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting below] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting below] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting below] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting below] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting below] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting below] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{y}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,initial above] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,initial above] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,initial above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,initial above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,initial above,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{z}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial above,accepting below] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,initial above,accepting below] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,initial above,accepting below] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,initial above,accepting below] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,initial above,accepting below] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,initial above,accepting below] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +\end{tabular} +\end{center} + +On définit aussi les douze langages suivants, où $w_0$ désigne le +mot $ababb$ : +\begin{itemize} +\item $L_0 = \varnothing$ : le langage vide. +\item $L_1 = \{w_0\}$ : le langage constitué du seul mot $w_0$. +\item $L_2$ : le langage constitué des mots qui sont un sous-mot de + $w_0$. +\item $L_3$ : le langage constitué des mots qui ont $w_0$ comme + sous-mot. +\item $L_4$ : le langage constitué des mots qui sont un facteur de + $w_0$. +\item $L_5$ : le langage constitué des mots qui ont $w_0$ comme + facteur. +\item $L_6$ : le langage constitué des mots qui sont un préfixe de + $w_0$. +\item $L_7$ : le langage constitué des mots qui ont $w_0$ comme + préfixe. +\item $L_8$ : le langage constitué des mots qui sont un suffixe de + $w_0$. +\item $L_9$ : le langage constitué des mots qui ont $w_0$ comme + suffixe. +\item $L_{10} = \{w_0^i : i\in\mathbb{N}\}$ : le langage constitué des + mots qui sont une répétition d'un nombre quelconque ($i$) de copies + de $w_0$ (par exemple, $ababbababb$). +\item $L_{11} = \{b^i w_0 a^i : i\in\mathbb{N}\}$ : le langage + constitué des mots obtenus en précédant $w_0$ d'un nombre + quelconque ($i$) de copies de la lettre $b$ et en le suivant du même + nombre de copies de la lettre $a$ (par exemple, $bbababbaa$). +\end{itemize} + +\textbf{(a)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire lequel ou +lesquels parmi les douze langages $L_0,\ldots,L_{11}$ est celui +reconnu par l'automate $A$. On ne demande pas de justifier la +réponse. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ reconnaît le langage $L_1 = \{w_0\}$. + +L'automate $A_{\mathrm{t}}$ reconnaît le langage $L_9$ des mots ayant +$w_0$ comme suffixe (car un chemin dans $A_{\mathrm{t}}$ finit par un +chemin consommant $w_0$). + +L'automate $A_{\mathrm{u}}$ reconnaît le langage $L_7$ des mots ayant +$w_0$ comme préfixe (car un chemin dans $A_{\mathrm{u}}$ commence +par un chemin consommant $w_0$). + +L'automate $A_{\mathrm{v}}$ reconnaît le langage $L_5$ des mots ayant +$w_0$ comme facteur (car un chemin dans $A_{\mathrm{u}}$ passe par un +chemin consommant $w_0$). + +L'automate $A_{\mathrm{w}}$ reconnaît le langage $L_3$ des mots ayant +$w_0$ comme sous-mot (car un chemin dans $A_{\mathrm{u}}$ consomme les +lettres $a,b,a,b,b$ dans cet ordre, intercalées par un nombre +quelconque de lettres quelconques). + +L'automate $A_{\mathrm{x}}$ reconnaît le langage $L_6$ des préfixes +de $w_0$ (car un chemin dans $A_{\mathrm{x}}$ consomme le début +de $w_0$). + +L'automate $A_{\mathrm{y}}$ reconnaît le langage $L_8$ des suffixes +de $w_0$ (car un chemin dans $A_{\mathrm{y}}$ consomme la fin +de $w_0$). + +L'automate $A_{\mathrm{z}}$ reconnaît le langage $L_4$ des facteurs +de $w_0$ (car un chemin dans $A_{\mathrm{z}}$ consomme un intervalle +de lettres consécutives de $w_0$). + +(Les justifications entre parenthèses n'étaient pas demandées.) +\end{corrige} + +\textbf{(b)} Pour chacun des sept automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}\}$ (cette question-ci n'est pas posée +pour $A_{\mathrm{z}}$), donner une expression rationnelle dénotant le +langage $L$ reconnu par $A$. On ne demande pas de justifier la +réponse, et il n'est pas obligatoire d'appliquer un algorithme vu en +cours. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ reconnaît le langage dénoté par $ababb$. + +L'automate $A_{\mathrm{t}}$ reconnaît le langage dénoté +par $(a|b){*}ababb$. + +L'automate $A_{\mathrm{u}}$ reconnaît le langage dénoté +par $ababb(a|b){*}$. + +L'automate $A_{\mathrm{v}}$ reconnaît le langage dénoté +par $(a|b){*}ababb(a|b){*}$. + +L'automate $A_{\mathrm{w}}$ reconnaît le langage dénoté +par $(a|b){*}a(a|b){*}b(a|b){*}a(a|b){*}b(a|b){*}b(a|b){*}$. + +L'automate $A_{\mathrm{x}}$ reconnaît le langage dénoté +par $\underline{\varepsilon}|a|ab|aba|abab|ababb$ (simple énumération +de tous les préfixes de $w_0$) ou, si on préfère, par +$\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|b))))$ +(obtenue en éliminant les états de $A_{\mathrm{x}}$ dans +l'ordre $5,4,3,2,1,0$). + +L'automate $A_{\mathrm{y}}$ reconnaît le langage dénoté +par $\underline{\varepsilon}|b|bb|abb|babb|ababb$ (simple énumération +de tous les suffixes de $w_0$) ou, si on préfère, par +$\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|a)b)a)b)b$ +(obtenue en éliminant les états de $A_{\mathrm{y}}$ dans +l'ordre $0,1,2,3,4,5$). +\end{corrige} + +\textbf{(c)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire de quel type +d'automate vu en cours (DFA complet, DFA à spécification incomplète, +NFA ou bien NFA à transitions spontanées) est l'automate $A$. On +donnera à chaque fois le type le plus particulier applicable. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{t}}$ est un NFA (à cause de la double +transition étiquetée $a$ depuis l'état $0$). + +L'automate $A_{\mathrm{u}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{v}}$ est un NFA. + +L'automate $A_{\mathrm{w}}$ est un NFA. + +L'automate $A_{\mathrm{x}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{y}}$ est un NFA (à cause des multiples états +initiaux). + +L'automate $A_{\mathrm{z}}$ est un NFA. +\end{corrige} + +\textbf{(d)} Pour chacun des cinq automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{x}}, A_{\mathrm{z}}\}$ +(cette question-ci n'est pas posée pour $A_{\mathrm{t}}, +A_{\mathrm{w}}, A_{\mathrm{y}}$), donner un DFA complet sans état +inaccessible qui soit équivalent à $A$ (c'est-à-dire, reconnaissant le +langage $L$). On appliquera un algorithme vu en cours en le nommant. + +{\footnotesize Conseil sur la présentation graphique : pour s'éviter + des maux de tête dans le placement des états (et en éviter aussi au + correcteur), il est conseillé de commencer par placer + horizontalement de gauche à droite les états successifs rencontrés + lors de la consommation du mot $w_0 = ababb$ par l'automate + construit, et d'ajouter ensuite les autres états éventuellement + nécessaires.\par} + +\begin{corrige} +S'agissant de $A_{\mathrm{s}}$, comme c'est un DFAi, il s'agit +simplement de lui ajouter un état « puits », noté $\bot$ ci-dessous, +où aboutissent toutes les transitions manquantes : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax +La construction est analogue pour $A_{\mathrm{u}}$ : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax S'agissant de $A_{\mathrm{v}}$, on a affaire à +un « vrai » non-déterminisme et on applique donc l'algorithme de +déterminisation vu en cours, qui donne (en omettant les accolades dans +le nommage des états) : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {\small $0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {\small $0,1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {\small $0,2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {\small $0,1,3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {\small $0,2,4$}; +\node (q5) at (300bp,-45bp) [draw,circle,state,final] {\small $0,5$}; +\node (q1X) at (30bp,-90bp) [draw,circle,state,accepting below] {\small $0,1,5$}; +\node (q2X) at (110bp,-90bp) [draw,circle,state,accepting below] {\small $0,2,5$}; +\node (q3X) at (190bp,-90bp) [draw,circle,state,accepting below] {\small $0,1,3,5$}; +\node (q4X) at (270bp,-90bp) [draw,circle,state,accepting below] {\small $0,2,4,5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop below] node[auto]{$b$} (q0); +\draw[->] (q1) to[loop below] node[auto]{$a$} (q1); +\draw[->] (q2) to[out=120,in=60] node[auto,swap]{$b$} (q0); +\draw[->] (q3) to[out=120,in=60] node[auto,swap]{$a$} (q1); +\draw[->] (q4) to[out=120,in=60] node[auto,swap]{$a$} (q3); +\draw[->] (q5) to[loop above] node[auto]{$b$} (q5); +\draw[->] (q5) to[out=165,in=45] node[auto,swap,near end]{$a$} (q1X); +\draw[->] (q1X) -- node[auto]{$b$} (q2X); +\draw[->] (q2X) -- node[auto]{$a$} (q3X); +\draw[->] (q3X) -- node[auto]{$b$} (q4X); +\draw[->] (q4X) -- node[auto,swap]{$b$} (q5); +\draw[->] (q1X) to[loop left] node[auto]{$a$} (q1X); +\draw[->] (q2X) to[out=45,in=195] node[auto]{$b$} (q5); +\draw[->] (q3X) to[out=240,in=300] node[auto]{$a$} (q1X); +\draw[->] (q4X) to[out=240,in=300] node[auto]{$a$} (q3X); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax {\footnotesize\textbf{Note:} Une version + précédente de ce corrigé donnait un automate certes correct (DFA + complet sans état inaccessible qui soit équivalent à $A$) mais qui + n'est pas celui, représenté ci-dessus, obtenu en appliquant + l'algorithme de déterminisation. (L'automate qui était représenté + était, en fait, l'automate minimal obtenu en identifiant tous les + états contenant $5$ dans celui ci-dessus.)\par} +La construction pour $A_{\mathrm{x}}$ est exactement comme pour +$A_{\mathrm{s}}$ sauf que les états $0$ à $5$ sont tous marqués +finaux : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax +S'agissant de $A_{\mathrm{z}}$, on a de nouveau affaire à un « vrai » +non-déterminisme et on applique donc l'algorithme de déterminisation +vu en cours, qui donne (en omettant les accolades dans le nommage des +états) : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)] +\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2,4$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (q245) at (120bp,-120bp) [draw,circle,state,accepting below] {\small $2,4,5$}; +\node (qbot) at (300bp,-90bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (qI) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (qI) to[out=270,in=150] node[auto,swap]{$b$} (q245); +\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot); +\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5); +\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto,near start]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (q245) to[out=60,in=240] node[auto]{$a$} (q3); +\draw[->] (q245) to[out=30,in=240] node[auto,swap,very near end]{$b$} (q5); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +où on a noté $I$ au lieu de $\{0,1,2,3,4,5\}$. +\end{corrige} + +\textbf{(e)} Pour $A = A_{\mathrm{z}}$ (et seulement celui-ci), +minimiser le DFA trouvé à la question (d). + +\begin{corrige} +On a affaire à un DFA complet sans état inaccessible : on va le +minimiser avec l'algorithme de Moore. + +Dans une première étape, on fait deux classes d'état : celle des états +finaux, c'est-à-dire $I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ +et celle des états non-finaux, c'est-à-dire le seul +état $\varnothing$. + +Séparons maintenant les états selon la cible de la transition +étiquetée par $a$ : la classe formée de +$I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ se scinde en deux : +$I,\{2,4\},\{2,4,5\}$ d'une part, où elle mène à un état final, et +$\{1,3\},\{3\},\{4\},\{5\}$ d'autre part, où elle mène à un état +non-final. La cible de la transition étiquetée par $b$, pour sa part, +sépare $\{5\}$ de tous les autres états (le seul où elle mène à un +état non-final). À ce stade, on a quatre classes : la classe formée +de $I,\{2,4\},\{2,4,5\}$, celle de $\{1,3\},\{3\},\{4\}$, et deux +classes singleton, $\{5\}$ et $\varnothing$. + +À l'étape suivante, la cible de la transition étiquetée par $a$ ne +sépare rien (les états de la première classe mènent à la seconde et +les états de la seconde mènent au puits). La cible de la transition +étiquetée par $b$, en revanche, sépare la classe formée de +$I,\{2,4\},\{2,4,5\}$ en $I$ d'une part (qui mène à cette même classe) +et $\{2,4\},\{2,4,5\}$ de l'autre (qui mène à $\{5\}$) ; et elle +sépare la classe formée de $\{1,3\},\{3\},\{4\}$ en trois (puisque les +cibles sont dans trois classes distinctes). À ce stade, les seuls +états qui n'ont pas été séparés sont $\{2,4\}$ et $\{2,4,5\}$. Or +comme ils ont exactement les mêmes cibles de transitions étiquetées +par $a$ et $b$, ils ne sont pas séparés, donc l'algorithme s'applique +ici : il fusionne exactement deux états, à savoir +$\{2,4\}$ et $\{2,4,5\}$, en un seul, que nous noterons $B$ : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)] +\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$B$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (qI) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (qI) to[out=60,in=120] node[auto]{$b$} (q2); +\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot); +\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5); +\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +\textbf{(f)} Parmi les douze langages $L_0,\ldots,L_{11}$, lesquels +sont rationnels ? Lesquels sont algébriques ? Lesquels sont +décidables ? Lesquels sont semi-décidables ? On justifiera la +réponse à chaque fois (par exemple en donnant une expression +rationnelle, un automate, une grammaire hors-contexte, un algorithme, +ou n'importe quel autre type d'argument permettant de conclure). + +\begin{corrige} +Les langages $L_1,L_3,L_4,L_5,L_6,L_7,L_8,L_9$ sont rationnels car ils +sont reconnaissables : on a vu que les automates $A_{\mathrm{s}}, +A_{\mathrm{w}}, A_{\mathrm{z}}, A_{\mathrm{v}}, A_{\mathrm{x}}, +A_{\mathrm{u}}, A_{\mathrm{y}}, A_{\mathrm{t}}$ respectivement les +reconnaissent. Il reste donc à traiter le cas de +$L_0,L_2,L_{10},L_{11}$. + +Les langages $L_0$ et $L_2$ sont rationnels car ils sont finis (on +peut donner des expressions rationnelles pour les deux, à savoir +$\bot$ pour $L_0$ et, en énumérant systématiquement tous les +sous-mots, $\varepsilon | b | bb | a | ab | abb | bbb | ba | bab | +babb | aa | aab | aabb | abbb | aba | abab | ababb$ pour $L_2$, mais +ce n'est pas très intéressant et ce n'était pas demandé). + +Le langage $L_{10} = \{w_0^i : i\in\mathbb{N}\} = L_1^*$ est rationnel +car il est l'étoile de Kleene d'un langage rationnel (si on préfère, +il est dénoté par l'expression rationnelle $(ababb){*}$). + +Tous les langages $L_0$ à $L_{10}$ sont donc rationnels, et, en +particulier, algébriques, décidables et semi-décidables. + +Reste à évoquer le cas du langage $L_{11} = \{b^i w_0 a^i : +i\in\mathbb{N}\}$. Montrons qu'il n'est pas rationnel, et montrons +qu'il est algébrique. + +Il n'est pas rationnel par le lemme de pompage. En effet, supposons +par l'absurde que $\{b^i w_0 a^i : i\in\mathbb{N}\}$ soit rationnel, +et soit $k$ tel que donné par le lemme de pompage. Considérons le mot +$t := b^k ababb a^k \in L_{11}$. D'après la propriété de $k$, il +existe une factorisation $t = uvw$ vérifiant les propriétés garanties +par le lemme de pompage. Le fait que $|uv|\leq k$, comme le préfixe +de longueur $k$ de $t$ est formé uniquement de la lettre $b$, assure +que $u = b^{\ell_1}$ et $v = b^{\ell_2}$ pour certains $\ell_1,\ell_2$ +avec, de plus, $\ell_2 > 0$ (car $v\neq\varepsilon$) et +$\ell_1+\ell_2\leq k$. On a alors $w = b^{k-\ell_1-\ell_2} ababb +a^k$, et $uv^iw = b^{k+(i-1)\ell_2} ababb a^k$. Comme les mots de +$L_{11}$ ont la propriété nécessaire que leur nombre initial de $b$ +(i.e., la longueur de leur plus long préfixe formé uniquement de la +lettre $b$) est égale à leur nombre final de $a$ (i.e., la longueur de +leur plus long suffixe formé uniquement de la lettre $a$), on devrait +avoir $k+(i-1)\ell_2 = k$, ce qui est une contradiction dès que $i\neq +1$. + +En revanche, le langage $L_{11}$ est algébrique, car il est engendré +par la grammaire suivante d'axiome $S$ : +\[ +S \rightarrow ababb \;|\; bSa +\] +Étant algébrique, le langage $L_{11}$ est décidable et semi-décidable. +(Au demeurant, il est facile de donner un algorithme qui décide si un +mot appartient à $L_{11}$ : on vérifie que son nombre initial de $b$ +est égal à son nombre final de $a$ et, une fois ce fait vérifié, on +vérifie qu'une fois retiré le préfixe et le suffixe en question il +reste exactement le mot $ababb$.) + +Pour résumer, tous les langages dont on a parlé sont algébriques, +décidables et semi-décidables, et tous sauf $L_{11}$ sont rationnels. +\end{corrige} + + +% +% +% + +\exercice + +{\footnotesize Dans cet exercice, les questions (1) et (2) sont + indépendantes, et la question (4) ne dépend que de la + question (2).\par} + +\textbf{(1)} La fonction $h\colon \mathbb{N} \to \mathbb{N}$ suivante +est-elle calculable ? +\[ +h(0) = 1\;\;,\;\; +h(1) = 10\;\;,\;\; +h(2) = 10^{10}\;\;,\;\; +h(3) = 10^{10^{\scriptstyle 10}}\;\;,\;\; +h(4) = 10^{10^{\scriptstyle 10^{\scriptstyle 10}}}\;\;,\;\; +\] +\[ +\left.\begin{matrix} h(n) = 10^{\scriptstyle 10^{\scriptstyle \cdots^{\scriptstyle 10}}}\end{matrix}\right\} n +\] +(Autrement dit, $h(n)$ est une tour d'exponentielle de hauteur $n$ sur +le nombre $10$. Bien sûr, $10^{10^{\scriptstyle 10}}$ se comprend +comme $10^{\big(10^{\scriptstyle 10}\big)}$.) + +\begin{corrige} +La fonction $g\colon n\mapsto 10^n$ est calculable : en effet, on peut +exécuter une boucle à $n$ itérations en multipliant par $10$ la valeur +d'une variable en partant de $1$. On en déduit que la fonction $h$ +est calculable : en effet, on peut exécuter une boucle à $n$ +itérations en appliquant la fonction $g$ à une variable en partant +de $1$. +\end{corrige} + +\medskip + +Fixons maintenant une numérotation (« codage de Gödel ») des +algorithmes prenant en entrée un entier et renvoyant un entier, et +appelons $\varphi_e(n)$ le résultat de l'exécution du programme codé +par l'entier $e$ sur l'entrée $n$, si cette exécution termine (et +$\varphi_e(n)$ non défini si cette exécution ne termine pas). +Considérons la fonction $b\colon \mathbb{N} \to \mathbb{N}$ suivante : +\[ +b(n) = \max\{\varphi_e(n) : 0\leq e\leq n +\text{~et~}\varphi_e(n)\text{~défini}\} +\] +(Autrement dit, $b(n)$ est la plus grande des valeurs $\varphi_e(n)$ +qui sont définies lorsque $e$ parcourt les entiers de $0$ à $n$.) + +\textbf{(2)} On veut montrer que pour toute fonction calculable +$f\colon \mathbb{N} \to \mathbb{N}$, il existe un $n_0$ tel que pour +tout $n\geq n_0$ on ait $b(n) > f(n)$. Supposons donc $f\colon +\mathbb{N} \to \mathbb{N}$ calculable.\quad\textbf{(a)} Expliquer +pourquoi il existe $p$ tel que $\varphi_p = f+1$ (c'est-à-dire +$\varphi_p(n) = f(n)+1$ pour tout $n$).\quad\textbf{(b)} En déduire +que $b(n) > f(n)$ lorsque $n\geq p$, et conclure. + +\begin{corrige} +\textbf{(a)} La fonction $n \mapsto f(n)+1$ est calculable puisque $f$ +l'est et que l'addition l'est. Il existe donc un algorithme qui la +calcule, c'est-à-dire un $p$ tel que $\varphi_p = f+1$. + +\textbf{(b)} Sachant que $\varphi_p = f+1$, si $n \geq p$, la valeur +$b(n)$ est le maximum des valeurs $\varphi_e(n)$ qui sont définies +lorsque $e$ et $n$ parcourent les entiers de $0$ à $n$. En +particulier, puisque $0\leq p\leq n$, parmi ces entiers se trouve la +valeur $\varphi_p(n) = f(n)+1$ (qui est bien définie car $f$ est une +fonction totale ici). On a donc $b(n) \geq \varphi_p(n) = f(n)+1 > +f(n)$. On a bien montré que si $n \geq p$ alors $b(n) > f(n)$, ce qui +était voulu (pour $n_0 = p$). +\end{corrige} + +\textbf{(3)} Montrer que (pour les fonctions $h$ et $b$ introduites +ci-dessus) : +\[ +\lim_{n\to+\infty} \frac{b(n)}{h(n)} = +\infty +\] + +\begin{corrige} +On souhaite montrer que pour tout $C>0$ il existe $n_0$ tel que si +$n\geq n_0$ alors $\frac{b(n)}{h(n)} > C$. Pour cela, soit $C$ un +réel $>0$, et, quitte à l'augmenter encore un peu, on peut supposer +$C$ entier. La fonction $C\cdot h$ (c'est-à-dire $n \mapsto C\cdot +h(n)$) est calculable car $h$ l'est (question (1)) et que la +multiplication l'est. D'après la question (2), il existe $n_0$ tel +que pour tout $n\geq n_0$ on ait $b(n) > C\cdot h(n)$ : c'est ce qu'on +voulait montrer. +\end{corrige} + +\textbf{(4)} On se propose ici de redémontrer l'indécidabilité du +problème de l'arrêt de manière légèrement différente de ce qui a été +vu en cours. Supposons donc par l'absurde que le problème de l'arrêt +$H = \{(e,n) : \varphi_e(n)\text{~défini}\}$ soit +décidable.\quad\textbf{(a)} Montrer soigneusement, sous cette +hypothèse, que $b$ est calculable.\quad\textbf{(b)} Conclure. + +\begin{corrige} +\textbf{(a)} Supposons par l'absurde qu'il existe un algorithme $T$ +qui décide le problème de l'arrêt : autrement dit, donnés $e$ et $n$, +cet algorithme est censé terminer en temps fini et répondre « oui » si +le programme codé par $e$ termine sur l'entrée $n$, « non » sinon. On +peut alors calculer $b(n)$ de la manière suivante : on démarre avec +$m=0$ et on effectue une boucle pour $e$ allant de $0$ à $n$, et pour +chacune des valeurs en question, on utilise $T$ pour savoir si +$\varphi_e(n)$ est défini, puis, \emph{si} c'est le cas, on caclcule +cette valeur $\varphi_e(n)$ au moyen de la machine universelle (ce +calcul termine en temps fini justement puisque $\varphi_e(n)$ est +défini), et on remplace la variable $m$ par $\max(m, \varphi_e(n))$. +À la fin de la boucle, on a bien calculé le max de toutes les valeurs +$\varphi_e(n)$ qui sont définies, c'est-à-dire $b(m)$. La fonction +$b$ est donc calculable (de nouveau, sous l'hypothèse que le problème +de l'arrêt l'est). + +\textbf{(b)} On a vu en (2) que pour toute fonction calculable $f$ il +existe un $n_0$ tel que pour tout $n\geq n_0$ on ait $b(n) > f(n)$. +Comme on vient de voir que (sous l'hypothèse que le problème de +l'arrêt est calculable) la fonction $b$ est calculable, en appliquant +ce résultat à $f = b$, il doit exister un $n_0$ tel que tout $n\geq +n_0$ on ait $b(n) > b(n)$, ce qui est absurde. C'est donc que +l'hypothèse était absurde : le problème de l'arrêt n'est pas +décidable. +\end{corrige} + + +% +% +% +\end{document} |