From 8b5e03dd7723f060ef496476b758007cf7ddf4e3 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 16 Jun 2023 17:52:44 +0200
Subject: Test for 2023-06-21, essentially copied from those of 2018-03-22 and
 2021-06-18.

---
 rattrapage-20230621.tex | 575 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 575 insertions(+)
 create mode 100644 rattrapage-20230621.tex

diff --git a/rattrapage-20230621.tex b/rattrapage-20230621.tex
new file mode 100644
index 0000000..27d0168
--- /dev/null
+++ b/rattrapage-20230621.tex
@@ -0,0 +1,575 @@
+%% 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 (rattrapage) — Corrigé\\{\normalsize Théorie des langages}}
+\else
+\title{INF105\\Contrôle de connaissances (rattrapage)\\{\normalsize Théorie des langages}}
+\fi
+\author{}
+\date{21 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
+
+Documents autorisés : uniquement une feuille A4 recto-verso
+(manuscrite ou typographiée).
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 1h30
+
+\ifcorrige
+Ce corrigé comporte 6 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
+
+% NOTE: Initially copied from controle-20180322.tex
+
+Dans cet exercice, on pose $\Sigma = \{a,b,c\}$.  On appelle $L$ le
+langage des mots sur $\Sigma$ qui ont $abc$ comme sous-mot,
+c'est-à-dire, qui contiennent un $a$, un $b$ et un $c$ dans cet ordre
+mais non nécessairement consécutivement (à titre d'exemple, $abac \in
+L$).
+
+\textbf{(1)} Proposer un automate non-déterministe (NFA), sans
+transition spontanée, $\mathscr{A}_1$ qui reconnaît le langage $L$.
+On justifiera rapidement pourquoi l'automate proposé convient.
+
+\begin{corrige}
+On peut proposer l'automate $\mathscr{A}_1$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (140bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3$};
+\draw [->] (q0) to[loop below] node[auto] {$a,b,c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a,b,c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a,b,c$} (q2);
+\draw [->] (q2) -- node[auto] {$c$} (q3);
+\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3);
+\end{tikzpicture}
+\end{center}
+Pour se convaincre qu'il convient, on remarque qu'un chemin de
+l'unique état initial ($0$) à l'unique état final ($3$) dans cet
+automate est formé par trois transitions $0\to 1$, $1\to 2$ et $2\to
+3$, étiquetées par les lettres $a$, $b$ et $c$ respectivement,
+intercalées d'un nombre quelconque de transitions d'un état vers
+lui-même, étiquetées par une lettre quelconque : la lecture de ses
+étiquettes donne bien un mot ayant $abc$ comme sous-mot ; et
+réciproquement, tout tel mot étiquette un chemin de $0$ à $3$ (une
+fois choisies les lettres $a,b,c$ dans l'ordre qui correspondront aux
+transitions changeant d'état).
+
+\emph{Remarque :} il est correct de donner directement l'automate
+déterministe $\mathscr{A}_2$ représenté ci-dessous (puisque tout DFA
+est, en particulier, un NFA), à condition de justifier proprement
+qu'il convient.
+\end{corrige}
+
+\textbf{(2)} Déterminiser (si nécessaire) l'automate $\mathscr{A}_1$
+trouvé en (1) ; on appellera $\mathscr{A}_2$ l'automate résultant.
+
+\begin{corrige}
+En notant $0':=\{0\}$, $1' := \{0,1\}$, $2' := \{0,1,2\}$ et $3' :=
+\{0,1,2,3\}$ les états de l'automate déterministe $\mathscr{A}_2$ qui
+correspondent aux ensembles d'états de l'automate $\mathscr{A}_1$
+qu'on vient d'indiquer, la déterminisation conduit à l'automate
+$\mathscr{A}_2$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$};
+\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$};
+\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3'$};
+\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2);
+\draw [->] (q2) -- node[auto] {$c$} (q3);
+\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+\textbf{(3)} Minimiser (si nécessaire) l'automate $\mathscr{A}_2$
+obtenu en (2) ; on appellera $\mathscr{A}_3$ l'automate minimal
+(=canonique) résultant.
+
+\begin{corrige}
+On part bien d'un automate $\mathscr{A}_2$ déterministe complet sans
+état inaccessible.  La première étape de l'algorithme de minimisation
+sépare deux classes d'états : $0',1',2'$ (non finaux) d'une part et
+$3'$ (final) de l'autre.  Ensuite on sépare $0',1'$ d'une part et $2'$
+de l'autre (car les premiers ne conduisent qu'à des états non finaux,
+tandis que $2'$ conduit à un état final par la transition
+étiquetée $c$).  L'étape suivante sépare $0'$ et $1'$ (car le premier
+ne conduit qu'à un état de la classe $\{0',1'\}$ de l'étape
+précédente, tandis que $1'$ conduit à un état de la classe $\{2'\}$
+par la transition étiquetée $b$).  On a donc séparé tous les états, ce
+qui montre que $\mathscr{A}_3 = \mathscr{A}_2$ est minimal.
+
+\emph{Remarque :} on pouvait aussi invoquer l'argument suivant :
+puisque le mot $abc$ doit être accepté et qu'aucun de ses sous-mots
+stricts ne l'est (ce qui exclut qu'il y ait une boucle dans le chemin
+d'acceptation), il faut au moins $|abc|+1 = 4$ états dans n'importe
+quel automate reconnaissant $L$.  Comme $\mathscr{A}_2$ a
+effectivement $4$ états, il est forcément minimal.
+\end{corrige}
+
+\textbf{(4)} Construire un automate $\mathscr{A}_4$ reconnaissant le
+langage $M := \Sigma^*\setminus L$ complémentaire de $L$.
+
+\begin{corrige}
+On obtient $\mathscr{A}_4$ en échangeant états finaux et non finaux
+dans $\mathscr{A}_3 = \mathscr{A}_2$, c'est-à-dire l'automate
+$\mathscr{A}_4$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state,final,accepting above] {$1'$};
+\node (q2) at (140bp,0bp) [draw,circle,state,final,accepting above] {$2'$};
+\node (q3) at (210bp,0bp) [draw,circle,state] {$3'$};
+\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2);
+\draw [->] (q2) -- node[auto] {$c$} (q3);
+\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+\textbf{(5)} En appliquant à $\mathscr{A}_4$ la méthode d'élimination
+des états, déterminer une expression rationnelle dénotant le
+langage $M$.  (Si on souhaite obtenir une expression plus compacte, il
+est recommandé de commencer l'élimination des états par ceux qui sont
+le plus loin de l'état initial.)
+
+\begin{corrige}
+On va manipuler des automates finis à transitions étiquetées par des
+expressions rationnelles (ou « RNFA »).  Dans un premier temps, on
+donne à l'automate un unique état final $F$ en faisant pointer vers
+lui une transition spontanée (i.e., étiquetée
+par $\underline{\varepsilon}$) depuis tout état qui était final, et un
+unique état initial $I$ depuis lequel on fait partir une transition
+spontanée vers $0'$.  L'état $3'$ peut être éliminé d'emblée puisqu'il
+est inutile (il n'est pas co-accessible : c'est un puits !).  Par
+ailleurs, deux transitions entre les mêmes états sont remplacées par
+une seule étiquetée par la disjonction des étiquettes (par exemple,
+les deux transitions $0'\to 0'$ étiquetées $b$ et $c$ sont remplacées
+par une seule étiquetée $b|c$).  On a donc affaire à l'automate
+suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$};
+\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$};
+\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0);
+\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a|b$} (q2);
+\draw [->] (q2) -- node[auto] {$\underline{\varepsilon}$} (qF);
+\draw [->] (q1) to[out=45,in=135] node[auto] {$\underline{\varepsilon}$} (qF);
+\draw [->] (q0) to[out=90,in=180] (70bp,60bp) to node[auto] {$\underline{\varepsilon}$} (140bp,60bp) to[out=0,in=90] (qF);
+\end{tikzpicture}
+\end{center}
+On élimine maintenant l'état $2'$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$};
+\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0);
+\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1);
+\draw [->] (q1) -- node[auto] {$\underline{\varepsilon}|b(a|b){*}$} (qF);
+\draw [->] (q0) to[out=90,in=180] (70bp,40bp) to node[auto] {$\underline{\varepsilon}$} (140bp,40bp) to[out=0,in=90] (qF);
+\end{tikzpicture}
+\end{center}
+(on a fait usage du fait évident que l'expression rationnelle
+$r\underline{\varepsilon}$ est équivalente à $r$).  On élimine
+ensuite l'état $1'$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$};
+\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0);
+\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0);
+\draw [->] (q0) -- node[auto] {$\underline{\varepsilon}|a(a|c){*}(\underline{\varepsilon}|b(a|b){*})$} (qF);
+\end{tikzpicture}
+\end{center}
+Enfin, l'élimination de l'état $0'$ conduit au RNFA ayant seulement
+deux états $I$ et $F$ reliés par une transition étiquetée par
+\[
+(b|c){*}\Big(\underline{\varepsilon}|a(a|c){*}\big(\underline{\varepsilon}|b(a|b){*}\big)\Big)
+\]
+qui est l'expression rationnelle recherchée (dénotant $M$).
+
+L'élimination des états dans l'ordre $0',1',2'$ conduirait à
+l'expression rationnelle moins compacte
+\[
+\underline{\varepsilon}\;|\;(b|c){*}\;|\;(b|c){*}a(a|c){*}\;|\;(b|c){*}a(a|c){*}b(a|b){*}
+\]
+qui est cependant sans doute plus lisible.
+
+\emph{Remarque :} le langage $M$ est aussi dénoté par l'expression
+rationnelle plus simple $(b|c){*}\,(a|c){*}\,(a|b){*}$, mais celle-ci
+ne répond pas à la question car elle ne peut pas s'obtenir par
+élimination des états à partir de $\mathscr{A}_4$.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+% NOTE: Initially copied from controle-20180322.tex
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On appelle $L = L(G)$
+le langage défini par la grammaire hors-contexte $G$ d'axiome $S$ et de
+nonterminaux $N = \{S\}$ sur l'alphabet $\Sigma$ donnée par
+\[
+\begin{aligned}
+S &\rightarrow aSbS \;|\; aS \;|\; \varepsilon\\
+\end{aligned}
+\]
+
+Les questions de cet exercice sont essentiellement indépendantes, si
+ce n'est que la question (6) fait appel à la conclusion (énoncée) des
+questions (2) à (5).
+
+\smallskip
+
+\textbf{(1)} Donner deux arbres d'analyse (pour $G$) différents du
+mot $aab$.  Que peut-on dire de la grammaire $G$ ?
+
+\begin{corrige}
+On peut proposer les arbres d'analyse suivants :\\
+% S<a.S<a.S<e.>>b.S<e.>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (42.500bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (S1) at (30.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
+\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$};  \draw (S2) -- (e0);
+\node (b0) at (60.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
+\node (S3) at (80.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S3);
+\node (e1) at (80.000bp,-50.000bp) [draw=none] {$\varepsilon$};  \draw (S3) -- (e1);
+\end{tikzpicture}
+d'une part,\hfill et
+% S<a.S<a.S<e.>b.S<e.>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (25.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (S1) at (50.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
+\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$};  \draw (S2) -- (e0);
+\node (b0) at (60.000bp,-60.000bp) [draw=none] {$b$};  \draw (S1) -- (b0);
+\node (S3) at (80.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S3);
+\node (e1) at (80.000bp,-80.000bp) [draw=none] {$\varepsilon$};  \draw (S3) -- (e1);
+\end{tikzpicture}
+d'autre part\\
+(en fait, on peut se convaincre que ce sont les seuls possibles).
+La grammaire $G$ est donc ambiguë.
+\end{corrige}
+
+L'objet des questions suivantes est de montrer que $L$ n'est pas
+rationnel.
+
+Soit $M$ le langage $\{a^i b^j : i,j\in\mathbb{N}\}$ constitué des
+mots de la forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels
+quelconques.
+
+\textbf{(2)} Donner une expression rationnelle qui dénote $M$.
+
+\begin{corrige}
+Le langage $M$ est dénoté par l'expression rationnelle $a{*}b{*}$.
+\end{corrige}
+
+Soit $P$ le langage $\{a^i b^j : i\geq j\}$ constitué des mots de la
+forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels vérifiant $i\geq
+j$ (autrement dit, les mots de $M$ qui ont au moins autant de $a$ que
+de $b$).
+
+\textbf{(3)} Montrer que $P \subseteq L$.
+
+\begin{corrige}
+Soient $i\geq j$ deux entiers naturels : on va expliquer comment
+produire le mot $a^i b^j$ selon les règles de $G$.  À partir de
+l'axiome $S$, on commence par appliquer $i-j$ fois la règle $a
+\rightarrow aS$, ce qui donne $a \Rightarrow aS \Rightarrow aaS
+\Rightarrow \cdots \Rightarrow a^{i-j} S$.  Appliquons maintenant $j$
+fois la règle $S\rightarrow aSbS$, suivie à chaque fois de
+$S\rightarrow\varepsilon$ sur le $S$ de droite : on obtient ainsi
+$a^{i-j} S \Rightarrow a^{i-j+1} S bS \Rightarrow a^{i-j+1} S b
+\Rightarrow a^{i-j+2} S b S b \Rightarrow a^{i-j+2} S bb \Rightarrow
+\cdots \Rightarrow a^i S b^j$.  Il suffit de terminer par une
+application de $S \rightarrow \varepsilon$ : on obtient ainsi une
+dérivation $S \mathrel{\Rightarrow^*} a^i b^j$ qui prouve que $a^i b^j
+\in L$.
+
+(On pouvait aussi, plus informellement, esquisser l'allure d'un arbre
+de dérivation de $a^i b^j$ un peu à la manière de l'un ou l'autre de
+ceux de la question (1), mais en appliquant $i-j$ fois la règle $a
+\rightarrow aS$ et $j$ fois la règle $S \rightarrow aSbS$.)
+\end{corrige}
+
+\textbf{(4)} Montrer que $L\cap M \subseteq P$.
+
+\begin{corrige}
+Considérons la propriété « avoir (au total) au moins autant de $a$ que
+de $b$ », ou si on veut $|\xi|_a\geq |\xi|_b$, sur un pseudo-mot $\xi$
+(un « pseudo-mot » signifiant, par définition, un mot sur $\Sigma\cup
+N = \{a,b,S\}$).  Cette propriété est vérifiée par le pseudo-mot $S$.
+Elle est préservée si on remplace $S$ par $aSbS$ ou $aS$ ou
+$\varepsilon$ puisque dans chacun de ces cas le nombre de $a$ augmente
+d'au moins autant que le nombre de $b$.  Elle est donc possédée par
+tout pseudo-mot, et en particulier tout mot, qui dérive de $S$
+selon $G$.  On vient donc de prouver que tout mot de $L$ a au moins
+autant de $a$ que de $b$.  Notamment, tout mot de $L\cap M$ est un mot
+de la forme $a^i b^j$ (par définition de $M$), et qui vérifie $i\geq
+j$ (c'est ce qu'on vient de prouver).  Il est donc dans $P$.
+\end{corrige}
+
+\textbf{(5)} Montrer que $P$ n'est pas rationnel.
+
+\begin{corrige}
+Supposons par l'absurde que $P = \{a^i b^j : i\geq j\}$ soit
+rationnel.  Appliquons le lemme de pompage pour les langages
+rationnels au langage $P$ : appelons $k$ l'entier dont le lemme de
+pompage garantit l'existence.  Considérons le mot $t := a^k b^k$ (qui
+appartient bien à $P$ et est bien de longueur $\geq k$) : il doit
+alors exister une factorisation $t = uvw$ (avec $u,v,w \in \Sigma^*$,
+non nécessairement dans $P$) pour laquelle on a
+(i) $|v|\geq 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in P$ pour
+tout $i\geq 0$.  La propriété (ii) assure que $uv$ est formé d'un
+certain nombre de répétitions de la lettre $a$ (car tout préfixe de
+longueur $\leq k$ de $a^k b^k$ est de cette forme) ; disons $u =
+a^\ell$ et $v = a^m$, si bien que $w = a^{k-\ell-m} b^k$.  La
+propriété (i) donne $m\geq 1$.  Enfin, la propriété (iii) affirme que
+le mot $uv^iw = a^{k+(i-1)m} b^k$ appartient à $P$ ; or pour $i=0$,
+ceci est faux puisque $a^{k-m} b^k$ vérifie $k-m < k$.  On a donc
+abouti à une contradiction, et c'est que $P$ n'est pas rationnel.
+\end{corrige}
+
+\textbf{(6)} Déduire des questions (2) à (5) que $L$ n'est pas
+rationnel (on explicitera très soigneusement le raisonnement).
+
+\begin{corrige}
+On a vu à la question (3) que $P \subseteq L$ ; il est par ailleurs
+trivial que $P \subseteq M$, et on a donc $P \subseteq L\cap M$.  Mais
+on a vu à la question (4) que $L\cap M \subseteq P$ : on a donc $L\cap
+M = P$.  Le langage $M$ est rationnel d'après la question (2).  Si le
+langage $L$ était lui aussi rationnel, le langage $L\cap M$
+(c'est-à-dire $P$) le serait car l'intersection de deux langages
+rationnels est rationnelle.  Or on a vu à la question (5) que $P$
+n'est pas rationnel.  C'est donc que $L$ ne l'est pas.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+% NOTE: Initially copied from controle-20210618.tex
+
+(Les deux questions suivantes sont indépendantes.)
+
+\smallskip
+
+\textbf{(1)} Le langage $\{a^n b^n c^n : n\in\mathbb{N}\}$ n'est pas
+algébrique\footnote{Ce fait est démontré dans le poly, dans la section
+  consacrée au lemme de pompage pour les langages algébriques et comme
+  illustration de ce dernier ; on ne demande pas ici de le
+  redémontrer : on peut le tenir pour admis.}.  Est-il rationnel ?
+Est-il décidable ?  Est-il semi-décidable ?  On justifiera
+soigneusement les réponses.
+
+\begin{corrige}
+Le langage proposé n'est pas rationnel car il n'est pas algébrique.
+
+Il est décidable car il est évident qu'on peut algorithmiquement d'une
+part vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci
+correspond à l'expression rationnelle $a{*}b{*}c{*}$, c'est faisable
+par automate fini) et d'autre part vérifier qu'il a autant de $a$ que
+de $b$ que de $c$.
+
+Étant décidable, il est notamment semi-décidable.
+\end{corrige}
+
+\smallskip
+
+\textbf{(2)} 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.
+
+On considère l'ensemble $J$ des triplets $(e_1,e_2,x)$ tels que
+$(e_1,x) \in H$ et $(e_2,x) \not\in H$.  Autrement dit, le programme
+$e_1$ termine en temps fini quand on l'exécute sur l'entrée $x$ mais
+le programme $e_2$, lui, ne termine pas sur cette même entrée.
+L'ensemble $J$ est-il décidable ?  Semi-décidable ?  On justifiera
+soigneusement.
+
+\begin{corrige}
+L'ensemble $J$ n'est pas semi-décidable.
+
+Pour le montrer, supposons par l'absurde qu'on dispose d'un algorithme
+$T$ qui semi-décide $J$ (où « semi-décider » un ensemble $Z$
+signifie : terminer en renvoyant $1$ (=vrai) si l'entrée $z$ fournie
+appartient à $Z$, et ne pas terminer sinon).  Fixons une fois pour
+toutes (le code d')un programme $f$ qui, donnée une entrée $x$,
+termine immédiatement (en ignorant $x$).  Alors trivialement $(f,x)
+\in H$ quel que soit $x$ ; donc, par définition de $J$, on a $(f,e,x)
+\in J$ si et seulement si $(e,h) \not \in H$.
+
+On considère alors l'algorithme $T'$, défini de la manière suivante :
+donnés $(e,x)$, on applique l'algorithme $T$ (qu'on a supposé exister)
+au triplet $(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in
+J$), on renvoie $1$ (sinon, bien sûr, on ne termine jamais).  Par
+construction, $T'$ termine en renvoyant $1$ sur l'entrée $(e,x)$ si
+$(f,e,x) \in J$, c'est-à-dire $(e,x) \not\in H$, et sinon il ne
+termine pas.  Ceci signifie que $T'$ semi-décide le complémentaire
+de $H$.
+
+Or le complémentaire de $H$ n'est pas semi-décidable (car si le
+complémentaire de $H$ était semi-décidable, on aurait à la fois $H$ et
+son complémentaire semi-décidables, donc $H$ serait décidable, et on
+sait qu'il ne l'est pas), donc un tel algorithme $T'$ ne peut pas
+exister.  C'est une contradiction : $J$ n'est donc pas semi-décidable.
+
+\textit{A fortiori}, $J$ n'est pas décidable.
+\end{corrige}
+
+
+%
+%
+%
+\end{document}
-- 
cgit v1.2.3