summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20200123.tex647
-rw-r--r--notes-inf105.tex300
2 files changed, 943 insertions, 4 deletions
diff --git a/controle-20200123.tex b/controle-20200123.tex
new file mode 100644
index 0000000..889a969
--- /dev/null
+++ b/controle-20200123.tex
@@ -0,0 +1,647 @@
+%% 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 connaissances — Corrigé\\{\normalsize Théorie des langages}}
+\else
+\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
+\fi
+\author{}
+\date{23 janvier 2020}
+\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.
+
+Dans l'exercice \ref{exercise-on-unary-languages}, les deux parties
+peuvent en principe être traitées indépendamment, mais la première
+donne un exemple aidant à comprendre la démarche de la seconde.
+
+\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} : 2+(7+6)+5.
+
+\ifcorrige
+Ce corrigé comporte 9 pages (page de garde incluse)
+\else
+Cet énoncé comporte 3 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
+
+Soit $\mathscr{A}$ l'automate fini suivant sur l'alphabet $\Sigma :=
+\{a,b,c\}$ :
+
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$};
+\draw [->] (S0) -- node[auto,near end] {$\varepsilon$} (S1);
+\draw [->] (S0) -- node[auto,below] {$\varepsilon$} (S2);
+\draw [->] (S1) to[out=225,in=135] node[auto,left] {$a$} (S2);
+\draw [->] (S2) to[out=45,in=315] node[auto,right] {$b$} (S1);
+\draw [->] (S2) to[loop below] node[auto] {$c$} (S2);
+\draw [->] (S1) -- node[auto] {$\varepsilon$} (S3);
+\draw [->] (S2) -- node[auto,below,near end] {$\varepsilon$} (S3);
+\end{tikzpicture}
+\end{center}
+
+\vskip-\baselineskip\vskip-.5ex\noindent En lui appliquant la méthode
+d'élimination des états, déterminer une expression rationnelle
+dénotant le langage qu'il reconnaît.
+
+\begin{corrige}
+L'élimination de l'état $1$ conduit à l'automate suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (S2) at (70bp,0bp) [draw,circle,state] {$2$};
+\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$};
+\draw [->] (S0) -- node[auto,below] {$\varepsilon|a$} (S2);
+\draw [->] (S2) to[loop below] node[auto] {$c|ba$} (S2);
+\draw [->] (S2) -- node[auto,below] {$\varepsilon|b$} (S3);
+\draw [->] (S0) to[out=90,in=180] (60bp,35bp) -- node[auto] {$\varepsilon$} (80bp,35bp) to[out=0,in=90] (S3);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-.5ex\noindent — et l'élimination de
+l'état $2$ conduit alors à l'expression rationnelle suivante :
+$\varepsilon\;|\;(\varepsilon|a)\,(c|ba){*}\,(\varepsilon|b)$ (il se
+trouve que le premier terme est inutile et que cette expression
+rationnelle est équivalente à
+simplement $(\varepsilon|a)\,(c|ba){*}\,(\varepsilon|b)$, mais la
+méthode d'élimination proprement menée conduit à ce qui a été dit).
+
+Si on élimine d'abord l'état $2$, on aboutit à l'automate suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (S1) at (70bp,0bp) [draw,circle,state] {$1$};
+\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$};
+\draw [->] (S0) -- node[auto,below] {$\varepsilon|c{*}b$} (S1);
+\draw [->] (S1) to[loop below] node[auto] {$ac{*}b$} (S1);
+\draw [->] (S1) -- node[auto,below] {$\varepsilon|ac{*}$} (S3);
+\draw [->] (S0) to[out=90,in=180] (60bp,35bp) -- node[auto] {$c{*}$} (80bp,35bp) to[out=0,in=90] (S3);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-.5ex\noindent — et à l'expression
+rationnelle suivante :
+$c{*}\;|\;(\varepsilon|c{*}b)\,(ac{*}b){*}\,(\varepsilon|ac{*})$.
+Elle est, bien sûr, équivalente à celle obtenue avec l'autre ordre
+d'élimination.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice\label{exercise-on-unary-languages}
+
+Dans cet exercice, on pose $\Sigma := \{a\}$ (alphabet à une seule
+lettre), de sorte que $\Sigma^* = \{a^n : n\in\mathbb{N}\}$ ; on va
+appliquer les automates finis à un problème arithmétique.
+
+\medskip
+
+\textbf{Première partie : étude d'un cas particulier.}
+
+\nobreak
+
+Dans cette partie, on considère l'expression rationnelle $r$
+suivante : $(aaa|aaaaa){*}$ (sur l'alphabet $\Sigma$). On appelle $L
+:= L(r)$ le langage qu'elle dénote et $M := \Sigma^* \setminus L$ son
+complémentaire.
+
+(1) Traiter l'une \emph{ou} l'autre des questions suivantes :
+(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ;
+(ii) construire l'automate de Thompson de $r$, puis éliminer les
+transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on
+retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$
+l'automate ainsi obtenu.
+
+(Dans les deux cas, on obtient le même automate $\mathscr{A}_1$, ayant
+$9$ états. À défaut de donner l'automate de Glushkov ou de Thompson,
+donner un NFA reconnaissant $L$ pourra apporter une partie des
+points.)
+
+\begin{corrige}
+L'automate $\mathscr{A}_1$ obtenu est le suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
+\node (S1) at (60bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (120bp,35bp) [draw,circle,state] {$2$};
+\node (S3) at (180bp,35bp) [draw,circle,state,final] {$3$};
+\node (S1p) at (60bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$1'$\hss}}\phantom{$1$}};
+\node (S2p) at (120bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$2'$\hss}}\phantom{$2$}};
+\node (S3p) at (180bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$3'$\hss}}\phantom{$3$}};
+\node (S4p) at (240bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$4'$\hss}}\phantom{$4$}};
+\node (S5p) at (300bp,-35bp) [draw,circle,state,final] {\vbox to0pt{\vss\hbox to0pt{$5'$\hss}}\phantom{$5$}};
+\draw [->] (S0) -- node[auto] {$a$} (S1);
+\draw [->] (S1) -- node[auto] {$a$} (S2);
+\draw [->] (S2) -- node[auto] {$a$} (S3);
+\draw [->] (S0) -- node[auto,below] {$a$} (S1p);
+\draw [->] (S1p) -- node[auto,below] {$a$} (S2p);
+\draw [->] (S2p) -- node[auto,below] {$a$} (S3p);
+\draw [->] (S3p) -- node[auto,below] {$a$} (S4p);
+\draw [->] (S4p) -- node[auto,below] {$a$} (S5p);
+\draw [->] (S3) -- node[auto,above,near end] {$a$} (S1p);
+\draw [->] (S5p) -- node[auto,below,very near end] {$a$} (S1);
+\draw [->] (S3) to[out=90,in=0] (130bp,70bp) -- node[auto,below] {$a$} (110bp,70bp) to[out=180,in=90] (S1);
+\draw [->] (S5p) to[out=210,in=0] (190bp,-70bp) -- node[auto,above] {$a$} (170bp,-70bp) to[out=180,in=330] (S1p);
+\end{tikzpicture}
+\end{center}
+C'est l'automate de Glushkov. Si on commence par construire
+l'automate de Thompson, celui-ci a $20$ états, et l'élimination des
+transitions spontanées conduit à l'automate $\mathscr{A}_1$ qu'on
+vient d'écrire.
+\end{corrige}
+
+(2) Déterminiser l'automate $\mathscr{A}_1$. On appellera
+$\mathscr{A}_2$ l'automate (déterministe complet) en question. (On
+obtient un automate $\mathscr{A}_2$ ayant $14$ états. On n'hésitera
+pas à introduire des notations allégées si on le juge utile ; il
+pourra être judicieux de réfléchir au préalable à une façon de nommer
+les états de $\mathscr{A}_1$ qui rend la construction
+de $\mathscr{A}_2$ plus facile à mener sans se tromper.)
+
+Pour simplifier les questions suivantes (ainsi que le travail du
+correcteur), on renommera si nécessaire les états de $\mathscr{A}_2$
+de façon que, autant que possible, l'état résultant de la lecture du
+mot $a^i$ par l'automate soit numéroté $i$.
+
+\begin{corrige}
+On travaille sur des ensembles d'états en suivant l'algorithme de
+déterminisation : partant de l'ensemble $\{0\}$ des états initiaux de
+l'automate $\mathscr{A}_1$, il n'y a à chaque fois qu'une seule
+transition (étiquetée par $a$) à considérer, ce qui construit
+successivement les états suivants (colonne du milieu de la table) :
+\begin{center}
+\begin{tabular}{c|l|c}
+$0$&$\{0\}$&F\\\hline
+$1$&$\{1,1'\}$&\\\hline
+$2$&$\{2,2'\}$&\\\hline
+$3$&$\{3,3'\}$&F\\\hline
+$4$&$\{1,1',4'\}$&\\\hline
+$5$&$\{2,2',5'\}$&F\\\hline
+$6$&$\{1,1',3,3'\}$&F\\\hline
+$7$&$\{1,1',2,2',4'\}$&\\\hline
+$8$&$\{2,2',3,3',5'\}$&F\\\hline
+$9$&$\{1,1',3,3',4'\}$&F\\\hline
+$10$&$\{1,1',2,2',4',5'\}$&F\\\hline
+$11$&$\{1,1',2,2',3,3',5'\}$&F\\\hline
+$12$&$\{1,1',2,2',3,3',4'\}$&F\\\hline
+$13$&$\{1,1',2,2',3,3',4',5'\}$&F\\
+\end{tabular}
+\end{center}
+Le procédé de calcul de la table est le suivant : à chaque ligne à
+partir de la deuxième, on incrémente tous les numéros avec et sans
+prime, sauf que $3$ ou $5'$ deviennent $1,1'$ (les deux à la fois,
+puisqu'il y a des transitions de $3$ et $5'$ vers $1$ et $1'$
+dans $\mathscr{A}_1$). Ceci permet de ne pas se tromper (d'où
+l'intérêt d'avoir judicieusement étiqueté les états
+de $\mathscr{A}_1$). L'unique transition de l'automate (évidemment
+étiquetée $a$) conduit de chaque ligne à la ligne suivante, sauf la
+dernière ligne qui boucle sur elle-même. Les états finaux sont ceux
+qui contiennent un des états finaux de $\mathscr{A}_1$, c'est-à-dire
+$0$ ou $3$ ou $5'$ (ou encore, les lignes qui précèdent une ligne
+avec $1,1'$), on les a marqués par un F dans la colonne de droite de
+la table ci-dessus.
+
+On peut bien sûr préférer tracer graphiquement l'automate comme
+d'habitude : c'est juste une ligne de $14$ états, toutes les
+transitions étant étiquetées $a$, menant de chaque état vers le
+suivant, sauf du dernier sur lui-même, certains états étant finaux
+comme on vient de le dire.
+
+On renumérote alors les états comme selon la colonne de gauche de la
+table, c'est-à-dire en suivant l'ordre des lignes. La transition
+étiquetée $a$ mène alors de l'état $i$ vers l'état $i+1$ sauf pour
+$i=13$ où elle mène vers lui-même. L'ensemble des états finaux est $F
+= \{0,3,5,6,8,9,10,11,12,13\}$ comme indiqué par la table.
+(Dans la notation introduite à la question (6) plus bas, l'automate
+$\mathscr{A}_2$ est décrit par $j_2 = 14$, $j_1 = 13$ et $F =
+\{0,3,5,6,8,9,10,11,12,13\}$.)
+\end{corrige}
+
+(3) Minimiser l'automate $\mathscr{A}_2$. On appellera
+$\mathscr{A}_3$ l'automate canonique ainsi obtenu.
+(On obtient un automate ayant $9$ états.)
+
+\begin{corrige}
+On a bien affaire pour commencer à un automate $\mathscr{A}_2$
+déterministe complet sans état inaccessible.
+
+L'algorithme de minimisation commence par partitionner l'ensemble
+$\{0,\ldots,13\}$ des états en deux classes, les finaux
+$\{0,3,5,6,8,9,10,11,12,13\}$ et les non-finaux $\{1,2,4,7\}$. Une
+première itération sépare les finaux en $\{5,8,9,10,11,12,13\}$ et
+$\{0,3,6\}$ (selon que l'état vers lequel aboutit l'unique transition
+est lui-même final ou non) et les non-finaux en $\{2,4,7\}$ et $\{1\}$
+(idem). La seconde itération sépare chacun de $0$, $2$ et $5$ des
+autres états de leur classe respective : les classes sont alors
+$\{0\}$, $\{1\}$, $\{2\}$, $\{3,6\}$, $\{4,7\}$ et
+$\{8,9,10,11,12,13\}$. La troisième itération sépare $4$ et $7$
+tandis que la quatrième sépare $3$ et $6$. Finalement, on obtient un
+automate $\mathscr{A}_3$ canonique ayant $9$ états : un pour chaque
+état de l'automate $\mathscr{A}_2$ entre $0$ et $7$ inclus, et un pour
+tous les états de $8$ à $13$ inclus.
+
+On pouvait aussi arguër de manière plus abstraite : il est clair que
+tous les états $8$ à $13$ devront être fusionnés puisqu'ils sont
+finaux et que leurs transitions arbitrairement itérées ne conduisent
+qu'à des états finaux, tandis que les états $0$ à $7$ inclus devront
+être tous séparés puisqu'ils sont distingués par le nombre de
+transitions à partir desquelles on n'arrive plus qu'à des états
+finaux.
+
+On peut bien sûr tracer graphiquement l'automate $\mathscr{A}_3$ comme
+d'habitude : c'est juste une ligne de $9$ états, toutes les
+transitions étant étiquetées $a$, menant de chaque état vers le
+suivant, sauf du dernier sur lui-même, les états finaux étant ceux
+numérotés $0,3,5,6,8$ si on numérote les états de $0$ à $8$ dans
+l'ordre des transitions. (Dans la notation introduite à la
+question (6) plus bas, l'automate $\mathscr{A}_3$ est décrit par
+$j_2 = 9$, $j_1 = 8$ et $F = \{0,3,5,6,8\}$.)
+\end{corrige}
+
+(4) Construire un automate fini déterministe complet $\mathscr{A}_4$
+reconnaissant le langage $M := \Sigma^*\setminus L$ complémentaire
+de $L$. Ce langage $M$ est fini : énumérer exhaustivement les mots
+qu'il contient.
+
+\begin{corrige}
+Il suffit d'échanger états finaux et non-finaux dans un automate
+déterministe complet quelconque reconnaissant $L$, disons l'automate
+$\mathscr{A}_3$ (on pouvait aussi utiliser $\mathscr{A}_2$ si on n'a
+pas réussi à calculer $\mathscr{A}_3$). On peut bien sûr tracer
+graphiquement l'automate $\mathscr{A}_4$ comme d'habitude : c'est
+juste une ligne de $9$ états, toutes les transitions étant
+étiquetées $a$, menant de chaque état vers le suivant, sauf du dernier
+sur lui-même, les états finaux étant ceux numérotés $1,2,4,7$ si on
+numérote les états de $0$ à $8$ dans l'ordre des transitions. (Dans
+la notation introduite à la question (6) plus bas, l'automate
+$\mathscr{A}_3$ est décrit par $j_2 = 9$, $j_1 = 8$ et $F =
+\{1,2,4,7\}$.)
+
+L'état $8$ (i.e., le dernier) étant un puits dans
+l'automate $\mathscr{A}_4$, les seuls mots acceptés le sont avant le
+puits, et ce sont les mots $a$, $aa$, $aaaa = a^4$ et $aaaaaaa = a^7$
+comme donnés par les états finaux de $\mathscr{A}_4$.
+\end{corrige}
+
+(5) En utilisant la question précédente, dire quels sont les (quatre)
+entiers naturels ne pouvant pas s'écrire sous la forme $3m+5m'$ avec
+$m,m'\in\mathbb{N}$.
+
+\begin{corrige}
+Si $n = 3m+5m'$ alors le mot $a^n = (aaa)^m(aaaaa)^{m'}$ appartient
+à $L$, c'est-à-dire qu'il vérifie $r$ puisqu'il est manifestement
+concaténation de mots de la forme $aaa$ ou $aaaaa$. Réciproquement,
+si le mot $a^n$ appartient à $L$, c'est-à-dire vérifie $r$, i.e.,
+concaténation de mots de la forme $aaa$ et de la forme $aaaaa$, disons
+$m$ de l'un et $m'$ de l'autre (en tout), il a pour longueur $n =
+3m+5m'$. Bref, les mots de $L$ sont exactement les $a^n$ avec $n$ de
+la forme $3m+5m'$ ; et les mots qui ne sont pas dans $L$ (i.e., sont
+dans $M$) sont exactement les $a^n$ avec $n$ ne pouvant pas s'écrire
+de la forme $3m+5m'$ : on a vu que ce sont $a$, $aa$, $aaaa = a^4$ et
+$aaaaaaa = a^7$. Ainsi, les quatre entiers naturels ne pouvant pas
+s'écrire sous la forme $3m+5m'$ avec $m,m'\in\mathbb{N}$ sont : $1$,
+$2$, $4$ et $7$.
+\end{corrige}
+
+\medbreak
+
+\textbf{Seconde partie : considérations générales.}
+
+\nobreak
+
+(6) Expliquer rapidement pourquoi un automate fini déterministe
+complet sans état inaccessible $\mathscr{A}$ sur $\Sigma = \{a\}$
+prend nécessairement la forme suivante : si on note $j_2$ son nombre
+d'états, on peut numéroter ces états de $0$ à $j_2-1$, avec $0$ l'état
+initial, et de façon qu'il y ait une unique transition étiquetée $a$
+de l'état $i$ vers l'état $i+1$ pour chaque $0\leq i<j_2-1$, ainsi
+qu'une transition étiquetée $a$ de l'état $j_2-1$ vers l'état $j_1$
+pour un certain $0\leq j_1<j_2$. Remarquer que l'automate
+$\mathscr{A}$ est alors complètement décrit par les entiers $0\leq
+j_1<j_2$ et par le sous-ensemble $F$ de $\{0,\ldots,j_2-1\}$ formé des
+états finaux.
+
+\begin{corrige}
+Appelons $q_0$ l'état initial de $\mathscr{A}$, et par récurrence
+sur $i$, posons $q_{i+1} = \delta(q_i,a)$ l'état vers lequel pointe la
+transition sortante depuis l'état $q_i$ étiquetée par la lettre $a$
+(cette transition étant unique puisqu'on a affaire à un automate
+déterministe complet) ; ou, pour dire les choses autrement, appelons
+$q_i = \delta^*(q_0, a^i)$ (pour tout $i\in \mathbb{N}$) l'état
+résultant de la lecture du mot $a^i$ par l'automate. L'automate
+$\mathscr{A}$ étant fini, les états $q_0,q_1,q_2,\ldots$ ne peuvent
+pas être tous distincts : il existe $j_1\neq j_2$ tels que $q_{j_1} =
+q_{j_2}$ ; appelons $j_2$ l'indice de la première répétition, i.e., le
+plus petit entier tel que $q_{j_2}$ coïncide avec un état $q_{j_1}$
+avec $0\leq j_1<j_2$. Alors (puisque $j_2$ est l'indice de la
+première répétition) les états $q_0,\ldots,q_{j_2-1}$ sont tous
+distincts. En nommant simplement $i$ l'état $q_i$ (pour $0\leq i<j_2$
+uniquement), on a, par construction, $\delta(i,a) = i+1$ pour $0\leq
+i<j_2-1$ tandis que $\delta(j_2-1,a) = j_1$, comme annoncé. De plus,
+les états $0,\ldots,j_2-1$ étant tous ceux qu'on peut atteindre en
+partant de $0$ et an suivant les transitions, ce sont tous les états
+de l'automate (car on l'a supposé sans état inaccessible), donc $j_2$
+est le nombre d'états, et l'automate a bien la forme demandée.
+
+(Les notations choisies sont censées rappeler la démonstration du
+lemme de pompage, qui utilise la même idée. Aussi dans le même ordre
+d'idées, il est utile pour la question suivante de remarquer que $q_i
+= q_{i+(j_2-j_1)}$ dès que $i\geq j_1$, et donc plus généralement $q_i
+= q_{i+k(j_2-j_1)}$ pour tout $k\in\mathbb{N}$.)
+\end{corrige}
+
+(7) Une fois un automate déterministe complet sur $\Sigma$ présenté
+comme décrit à la question (6), à quelle condition nécessaire et
+suffisante (sur $j_1,j_2,F$) le langage qu'il reconnaît est-il fini ?
+
+\begin{corrige}
+Les états $i$ tels que $j_1\leq i<j_2$ avec la notation introduite
+en (6) sont des états résultat de la lecture d'un nombre infini de
+mots distincts (à savoir $a^i$, $a^{i+(j_2-j_1)}$, et plus
+généralement $a^{i+k(j_2-j_1)}$ pour tout $k\in\mathbb{N}$). Si l'un
+quelconque de ces états est acceptant (=final), le langage reconnu par
+l'automate est infini. À l'inverse, si aucun de ces états n'est
+acceptant, le langage est fini et égal à $\{a^i : i\in F\}$.
+
+Bref, la condition nécessaire et suffisante de finitude du langage
+reconnu par $\mathscr{A}$ est que $F \cap \{j_1,\ldots,j_2-1\} =
+\varnothing$, et le cas échéant, le langage est constitué des $a^i$
+pour $i\in F$ (et $i<j_1$).
+\end{corrige}
+
+(8) Déduire de l'ensemble de cet exercice que le problème suivant est
+calculable algorithmiquement\footnote{Autrement dit, montrer qu'il
+ existe un algorithme qui, prenant en entrée $\ell_1,\ldots,\ell_r
+ \in \mathbb{N}$, termine toujours en temps fini et répond au
+ problème posé.} : donné des entiers naturels $\ell_1,\ldots,\ell_r
+\in \mathbb{N}$, décider si l'ensemble\footnote{Autrement dit, il
+ s'agit de l'ensemble $\mathbb{N} \setminus \{\ell_1 m_1 + \cdots +
+ \ell_r m_r : (m_1,\ldots,m_r)\in \mathbb{N}^r\}$ complémentaire de
+ l'image de $\mathbb{N}^r \to \mathbb{N},\penalty0\; (m_1,\ldots,m_r)
+ \mapsto \ell_1 m_1 + \cdots + \ell_r m_r$.} des entiers naturels qui
+ne peuvent pas s'écrire sous la forme $\ell_1 m_1 + \cdots + \ell_r
+m_r$ avec $m_1,\ldots,m_r \in \mathbb{N}$ est fini, et, le cas
+échéant, les énumérer.
+
+\begin{corrige}
+Il suffit d'appliquer la même méthode qui a été utilisée dans les
+questions précédentes : donnés $\ell_1,\ldots,\ell_r \in \mathbb{N}$,
+on fabrique l'expression rationnelle
+$(a^{\ell_1}|\cdots|a^{\ell_r}){*}$ sur $\Sigma$, on construit son
+automate de Glushkov (ou de Thompson dont on élimine ensuite les
+transitions spontanées), on le déterminise, on peut éventuellement le
+minimiser même si ce n'est pas nécessaire pour cette question, on
+échange états finaux et non-finaux pour obtenir un automate
+reconnaissant le langage complémentaire, et enfin on utilise le
+critère trouvé en (7) pour savoir si ce langage est fini et, le cas
+échéant, l'énumérer. Par le même raisonnement qu'en (5), ceci donne
+exactement les $a^n$ pour les $n$ qui ne peuvent pas s'écrire sous la
+forme $\ell_1 m_1 + \cdots + \ell_r m_r$ avec $m_1,\ldots,m_r \in
+\mathbb{N}$.
+
+\emph{Remarque :} En fait, il s'avère que l'ensemble $\mathbb{N}
+\setminus \{\ell_1 m_1 + \cdots + \ell_r m_r : (m_1,\ldots,m_r)\in
+\mathbb{N}^r\}$ est fini si et seulement si le pgcd de
+$\ell_1,\ldots,\ell_r$ vaut $1$ (i.e., si et seulement si ces nombres
+sont premiers entre eux dans leur ensemble), ce qui est aussi testable
+algorithmiquement ; mais ce n'était pas demandé ici, et ceci ne résout
+pas la question d'énumérer explicitement l'ensemble.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+On considère la grammaire hors-contexte $G$ d'axiome $S$ et de
+nonterminaux $N = \{S, T, U\}$ sur l'alphabet $\Sigma = \{a,b,c\}$
+donnée par
+\[
+\begin{aligned}
+S &\rightarrow T \;|\; TaS\\
+T &\rightarrow U \;|\; UbT\\
+U &\rightarrow c\\
+\end{aligned}
+\]
+(La grammaire en question est inambiguë : on ne demande pas de le
+démontrer.)
+
+(1) Donner les arbres d'analyse (= de dérivation) des mots suivants :
+$cacbcac$ et $cbcacbc$.
+
+\begin{corrige}
+On obtient les arbres d'analyse suivants :
+
+\hbox to\hsize{
+% S<T<U<c.>>a.S<T<U<c.>b.T<U<c.>>>a.S<T<U<c.>>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (37.778bp,0.000bp) [draw=none] {$S$};
+\node (T0) at (0.000bp,-30.000bp) [draw=none] {$T$}; \draw (S0) -- (T0);
+\node (U0) at (0.000bp,-50.000bp) [draw=none] {$U$}; \draw (T0) -- (U0);
+\node (c0) at (0.000bp,-70.000bp) [draw=none] {$c$}; \draw (U0) -- (c0);
+\node (a0) at (20.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0);
+\node (S1) at (93.333bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1);
+\node (T1) at (60.000bp,-60.000bp) [draw=none] {$T$}; \draw (S1) -- (T1);
+\node (U1) at (40.000bp,-90.000bp) [draw=none] {$U$}; \draw (T1) -- (U1);
+\node (c1) at (40.000bp,-110.000bp) [draw=none] {$c$}; \draw (U1) -- (c1);
+\node (b0) at (60.000bp,-90.000bp) [draw=none] {$b$}; \draw (T1) -- (b0);
+\node (T2) at (80.000bp,-90.000bp) [draw=none] {$T$}; \draw (T1) -- (T2);
+\node (U2) at (80.000bp,-110.000bp) [draw=none] {$U$}; \draw (T2) -- (U2);
+\node (c2) at (80.000bp,-130.000bp) [draw=none] {$c$}; \draw (U2) -- (c2);
+\node (a1) at (100.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a1);
+\node (S2) at (120.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2);
+\node (T3) at (120.000bp,-80.000bp) [draw=none] {$T$}; \draw (S2) -- (T3);
+\node (U3) at (120.000bp,-100.000bp) [draw=none] {$U$}; \draw (T3) -- (U3);
+\node (c3) at (120.000bp,-120.000bp) [draw=none] {$c$}; \draw (U3) -- (c3);
+\end{tikzpicture}
+\hss et\hss
+% S<T<U<c.>b.T<U<c.>>>a.S<T<U<c.>b.T<U<c.>>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (60.000bp,0.000bp) [draw=none] {$S$};
+\node (T0) at (20.000bp,-30.000bp) [draw=none] {$T$}; \draw (S0) -- (T0);
+\node (U0) at (0.000bp,-60.000bp) [draw=none] {$U$}; \draw (T0) -- (U0);
+\node (c0) at (0.000bp,-80.000bp) [draw=none] {$c$}; \draw (U0) -- (c0);
+\node (b0) at (20.000bp,-60.000bp) [draw=none] {$b$}; \draw (T0) -- (b0);
+\node (T1) at (40.000bp,-60.000bp) [draw=none] {$T$}; \draw (T0) -- (T1);
+\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$}; \draw (T1) -- (U1);
+\node (c1) at (40.000bp,-100.000bp) [draw=none] {$c$}; \draw (U1) -- (c1);
+\node (a0) at (60.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0);
+\node (S1) at (100.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1);
+\node (T2) at (100.000bp,-50.000bp) [draw=none] {$T$}; \draw (S1) -- (T2);
+\node (U2) at (80.000bp,-80.000bp) [draw=none] {$U$}; \draw (T2) -- (U2);
+\node (c2) at (80.000bp,-100.000bp) [draw=none] {$c$}; \draw (U2) -- (c2);
+\node (b1) at (100.000bp,-80.000bp) [draw=none] {$b$}; \draw (T2) -- (b1);
+\node (T3) at (120.000bp,-80.000bp) [draw=none] {$T$}; \draw (T2) -- (T3);
+\node (U3) at (120.000bp,-100.000bp) [draw=none] {$U$}; \draw (T3) -- (U3);
+\node (c3) at (120.000bp,-120.000bp) [draw=none] {$c$}; \draw (U3) -- (c3);
+\end{tikzpicture}
+}
+
+(On les trouve plus facilement si on se convainc d'abord que la
+grammaire peut être vue comme décrivant une expression de termes $c$
+reliés par deux opérations binaires $a$ et $b$, toutes les deux
+associatives à droite, et l'opération $b$ étant prioritaire sur $a$.
+Autrement dit, l'expression dérivant de $S$ est coupée d'abord au
+niveau des $a$ en des sous-expressions dérivant de $T$, elles-mêmes
+coupées au niveau des $b$.)
+\end{corrige}
+
+(2) Le langage $L := L(G)$ engendré par $G$ est, en fait, rationnel :
+expliquer brièvement pourquoi, et donner une expression rationnelle
+qui le dénote. (On pourra commencer par décrire le langage $L' :=
+L(G,T) := \{w \in \Sigma^* : T \mathrel{\Rightarrow^*_G} w\}$ des mots
+qui dérivent de $T$ selon $G$.)
+
+\begin{corrige}
+Le langage $L' = L(G,T)$ est celui décrit par la grammaire $T
+\rightarrow c \;|\; cbT$ d'axiome $T$ (le nonterminal $U$ est
+visiblement inutile et peut être directement remplacé par $c$ pour y
+voir plus clair). Il s'agit visiblement du langage dénoté par
+l'expression rationnelle $(cb){*}c$ (ceci se démontre par exemple en
+remarquant que ses dérivations sont toutes de la forme $T \Rightarrow
+cbT \Rightarrow \cdots \Rightarrow (cb)^k T \Rightarrow (cb)^k c$, ou
+en raisonnant sur les arbres d'analyse qui sont formés en empilant des
+$T$ ayant pour fils gauche $c$ et $b$ et pour fils droite un autre $T$
+jusqu'à un dernier $T$ qui a pour seul fils $c$ ; on peut aussi
+remarquer qu'il s'agit essentiellement d'une grammaire régulière) : si
+on préfère, $L'$ est le plus petit langage tel que $L' = \{c\} \cup
+(\{c\}\{b\}L')$, ce que dénote justement $(cb){*}c$. Bref, un mot de
+$L'$ est une succession de $c$ séparés par des $b$, ce que dénote
+justement $(cb){*}c$.
+
+Le langage $L = L(G,S)$ est construit selon exactement le même modèle
+à partir de $L'$ que $L'$ à partir de $c$ : si on préfère, $L$ est le
+plus petit langage tel que $L = L' \cup (L'\{a\}L)$, donc on s'attend
+à avoir ce qu'il soit dénoté par $((cb){*}ca){*}(cb){*}c$. On peut
+par exemple raisonner sur les arbres d'analyse : ils sont formés en
+empilant des $S$ ayant pour fils gauche $T$ et $a$ et pour fils droite
+un autre $S$ jusqu'à un dernier $S$ qui a pour seul fils $T$, et enfin
+en insérant un arbre d'analyse d'un mot de $L'$ comme descendance de
+chaque $T$. Bref, un mot de $L$ est une succession de mots de $L'$
+séparés par des $a$, ce que dénote justement $((cb){*}ca){*}(cb){*}c$.
+
+Tout ceci étant dit, en fait, le langage $L$ peut aussi être dénoté
+par une expression rationnelle plus simple, à savoir $(c(a|b)){*}c$
+(ou encore $c((a|b)c){*}$ ou encore $c(ac|bc){*}$ ou toutes sortes
+d'autres variantes), puisqu'il s'agit d'une succession de $c$ séparés
+indifféremment par des $a$ ou des $b$. Cette expression rationnelle
+perd le découpage en deux niveaux (d'abord par $a$ puis par $b$)
+effectué par la grammaire $G$, mais est correcte comme description du
+langage.
+\end{corrige}
+
+
+%
+%
+%
+\end{document}
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 1ac129e..74b3147 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -4271,7 +4271,7 @@ Voici comment on peut le mettre en œuvre de façon plus concrète :
état inaccessible}} (si nécessaire, déterminiser l'automate s'il
n'est pas déterministe, le compléter s'il est incomplet, et
supprimer les états inaccessibles s'il y en a) ;
-\item appeler $\Pi$ la partition des automates en deux classes : les
+\item appeler $\Pi$ la partition des états en deux classes : les
états finaux d'un côté, et les non-finaux de l'autre ;
\item répéter l'opération suivante tant que la partition $\Pi$
change : pour chaque classe $C$ de $\Pi$ et chaque lettre $x \in
@@ -6088,7 +6088,7 @@ construits (et éventuellement les arbres eux-mêmes).
\subsection{Présentation générale}
\thingy\textbf{Discussion préalable.} On s'intéresse ici à la question
-de savoir ce qu'un \defin{algorithme} peut ou ne peut pas faire.
+de savoir ce qu'un \defin[algorithme (en calculabilité)]{algorithme} peut ou ne peut pas faire.
Pour procéder de façon rigoureuse, il faudrait formaliser la notion
d'algorithme (par exemple à travers le concept de machine de Turing) :
on a préféré rester informel sur cette définition — par exemple « un
@@ -6266,7 +6266,7 @@ temps fini, et calcule (renvoie) $f(n)$.
\smallskip
On dit qu'un ensemble $A \subseteq \mathbb{N}$ (un « langage »,
-cf. \ref{computability-all-data-are-integers}) est \defin{décidable}
+cf. \ref{computability-all-data-are-integers}) est \defin[décidable (langage)]{décidable}
(ou \index{calculable (langage)|see{décidable}}« calculable » ou
\index{récursif (langage)|see{décidable}}« récursif ») lorsque sa
fonction indicatrice $\mathbf{1}_A \colon \mathbb{N} \to \mathbb{N}$
@@ -7766,6 +7766,243 @@ l'expression.)
\end{corrige}
%
+
+\exercice
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.
+
+On considère l'expression rationnelle $r$ suivante : $(ab|ba){*}$ (sur
+l'alphabet $\Sigma$). On appelle $L := L(r)$ le langage qu'elle
+dénote.
+
+(0) Donner quatre exemples de mots de $L$ et quatre exemples de mots
+n'appartenant pas à $L$.
+
+\begin{corrige}
+Par exemple, les mots $\varepsilon$, $ab$, $ba$ et $abba$
+appartiennent à $L$. Les mots $a$, $b$, $aa$ et $aba$ n'appartiennent
+pas à $L$.
+\end{corrige}
+
+(1) Traiter l'une \emph{ou} l'autre des questions suivantes :
+(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ;
+(ii) construire l'automate de Thompson de $r$, puis éliminer les
+transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on
+retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$
+l'automate ainsi obtenu.
+
+\begin{corrige}
+L'automate $\mathscr{A}_1$ obtenu est le suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (S3) at (150bp,35bp) [draw,circle,state,final] {$3$};
+\node (S4) at (150bp,-35bp) [draw,circle,state,final] {$4$};
+\draw [->] (S0) -- node[auto,near end] {$a$} (S1);
+\draw [->] (S0) -- node[auto,below] {$b$} (S2);
+\draw [->] (S1) -- node[auto,below] {$b$} (S3);
+\draw [->] (S2) -- node[auto] {$a$} (S4);
+\draw [->] (S3) -- node[auto,above,very near end] {$b$} (S2);
+\draw [->] (S4) -- node[auto,very near end] {$a$} (S1);
+\draw [->] (S3) to[out=135,in=45] node[auto,above] {$a$} (S1);
+\draw [->] (S4) to[out=225,in=315] node[auto] {$b$} (S2);
+\end{tikzpicture}
+\end{center}
+C'est l'automate de Glushkov. Si on commence par construire
+l'automate de Thompson, on obtient le suivant (à $12$ états) :
+\begin{center}
+\scalebox{0.70}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial] {};
+\node (S0u) at (60bp,0bp) [draw,circle,state] {};
+\node (S0a) at (120bp,40bp) [draw,circle,state] {};
+\node (S1) at (180bp,40bp) [draw,circle,state] {};
+\node (S1u) at (240bp,40bp) [draw,circle,state] {};
+\node (S3) at (300bp,40bp) [draw,circle,state] {};
+\node (S0b) at (120bp,-40bp) [draw,circle,state] {};
+\node (S2) at (180bp,-40bp) [draw,circle,state] {};
+\node (S2u) at (240bp,-40bp) [draw,circle,state] {};
+\node (S4) at (300bp,-40bp) [draw,circle,state] {};
+\node (SF) at (360bp,0bp) [draw,circle,state] {};
+\node (SFu) at (420bp,0bp) [draw,circle,state,final] {};
+\draw [->] (S0) -- (S0u);
+\draw [->] (S0u) -- (S0a);
+\draw [->] (S0a) -- node[auto] {$a$} (S1); \draw [->] (S1) -- (S1u);
+\draw [->] (S1u) -- node[auto] {$b$} (S3); \draw [->] (S3) -- (SF);
+\draw [->] (S0u) -- (S0b);
+\draw [->] (S0b) -- node[auto] {$b$} (S2); \draw [->] (S2) -- (S2u);
+\draw [->] (S2u) -- node[auto] {$a$} (S4); \draw [->] (S4) -- (SF);
+\draw [->] (SF) -- (SFu);
+\draw [->] (SF) to[out=90,in=0] (210bp,70bp) to[out=180,in=90] (S0u);
+\draw [->] (S0) to[out=270,in=180] (120bp,-70bp) -- (300bp,-70bp) to[out=0,in=270] (SFu);
+\end{tikzpicture}
+}
+\end{center}
+(où toutes les flèches non étiquetées sont des transitions spontanées,
+c'est-à-dire qu'il faut les imaginer étiquetées par $\varepsilon$) qui
+par élimination des transitions spontanées donne celui $\mathscr{A}_1$
+qu'on a tracé au-dessus (les seuls états qui subsistent après
+élimination des transitions spontanées sont l'état initial et les
+quatre états auxquels aboutissent une transition non spontanée).
+\end{corrige}
+
+(2) À partir de $\mathscr{A}_1$, construire un automate fini
+déterministe complet reconnaissant $L$. On appellera $\mathscr{A}_2$
+l'automate en question.
+
+\begin{corrige}
+L'automate $\mathscr{A}_1$ est déterministe incomplet : il s'agit donc
+simplement de lui ajouter un état « puits » pour le rendre complet, ce
+qui donne l'automate $\mathscr{A}_2$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (S3) at (150bp,35bp) [draw,circle,state,final] {$3$};
+\node (S4) at (150bp,-35bp) [draw,circle,state,final] {$4$};
+\node (Sink) at (220bp,0bp) [draw,circle,state] {$\bot$};
+\draw [->] (S0) -- node[auto,near end] {$a$} (S1);
+\draw [->] (S0) -- node[auto,below] {$b$} (S2);
+\draw [->] (S1) -- node[auto] {$b$} (S3);
+\draw [->] (S2) -- node[auto,below] {$a$} (S4);
+\draw [->] (S3) -- node[auto,above,very near end] {$b$} (S2);
+\draw [->] (S4) -- node[auto,very near end] {$a$} (S1);
+\draw [->] (S3) to[out=135,in=45] node[auto,above] {$a$} (S1);
+\draw [->] (S4) to[out=225,in=315] node[auto] {$b$} (S2);
+\draw [->] (S1) -- node[auto,very near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,very near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop right] node[auto] {$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(3) Minimiser l'automate $\mathscr{A}_2$. On appellera
+$\mathscr{A}_3$ l'automate canonique ainsi obtenu.
+
+(On obtient un automate ayant $4$ états.)
+
+\begin{corrige}
+L'algorithme de minimisation identifie les trois états finaux
+($0,3,4$) de l'automate $\mathscr{A}_2$, ce qui donne
+l'automate $\mathscr{A}_3$ suivant (on note $0$ pour l'état résultant
+de l'identification de $0,3,4$) :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (Sink) at (140bp,0bp) [draw,circle,state] {$\bot$};
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) -- node[auto,near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop right] node[auto] {$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M
+:= \Sigma^*\setminus L$ complémentaire de $L$.
+
+\begin{corrige}
+L'automate $\mathscr{A}_3$ étant un automate fini déterministe complet
+reconnaissant $L$, il suffit de marquer finaux les états non-finaux et
+vice versa pour obtenir l'automate $\mathscr{A}_4$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state,final,accepting above] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state,final,accepting below] {$2$};
+\node (Sink) at (140bp,0bp) [draw,circle,state,final,accepting below] {$\bot$};
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) -- node[auto,near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop right] node[auto] {$a,b$} (Sink);
+\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$.
+
+\begin{corrige}
+Pour appliquer la méthode d'élimination des états, on commence par
+modifier l'automate pour avoir un unique état initial $I$, qui ne soit
+pas final, et qui n'ait aucune transition qui y aboutisse, et un
+unique état final $F$, qui ne soit pas initial, et sans aucune
+transition qui en part :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (SI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (S0) at (0bp,0bp) [draw,circle,state] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (Sink) at (140bp,0bp) [draw,circle,state] {$\bot$};
+\node (SF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (SI) -- node[auto] {$\underline{\varepsilon}$} (S0);
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) -- node[auto,near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop above] node[auto] {$a|b$} (Sink);
+\draw [->] (S1) to[out=15,in=135] node[auto,near end] {$\underline{\varepsilon}$} (SF);
+\draw [->] (S2) to[out=345,in=225] node[auto,near end] {$\underline{\varepsilon}$} (SF);
+\draw [->] (Sink) -- node[auto] {$\underline{\varepsilon}$} (SF);
+\end{tikzpicture}
+\end{center}
+On élimine ensuite l'état $\bot$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (SI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (S0) at (0bp,0bp) [draw,circle,state] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (SF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (SI) -- node[auto] {$\underline{\varepsilon}$} (S0);
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) to[out=15,in=135] node[auto,near end] {$\underline{\varepsilon}|a(a|b){*}$} (SF);
+\draw [->] (S2) to[out=345,in=225] node[auto,near end] {$\underline{\varepsilon}|b(a|b){*}$} (SF);
+\end{tikzpicture}
+\end{center}
+Puis les états $1$ et $2$ peuvent être éliminés simultanément :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (SI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (S0) at (0bp,0bp) [draw,circle,state] {$0$};
+\node (SF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (SI) -- node[auto] {$\underline{\varepsilon}$} (S0);
+\draw [->] (S0) -- node[auto] {$a(\underline{\varepsilon}|a(a|b){*})|b(\underline{\varepsilon}|b(a|b){*})$} (SF);
+\draw [->] (S0) to[loop above] node[auto] {$ab|ba$} (S0);
+\end{tikzpicture}
+\end{center}
+Et l'expression rationnelle finalement obtenue est la suivante :
+\[
+(ab|ba){*}(a(\underline{\varepsilon}|a(a|b){*})|b(\underline{\varepsilon}|b(a|b){*}))
+\]
+On pouvait aussi donner, entre autres choses :
+\[
+(ab|ba){*}(a|aa(a|b){*}|b|bb(a|b){*})
+\]
+(obtenue en éliminant les états $1$ et $2$ avant $\bot$).
+\end{corrige}
+
+%
%
%
@@ -8666,6 +8903,61 @@ sont de la forme $S \Rightarrow baS \Rightarrow babaS \Rightarrow
\exercice
+On rappelle la définition du problème de l'arrêt : c'est l'ensemble
+$H$ des couples\footnote{Pour être rigoureux, on a fixé un codage
+ permettant de représenter les programmes $e$, les entrées $x$ à ces
+ programmes, et les couples $(e,x)$, comme des éléments
+ de $\mathbb{N}$ (ou bien de $\Sigma^*$ sur un alphabet
+ $\Sigma\neq\varnothing$ arbitraire). Il n'est pas nécessaire de
+ faire apparaître ce codage dans la description des algorithmes
+ proposés, qui peut rester informelle.} $(e,x)$ formés d'un programme
+(=algorithme) $e$ et d'une entrée $x$, tels que l'exécution du
+programme $e$ sur l'entrée $x$ termine en temps fini. On a vu en
+cours que $H$ était semi-décidable mais non décidable\footnote{Une
+ variante consiste à considérer l'ensemble des $e$ tels que $e$
+ termine sur l'entrée $e$ : l'ensemble $H$ qu'on vient de définir s'y
+ ramène facilement.}.
+
+On considère l'ensemble $H'$ des triplets $(e_1,e_2,x)$ tels que
+$(e_1,x) \in H$ \emph{ou bien} $(e_2,x) \in H$ (ou les deux).
+Autrement dit, au moins l'un des programmes $e_i$ termine en temps
+fini quand on l'exécute sur l'entrée $x$.
+
+(1) L'ensemble $H'$ est-il semi-décidable ?
+
+\begin{corrige}
+Nous allons montrer que $H'$ est semi-décidable.
+
+Considérons l'algorithme suivant : donné en entrée un triplet
+$(e_1,e_2,x)$, on exécute en parallèle, en fournissant à chacun
+l'entrée $x$, les programmes (codés par) $e_1$ et $e_2$ (au moyen
+d'une machine universelle), et en s'arrêtant immédiatement si l'un des
+deux s'arrête, et on renvoie alors « vrai ». Manifestement, cet
+algorithme termine (en renvoyant « vrai ») si et seulement si
+$(e_1,e_2,x) \in H'$, ce qui montre que $H'$ est semi-décidable.
+\end{corrige}
+
+(2) L'ensemble $H'$ est-il décidable ?
+
+\begin{corrige}
+Nous allons montrer que $H'$ n'est pas décidable.
+
+Supposons par l'absurde qu'il existe un algorithme $T$ qui
+décide $H'$. Soit $e'$ (le code d')un programme quelconque qui
+effectue une boucle infinie (quelle que soit son entrée) : comme $e'$
+ne termine jamais, un triplet $(e,e',x)$ appartient à $H'$ si et
+seulement si $(e,x)$ appartient à $H$. Considérons maintenant
+l'algorithme suivant : donné en entrée un couple $(e,x)$, on applique
+l'algorithme $T$ supposé exister pour décider si $(e,e',x) \in H'$ ;
+comme on vient de l'expliquer, ceci équivaut à $(e,x) \in H$. On a
+donc fabriqué un algorithme qui décide $H$, ce qui est impossible,
+d'où la contradiction annoncée.
+\end{corrige}
+
+%
+
+\exercice
+
Soit $\Sigma$ un alphabet (fini, non vide) fixé. Les questions
suivantes sont indépendantes (mais on remarquera leur parallélisme).
Ne pas hésiter à décrire les algorithmes de façon succincte et
@@ -8950,7 +9242,7 @@ termine en renvoyant vrai (sinon, bien sûr, on ne termine pas).
Pour semi-décider $L_1\cap L_2$, en revanche, il n'y a pas de raison
de procéder en parallèle : on lance d'abord $T_1$ sur le mot $w$ à
-tester : si $T_1$ termine, on lance ensuite $T_1$ sur le même mot : si
+tester : si $T_1$ termine, on lance ensuite $T_2$ sur le même mot : si
$T_2$ termine et renvoie vrai, on renvoie vrai ; si l'un des deux
algorithmes $T_i$ lancés séquentiellement ne termine pas, bien sûr, le
calcul dans son ensemble ne terminera pas.