Test for 2022-08-25, essentially copied for that of 2018-02-06.

1 files changed, 683 insertions, 0 deletions

diff --git a/controle-20220825.tex b/controle-20220825.tex
new file mode 100644
index 0000000..c3cf461
--- /dev/null
+++ b/controle-20220825.tex
@@ -0,0 +1,683 @@
+%% 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{25 août 2022}
+\maketitle
+
+% NOTE: Initially copied from controle-20180206.tex
+
+\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
+
+Documents autorisés : uniquement une feuille A4 recto-verso
+(manuscrite ou typographiée).
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 1h30
+
+Barème \emph{indicatif} : 7 points par exercice
+
+\ifcorrige
+Ce corrigé comporte 9 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 s'intéresse au
+langage $L$ formé des mots (éléments de $\Sigma^*$) ayant $aa$ ou $bb$
+comme facteur (c'est-à-dire contenant deux $a$ consécutifs, ou bien
+deux $b$ consécutifs), ainsi qu'à son
+complémentaire $M := \Sigma^* \setminus L$.
+
+(1) Donner une expression rationnelle dénotant $L$.
+
+\begin{corrige}
+Le langage des mots contenant deux $a$ consécutifs est dénoté par
+l'expression rationnelle $(a|b){*}\,aa\,(a|b){*}$, et celui des mots
+contenant deux $b$ consécutifs par $(a|b){*}\,bb\,(a|b){*}$.  On peut
+donc proposer l'expression rationnelle $(a|b){*}\,aa\,(a|b){*} \; | \;
+(a|b){*}\,bb\,(a|b){*}$ ou encore, si on préfère,
+$(a|b){*}\,(aa|bb)\,(a|b){*}$.
+\end{corrige}
+
+(2) \emph{Indépendamment} de la question (1), expliquer brièvement pourquoi
+l'automate $\mathscr{A}_2$ suivant reconnaît le langage $L$ :
+
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (A) at (70bp,35bp) [draw,circle,state] {$A$};
+\node (B) at (70bp,-35bp) [draw,circle,state] {$B$};
+\node (T) at (140bp,0bp) [draw,circle,state,final] {$T$};
+\draw [->] (S) to[loop above] node[auto] {$a,b$} (S);
+\draw [->] (S) -- node[auto,near end] {$a$} (A);
+\draw [->] (S) -- node[auto] {$b$} (B);
+\draw [->] (T) to[loop above] node[auto] {$a,b$} (T);
+\draw [->] (A) -- node[auto,near start] {$a$} (T);
+\draw [->] (B) -- node[auto] {$b$} (T);
+\end{tikzpicture}
+\end{center}
+
+De quelle sorte d'automate s'agit-il ?  (DFA ?  NFA ?...)
+
+\begin{corrige}
+Un chemin de l'unique état initial $S$ à l'unique état final $T$ de
+$\mathscr{A}_2$ doit passer soit par l'état $A$ soit par l'état $B$,
+donc la lecture de ses étiquettes contient le facteur $aa$
+(correspondant aux transitions $S\to A$ et $A\to T$) ou $bb$ ; et
+réciproquement, un mot contenant le facteur $aa$ ou $bb$ peut se lire
+en suivant un chemin de $S$ à $T$ dans l'automate (en plaçant le
+facteur $aa$ au niveau des transitions $S\to A$ et $A\to T$ ou de
+façon analogue pour $bb$).
+
+Il s'agit là d'un automate non déterministe (l'état $S$ a plusieurs
+transitions sortantes étiquetées par $a$), mais sans transitions
+spontanées ou en abrégé, NFA.
+\end{corrige}
+
+(3) Déterminiser (si nécessaire) l'automate $\mathscr{A}_2$ représenté
+en (2) ; on appellera $\mathscr{A}_3$ l'automate résultant.
+
+\begin{corrige}
+En notant $S$, $SA$, $SB$, $SAT$ et $SBT$ les états de l'automate
+déterministe $\mathscr{A}_3$ qui correspondent aux ensembles d'états
+de l'automate $\mathscr{A}_2$ donnés par les lettres en question, la
+déterminisation conduit à l'automate $\mathscr{A}_3$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$};
+\node (SAT) at (140bp,35bp) [draw,circle,state,final] {$SAT$};
+\node (SBT) at (140bp,-35bp) [draw,circle,state,final] {$SBT$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$a$} (SAT);
+\draw [->] (SB) -- node[auto,below] {$b$} (SBT);
+\draw [->] (SAT) to[out=300,in=60] node[auto] {$b$} (SBT);
+\draw [->] (SBT) to[out=120,in=240] node[auto] {$a$} (SAT);
+\draw [->] (SAT) to[loop above] node[auto] {$a$} (SAT);
+\draw [->] (SBT) to[loop below] node[auto] {$b$} (SBT);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(4) Minimiser (si nécessaire) l'automate $\mathscr{A}_3$ obtenu
+en (3) ; on appellera $\mathscr{A}_4$ l'automate minimal (=canonique)
+résultant.
+
+\begin{corrige}
+On part bien d'un automate $\mathscr{A}_3$ déterministe complet sans
+état inaccessible.  La première étape de l'algorithme de minimisation
+sépare deux classes d'états : $S,SA,SB$ (non finaux) d'une part et
+$SAT,SBT$ de l'autre.  Ensuite on sépare $S$ et $SA$ et $SB$ (car le
+premier ne conduit qu'à des états non finaux, le deuxième conduit à un
+état final par la transition étiquetée $a$, et le troisième conduit à
+un état final par la transition étiquetée $b$).  Les étapes suivantes
+ne conduisent pas à d'autres séparations d'états.  On obtient
+finalement un automate $\mathscr{A}_4$ à quatre états, qu'on peut
+appeler $S,SA,SB,U$ où $U$ est la classe de $SAT$ et $SBT$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$};
+\node (U) at (140bp,0bp) [draw,circle,state,final] {$U$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$a$} (U);
+\draw [->] (SB) -- node[auto,below] {$b$} (U);
+\draw [->] (U) to[loop above] node[auto] {$a,b$} (U);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(5) Construire un automate $\mathscr{A}_5$ reconnaissant le
+langage $M$ complémentaire de $L$.
+
+\begin{corrige}
+On obtient $\mathscr{A}_5$ en échangeant états finaux et non finaux
+dans $\mathscr{A}_4$, c'est-à-dire l'automate $\mathscr{A}_5$
+suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state,final] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state,final] {$SB$};
+\node (U) at (140bp,0bp) [draw,circle,state] {$U$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$a$} (U);
+\draw [->] (SB) -- node[auto,below,near end] {$b$} (U);
+\draw [->] (U) to[loop above] node[auto] {$a,b$} (U);
+\end{tikzpicture}
+\end{center}
+(L'état $U$ est maintenant un puits.)
+\end{corrige}
+
+(6) En appliquant à $\mathscr{A}_5$ la méthode d'élimination des
+états, déterminer une expression rationnelle dénotant le langage $M$.
+
+\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.
+L'état $U$ peut être éliminé d'emblée puisqu'il est inutile (il n'est
+pas co-accessible : c'est un puits !).  On a donc affaire à l'automate
+suivant
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$};
+\node (F) at (140bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$\underline{\varepsilon}$} (F);
+\draw [->] (SB) -- node[auto,below,near end] {$\underline{\varepsilon}$} (F);
+\draw [->] (S) to[out=270,in=90] (0,-30bp) to[out=270,in=270] node[auto,below] {$\underline{\varepsilon}$} (140bp,-30bp) to[in=270,out=90] (F);
+\end{tikzpicture}
+\end{center}
+On élimine maintenant l'état $SB$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (F) at (140bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (S) -- node[auto,near end] {$a|ba$} (SA);
+\draw [->] (SA) -- node[auto] {$\underline{\varepsilon}|b$} (F);
+\draw [->] (S) to[out=270,in=270] node[auto,below] {$\underline{\varepsilon}|b$} (F);
+\draw [->] (SA) to[loop below] node[auto] {$ba$} (SA);
+\end{tikzpicture}
+\end{center}
+Et l'élimination de l'état $SA$ conduit à l'expression rationnelle
+$\underline{\varepsilon}\,|\,b\,|\penalty0\,(a|ba)(ba){*}(\underline{\varepsilon}|b)$
+(il y a bien sûr toutes sortes d'autres expressions rationnelles
+équivalentes : par exemple, on peut la réécrire comme
+$\underline{\varepsilon}\,|\,b\,|\penalty0\,(\varepsilon|b)a(ba){*}(\underline{\varepsilon}|b)$
+ou encore comme
+$(\varepsilon|b)(\underline{\varepsilon}|a(ba){*}(\underline{\varepsilon}|b))$ ;
+si on avait éliminé l'état $SA$ en premier, on serait plutôt tombé sur
+$\underline{\varepsilon}\,|\,a\,|\penalty0\,(b|ab)(ab){*}(\underline{\varepsilon}|a)$,
+et ainsi de suite).
+\end{corrige}
+
+
+
+%
+%
+%
+
+\exercice
+
+On considère la grammaire hors-contexte $G$ d'axiome $S$ et de
+nonterminaux $N = \{S, T, U, V\}$ sur l'alphabet $\Sigma =
+\{{\#},{@},{(},{)}, x, y, z\}$ (soit $7$ lettres) donnée par
+\[
+\begin{aligned}
+S &\rightarrow T \;|\; S\mathbin{\#}T\\
+T &\rightarrow U \;|\; U\mathbin{@}T\\
+U &\rightarrow V \;|\; (\,S\,)\\
+V &\rightarrow x \;|\; y \;|\; z\\
+\end{aligned}
+\]
+(On pourra imaginer que $\#$ et $@$ sont deux opérations binaires, les
+parenthèses servent comme on s'y attend, et $x,y,z$ sont trois opérandes
+auxquelles on peut vouloir appliquer ces opérations.)
+
+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 :
+(a) $x\mathbin{\#}y\mathbin{\#}z$, (b) $x\mathbin{\#}y\mathbin{@}z$,
+(c) $x\mathbin{@}y\mathbin{\#}z$, (d) $x\mathbin{@}y\mathbin{@}z$,
+(e) $(x\mathbin{\#}y)\mathbin{@}z$.
+
+\begin{corrige}
+On obtient les arbres d'analyse suivants :
+(a) % S<S<S<T<U<V<x.>>>>#.T<U<V<y.>>>>#.T<U<V<z.>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (53.333bp,0.000bp) [draw=none] {$S$};
+\node (S1) at (20.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (S2) at (0.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (T0) at (0.000bp,-80.000bp) [draw=none] {$T$};  \draw (S2) -- (T0);
+\node (U0) at (0.000bp,-100.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (V0) at (0.000bp,-120.000bp) [draw=none] {$V$};  \draw (U0) -- (V0);
+\node (x0) at (0.000bp,-140.000bp) [draw=none] {$x$};  \draw (V0) -- (x0);
+\node (o0) at (20.000bp,-60.000bp) [draw=none] {$\#$};  \draw (S1) -- (o0);
+\node (T1) at (40.000bp,-60.000bp) [draw=none] {$T$};  \draw (S1) -- (T1);
+\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (V1) at (40.000bp,-100.000bp) [draw=none] {$V$};  \draw (U1) -- (V1);
+\node (y0) at (40.000bp,-120.000bp) [draw=none] {$y$};  \draw (V1) -- (y0);
+\node (o1) at (60.000bp,-30.000bp) [draw=none] {$\#$};  \draw (S0) -- (o1);
+\node (T2) at (80.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T2);
+\node (U2) at (80.000bp,-50.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (V2) at (80.000bp,-70.000bp) [draw=none] {$V$};  \draw (U2) -- (V2);
+\node (z0) at (80.000bp,-90.000bp) [draw=none] {$z$};  \draw (V2) -- (z0);
+\end{tikzpicture}
+\hskip1cmplus5cmminus.5cm
+(b) % S<S<T<U<V<x.>>>>#.T<U<V<y.>>@.T<U<V<z.>>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (26.667bp,0.000bp) [draw=none] {$S$};
+\node (S1) at (0.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (T0) at (0.000bp,-50.000bp) [draw=none] {$T$};  \draw (S1) -- (T0);
+\node (U0) at (0.000bp,-70.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (V0) at (0.000bp,-90.000bp) [draw=none] {$V$};  \draw (U0) -- (V0);
+\node (x0) at (0.000bp,-110.000bp) [draw=none] {$x$};  \draw (V0) -- (x0);
+\node (o0) at (20.000bp,-30.000bp) [draw=none] {$\#$};  \draw (S0) -- (o0);
+\node (T1) at (60.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T1);
+\node (U1) at (40.000bp,-60.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (V1) at (40.000bp,-80.000bp) [draw=none] {$V$};  \draw (U1) -- (V1);
+\node (y0) at (40.000bp,-100.000bp) [draw=none] {$y$};  \draw (V1) -- (y0);
+\node (o1) at (60.000bp,-60.000bp) [draw=none] {$@$};  \draw (T1) -- (o1);
+\node (T2) at (80.000bp,-60.000bp) [draw=none] {$T$};  \draw (T1) -- (T2);
+\node (U2) at (80.000bp,-80.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (V2) at (80.000bp,-100.000bp) [draw=none] {$V$};  \draw (U2) -- (V2);
+\node (z0) at (80.000bp,-120.000bp) [draw=none] {$z$};  \draw (V2) -- (z0);
+\end{tikzpicture}
+\hskip1cmplus5cmminus.5cm
+(c) % S<S<T<U<V<x.>>@.T<U<V<y.>>>>>#.T<U<V<z.>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (53.333bp,0.000bp) [draw=none] {$S$};
+\node (S1) at (20.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (T0) at (20.000bp,-50.000bp) [draw=none] {$T$};  \draw (S1) -- (T0);
+\node (U0) at (0.000bp,-80.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (V0) at (0.000bp,-100.000bp) [draw=none] {$V$};  \draw (U0) -- (V0);
+\node (x0) at (0.000bp,-120.000bp) [draw=none] {$x$};  \draw (V0) -- (x0);
+\node (o0) at (20.000bp,-80.000bp) [draw=none] {$@$};  \draw (T0) -- (o0);
+\node (T1) at (40.000bp,-80.000bp) [draw=none] {$T$};  \draw (T0) -- (T1);
+\node (U1) at (40.000bp,-100.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (V1) at (40.000bp,-120.000bp) [draw=none] {$V$};  \draw (U1) -- (V1);
+\node (y0) at (40.000bp,-140.000bp) [draw=none] {$y$};  \draw (V1) -- (y0);
+\node (o1) at (60.000bp,-30.000bp) [draw=none] {$\#$};  \draw (S0) -- (o1);
+\node (T2) at (80.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T2);
+\node (U2) at (80.000bp,-50.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (V2) at (80.000bp,-70.000bp) [draw=none] {$V$};  \draw (U2) -- (V2);
+\node (z0) at (80.000bp,-90.000bp) [draw=none] {$z$};  \draw (V2) -- (z0);
+\end{tikzpicture}
+\hskip1cmplus5cmminus.5cm
+(d) % S<T<U<V<x.>>@.T<U<V<y.>>@.T<U<V<z.>>>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (26.667bp,0.000bp) [draw=none] {$S$};
+\node (T0) at (26.667bp,-20.000bp) [draw=none] {$T$};  \draw (S0) -- (T0);
+\node (U0) at (0.000bp,-50.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (V0) at (0.000bp,-70.000bp) [draw=none] {$V$};  \draw (U0) -- (V0);
+\node (x0) at (0.000bp,-90.000bp) [draw=none] {$x$};  \draw (V0) -- (x0);
+\node (o0) at (20.000bp,-50.000bp) [draw=none] {$@$};  \draw (T0) -- (o0);
+\node (T1) at (60.000bp,-50.000bp) [draw=none] {$T$};  \draw (T0) -- (T1);
+\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (V1) at (40.000bp,-100.000bp) [draw=none] {$V$};  \draw (U1) -- (V1);
+\node (y0) at (40.000bp,-120.000bp) [draw=none] {$y$};  \draw (V1) -- (y0);
+\node (o1) at (60.000bp,-80.000bp) [draw=none] {$@$};  \draw (T1) -- (o1);
+\node (T2) at (80.000bp,-80.000bp) [draw=none] {$T$};  \draw (T1) -- (T2);
+\node (U2) at (80.000bp,-100.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (V2) at (80.000bp,-120.000bp) [draw=none] {$V$};  \draw (U2) -- (V2);
+\node (z0) at (80.000bp,-140.000bp) [draw=none] {$z$};  \draw (V2) -- (z0);
+\end{tikzpicture}
+\hskip1cmplus5cmminus.5cm
+(e) % S<T<U<(.S<S<T<U<V<x.>>>>#.T<U<V<y.>>>>).>@.T<U<V<z.>>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (86.667bp,0.000bp) [draw=none] {$S$};
+\node (T0) at (86.667bp,-20.000bp) [draw=none] {$T$};  \draw (S0) -- (T0);
+\node (U0) at (40.000bp,-50.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (p0) at (0.000bp,-80.000bp) [draw=none] {$($};  \draw (U0) -- (p0);
+\node (S1) at (40.000bp,-80.000bp) [draw=none] {$S$};  \draw (U0) -- (S1);
+\node (S2) at (20.000bp,-110.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (T1) at (20.000bp,-130.000bp) [draw=none] {$T$};  \draw (S2) -- (T1);
+\node (U1) at (20.000bp,-150.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (V0) at (20.000bp,-170.000bp) [draw=none] {$V$};  \draw (U1) -- (V0);
+\node (x0) at (20.000bp,-190.000bp) [draw=none] {$x$};  \draw (V0) -- (x0);
+\node (o0) at (40.000bp,-110.000bp) [draw=none] {$\#$};  \draw (S1) -- (o0);
+\node (T2) at (60.000bp,-110.000bp) [draw=none] {$T$};  \draw (S1) -- (T2);
+\node (U2) at (60.000bp,-130.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (V1) at (60.000bp,-150.000bp) [draw=none] {$V$};  \draw (U2) -- (V1);
+\node (y0) at (60.000bp,-170.000bp) [draw=none] {$y$};  \draw (V1) -- (y0);
+\node (p1) at (80.000bp,-80.000bp) [draw=none] {$)$};  \draw (U0) -- (p1);
+\node (o1) at (100.000bp,-50.000bp) [draw=none] {$@$};  \draw (T0) -- (o1);
+\node (T3) at (120.000bp,-50.000bp) [draw=none] {$T$};  \draw (T0) -- (T3);
+\node (U3) at (120.000bp,-70.000bp) [draw=none] {$U$};  \draw (T3) -- (U3);
+\node (V2) at (120.000bp,-90.000bp) [draw=none] {$V$};  \draw (U3) -- (V2);
+\node (z0) at (120.000bp,-110.000bp) [draw=none] {$z$};  \draw (V2) -- (z0);
+\end{tikzpicture}
+\end{corrige}
+
+(2) En considérant que $(w)$ a le même effet ou la même valeur
+que $w$ : (a) L'une des deux opérations $\#$ et $@$ est-elle
+prioritaire\footnote{On dit qu'une opération binaire $\boxtimes$ est
+  \emph{prioritaire} sur $\boxplus$ lorsque « $u\boxtimes v\boxplus
+  w$ » se comprend comme « $(u\boxtimes v)\boxplus w$ » (i.e., les
+  deux ont le même effet ou la même valeur), et « $u\boxplus
+  v\boxtimes w$ » comme « $u\boxplus (v\boxtimes w)$ ».}  sur
+l'autre ?  Laquelle ?\quad (b) L'opération $\#$
+s'associe-t-elle\footnote{On dit qu'une opération binaire $\boxdot$
+  \emph{s'associe à gauche} lorsque « $u\boxdot v\boxdot w$ » se
+  comprend comme « $(u\boxdot v)\boxdot w$ », et \emph{s'associe à
+    droite} lorsque « $u\boxdot v\boxdot w$ » se comprend comme
+  « $u\boxdot (v\boxdot w)$ ».} à gauche ou à droite ?\quad
+(c) L'opération $@$ s'associe-t-elle à gauche ou à droite ?
+
+\begin{corrige}
+(a) Les arbres d'analyse (b) et (c) de la question (1) montrent que
+  l'opération $@$ est prioritaire sur $\#$ (elle est toujours plus
+  profonde dans l'arbre, c'est-à-dire appliquée en premier aux
+  opérandes).\quad (b) L'arbre d'analyse (a) de la question (1) montre
+  que $\#$ s'associe à gauche (le $\#$ entre les deux opérandes gauche
+  est plus profond, c'est-à-dire appliqué en premier).\quad
+  (c) Symétriquement, l'arbre d'analyse (d) de la question (1) montre
+  que $@$ s'associe à droite.
+\end{corrige}
+
+\smallskip
+
+(La question (3) est indépendante de (1) et (2).  Par ailleurs, on
+pourra, si on souhaite s'épargner des confusions, choisir de renommer
+en $a$ la lettre « parenthèse ouvrante » de $\Sigma$ et en $b$ la
+lettre « parenthèse fermante » afin de les distinguer des parenthèses
+mathématiques.)
+
+(3) Soit $L = L(G)$ le langage engendré par $G$.  Soit $M$ le langage
+des mots sur $\Sigma$ formés d'un certain nombre de parenthèses
+ouvrantes, puis de la lettre $x$, puis d'un certain nombre
+(possiblement différent) de parenthèses fermantes : autrement dit, des
+mots de la forme « ${(}^i\, x\, {)}^j$ », où on a noté « ${(}^i$ » une
+succession de $i$ parenthèses ouvrantes et « ${)}^j$ » une succession
+de $j$ parenthèses fermantes (on pourra noter ce mot $a^i x b^j$ si on
+préfère).\quad (a) Décrire le langage $L\cap M$ (des mots de $L$ qui
+appartiennent aussi à $M$).\quad (b) Ce langage $L\cap M$ est-il
+rationnel ?\quad (c) Le langage $L$ est-il rationnel ?
+
+\begin{corrige}
+(a) Cherchons pour quelles valeurs $(i,j) \in \mathbb{N}^2$ le mot
+  « ${(}^i\, x\, {)}^j$ » de $M$ appartient à $L$.  La dérivation $S
+  \Rightarrow T \Rightarrow U \Rightarrow (S) \Rightarrow (T)
+  \Rightarrow (U) \Rightarrow ((S)) \Rightarrow \cdots
+  \Rightarrow{(}^i\, S\, {)}^i \Rightarrow{(}^i\, T\, {)}^i
+  \Rightarrow{(}^i\, U\, {)}^i \Rightarrow{(}^i\, V\, {)}^i
+  \Rightarrow{(}^i\, x\, {)}^i$ montre que c'est le cas si $j=i$,
+  autrement dit s'il y a autant de parenthèses fermantes qu'ouvrantes.
+  Mais réciproquement, la propriété d'avoir autant de parenthèses
+  fermantes qu'ouvrantes est préservée par toutes les productions
+  de $G$ (et est satisfaite par l'axiome), donc est vérifiée par tout
+  mot de $L=L(G)$.  On a donc prouvé que le $L\cap M$ est l'ensemble
+  des mots de la forme « ${(}^i\, x\, {)}^i$ » où $i\in \mathbb{N}$.
+
+(b) Le langage $L\cap M$ constitué des mots de la forme « ${(}^n\,
+  x\, {)}^n$ » où $i\in \mathbb{N}$ n'est pas rationnel.  Cela résulte
+  du lemme de pompage (presque exactement comme l'exemple du langage
+  $\{a^n b^n : i\in\mathbb{N}\}$ donné en cours) : donnons l'argument
+  en remplaçant la parenthèse ouvrante par $a$ et la parenthèse
+  fermante par $b$ pour plus de clarté notationnelle.  Appliquons le
+  lemme de pompage pour les langages rationnels au langage $L \cap M =
+  \{a^n x b^n : i\in\mathbb{N}\}$ supposé par l'absurde être
+  rationnel : appelons $k$ l'entier dont le lemme de pompage garantit
+  l'existence.  Considérons le mot $t := a^k x b^k$ : il doit alors
+  exister une factorisation $t = uvw$ pour laquelle on a (i) $|v|\geq
+  1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in L\cap M$ 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 x b^k$ est de cette forme) ; disons $u = a^\ell$ et $v =
+  a^m$, si bien que $w = a^{k-\ell-m} x 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} x b^k$ appartient à $L\cap M$ ; mais dès que
+  $i\neq 1$, ceci est faux : il suffit donc de prendre $i=0$ pour
+  avoir une contradiction.
+
+(c) Le langage $M$ est rationnel puisqu'il est dénoté par l'expression
+  rationnelle $a{*}xb{*}$ (toujours en notant $a$ la parenthèse
+  ouvrante et $b$ la parenthèse fermante).  Si le langage $L$ était
+  rationnel, le langage $L\cap M$ le serait aussi (on sait que
+  l'intersection de deux langages rationnels est rationnelle), ce qui
+  n'est pas le cas d'après la question (b).  Le langage $L$ n'est donc
+  pas rationnel.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+(On pourra si on le souhaite remplacer $\mathbb{N}$ partout dans cet
+exercice par l'ensemble $\Sigma^*$ des mots sur un alphabet $\Sigma$
+[fini] non vide fixé quelconque : grâce au codage de Gödel, ceci ne
+change rien au problème ni aux raisonnements.)
+
+Dans cet exercice, on appelle « langage » une partie de $\mathbb{N}$
+(cf. le paragraphe précédent).
+
+On dira que deux langages $L,M$ disjoints (c'est-à-dire tels que
+$L\cap M = \varnothing$) sont \emph{calculablement séparables}
+lorsqu'il existe un langage $E$ \underline{décidable} tel que $L
+\subseteq E$ et $M \subseteq (\mathbb{N}\setminus E)$ (où
+$\mathbb{N}\setminus E$ désigne le complémentaire de $E$) ; dans le
+cas contraire, on dit que $L$ et $M$ sont \emph{calculablement
+  inséparables}.
+
+(1) Expliquer pourquoi deux langages $L,M$ disjoints sont
+calculablement séparables si et seulement s'il existe un algorithme
+qui, prenant en entrée un élément $x$ de $\mathbb{N}$ :
+\begin{itemize}
+\item termine toujours en temps fini,
+\item répond « vrai » si $x\in L$ et « faux » si $x \in M$ (rien n'est
+  imposé si $x\not\in L\cup M$ à part de terminer en temps fini).
+\end{itemize}
+
+\begin{corrige}
+Si $E$ est décidable tel que $L \subseteq E$ et $M \subseteq
+(\mathbb{N}\setminus E)$, alors un algorithme qui décide $E$
+(c'est-à-dire, quand on lui fournit l'entrée $x$, répond « vrai » si
+$x\in E$, et « faux » si $x \not\in E$) répond bien aux critères
+demandés.  Réciproquement, donné un algorithme qui répond aux critères
+demandés, si $E$ est l'ensemble des $x$ sur lesquels il répond
+« vrai », alors $E$ est bien décidable (on peut toujours modifier
+l'algorithme si nécessaire pour qu'il ne réponde que « vrai » ou
+« faux »), et on a $L \subseteq E$ et $M \subseteq
+(\mathbb{N}\setminus E)$.
+\end{corrige}
+
+(2) Expliquer pourquoi deux langages \emph{décidables} disjoints sont
+toujours calculablement séparables.
+
+\begin{corrige}
+Si $L,M$ sont décidables disjoints, on peut poser $E = L$, qui est
+décidable et vérifie à la fois $L \subseteq E$ (trivialement) et $M
+\subseteq (\mathbb{N}\setminus E)$ (c'est une reformulation du fait
+que $M$ est disjoint de $E=L$).
+\end{corrige}
+
+On cherche maintenant à montrer qu'il existe deux langages $L,M$
+\emph{semi-décidables} disjoints et calculablement inséparables.
+
+Pour cela, on appelle $L$ l'ensemble des couples\footnote{Pour être
+  rigoureux, on a fixé un codage de Gödel 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}$.  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 et
+renvoie la valeur $1$ (ce qui peut se noter $\varphi_e(x) = 1$) ; et
+$M$ le langage défini de la même manière mais avec la valeur $2$,
+i.e., $\varphi_e(x) = 2$.  (Ici, $1$ et $2$ peuvent être remplacés par
+deux éléments distincts quelconques de $\mathbb{N}$ : si on a souhaité
+remplacer $\mathbb{N}$ par $\Sigma^*$, on peut prendre deux mots
+distincts quelconques, par exemple $a$ et $aa$.)
+
+(3) Pourquoi $L$ et $M$ sont-ils disjoints ?
+
+\begin{corrige}
+Comme $L$ est l'ensemble des couples $(e,x)$ tels que $\varphi_e(x) =
+1$ et $M$ l'ensemble des couples $(e,x)$ tels que $\varphi_e(x) = 2$,
+aucun couple ne peut appartenir aux deux, c'est-à-dire qu'ils sont
+disjoints.
+\end{corrige}
+
+(4) Pourquoi $L$ et $M$ sont-ils semi-décidables ?
+
+\begin{corrige}
+Pour semi-décider si un couple $(e,x)$ appartient à $L$, il suffit de
+lancer l'exécution du programme $e$ sur l'entrée $x$ et, si elle
+termine en retournant $1$, renvoyer « vrai », tandis que si elle
+termine en renvoyant n'importe quelle autre valeur, faire une boucle
+infinie (bien sûr, si le programme $e$ ne termine jamais sur
+l'entrée $x$, on ne termine pas non plus).  Ceci montre que $L$ est
+semi-décidable.  Le même raisonnement s'applique pour $M$.
+\end{corrige}
+
+(5) En imitant la démonstration du théorème de Turing sur
+l'indécidabilité du problème de l'arrêt, montrer qu'il n'existe aucun
+algorithme qui, prenant en entrée un couple $(e,x)$, termine toujours
+en temps fini et répond « vrai » si $(e,x)\in L$ et « faux » si $(e,x)
+\in M$ (indication : si un tel algorithme existait, on pourrait s'en
+servir pour faire le contraire de ce qu'il prédit).
+
+\begin{corrige}
+Montrons par l'absurde qu'il n'existe aucun algorithme $T$ comme
+annoncé.  Définissons un nouvel algorithme $T'$ qui, donné un
+entier $e$, effectue les calculs suivants : (1º) interroger
+l'algorithme $T$ (supposé exister !) en lui fournissant le couple
+$(e,e)$ comme entrée, et ensuite (2º) s'il répond vrai, renvoyer la
+valeur $2$, tandis que s'il répond n'importe quoi d'autre, renvoyer la
+valeur $1$.  L'algorithme $T'$ qui vient d'être décrit aurait un
+certain numéro, disons, $p$, et la description de l'algorithme fait
+qu'il termine toujours, que la valeur $\varphi_p(e)$ qu'il renvoie
+vaut toujours soit $1$ soit $2$, et qu'elle vaut $2$ si $(e,e) \in L$
+(c'est-à-dire si $\varphi_e(e) = 1$) et $1$ si $(e,e) \in M$
+(c'est-à-dire si $\varphi_e(e) = 2$).  En particulier, en prenant
+$e=p$, on voit que $\varphi_p(p)$ doit valoir $1$ ou $2$, doit valoir
+$2$ si $\varphi_p(p) = 1$ et $1$ si $\varphi_p(p) = 2$, ce qui est une
+contradiction.
+\end{corrige}
+
+(6) Conclure.
+
+\begin{corrige}
+La question (5) montre (compte tenu de la question (1)) que $L$ et $M$
+ne sont pas calculablement séparables, i.e.., sont calculablement
+inséparables, tandis que (4) et (5) montrent que $L$ et $M$ sont
+disjoints et semi-décidables.  On a donc bien montré l'existence de
+langages semi-décidables disjoints et calculablement inséparables.
+\end{corrige}
+
+
+
+%
+%
+%
+\end{document}