%% 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}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\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\relax\else\egroup\fi\par}
\newenvironment{commentaire}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
{{\hbox{}\nobreak\hfill\maltese}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
% 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{7 février 2017}
\maketitle

%% {\footnotesize
%% \immediate\write18{sh ./vc > vcline.tex}
%% \begin{center}
%% Git: \input{vcline.tex}
%% \end{center}
%% \immediate\write18{echo ' (stale)' >> vcline.tex}
%% \par}

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Les exercices sont totalement indépendants.  Ils pourront être traités
dans un ordre quelconque, mais on demande de faire apparaître de façon
très visible dans les copies où commence chaque exercice.

\medbreak

Le sujet étant long pour le temps imparti, il ne sera pas nécessaire
de traiter toutes les questions pour obtenir la totalité des points.

\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} : 8 points par exercices

\ifcorrige
%Ce corrigé comporte 10 pages (page de garde incluse)
\else
Cet énoncé comporte 4 pages (page de garde incluse)
\fi

\pagebreak


%
%
%

\exercice

On considère l'automate fini $M$ sur l'alphabet $\Sigma = \{a,b\}$
représenté par la figure suivante :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$};
\node (Y) at (80bp,0bp) [draw,circle,state,final] {$Y$};
\node (A1) at (-40bp,50bp) [draw,circle,state] {$A\phantom{'}$};
\node (A2) at (40bp,50bp) [draw,circle,state] {$A'$};
\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B\phantom{'}$};
\node (B2) at (40bp,-50bp) [draw,circle,state] {$B'$};
\draw[->] (X) -- node[auto]{$\varepsilon$} (A1);
\draw[->] (X) -- node[auto,below left]{$\varepsilon$} (B1);
\draw[->] (A1) -- node[auto]{$a$} (A2);
\draw[->] (B1) -- node[auto]{$b$} (B2);
\draw[->] (A1) to[loop above] node[auto]{$b$} (A1);
\draw[->] (A2) to[loop above] node[auto]{$b$} (A2);
\draw[->] (B1) to[loop below] node[auto]{$a$} (B1);
\draw[->] (B2) to[loop below] node[auto]{$a$} (B2);
\draw[->] (A2) -- node[auto]{$\varepsilon$} (Y);
\draw[->] (B2) -- node[auto,below right]{$\varepsilon$} (Y);
\end{tikzpicture}
\end{center}

(0) De quelle sorte d'automate s'agit-il ?  (Autrement dit : est-il
déterministe ou non ? avec transitions spontanées ou non ?)

(1a) Décrire brièvement, en français, le langage $L$ reconnu
(=accepté) par l'automate $M$, puis donner une expression
rationnelle qui le dénote.  (On pourra préférer traiter la question
(1b) d'abord.)

(1b) Pour chacun des mots suivants, dire s'ils sont dans $L$ ou non :
$\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$.
(Note : il est recommandé de réutiliser ces mots pour vérifier
rapidement les réponses aux questions suivantes et ainsi détecter
d'éventuelles erreurs lors des transformations des automates.)

(2) Éliminer les transitions spontanées de l'automate $M$.  (On
supprimera les états devenus inutiles.)  On appellera $M_2$ l'automate
obtenu.

(3) Déterminiser l'automate $M_2$ obtenu en (2), si nécessaire.  (On
demande un automate déterministe complet.)  On appellera $M_3$
l'automate déterminisé.

Pour simplifier le travail du correcteur, on demande de représenter
$M_3$ de sorte que les transitions étiquetées par $a$ soient, dans la
mesure du possible, horizontales de la gauche vers la droite, et
celles étiquetées par $b$, verticales du haut vers le bas.

(4) Minimiser l'automate $M_3$ obtenu en (3), si nécessaire
(justifier).

(5) Donner un automate (de n'importe quelle sorte) qui reconnaît le
langage $\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$.

(6) Décrire brièvement, en français, ce langage
complémentaire $\overline{L}$.

(7) (Question bonus, plus longue, à ne traiter qu'en dernier.)
Calculer une expression rationnelle qui dénote ce langage
complémentaire $\overline{L}$.  (Ne pas hésiter à introduire des
notations intermédiaires.)

\begin{corrige}
(0) L'automate $M$ est un automate fini non-déterministe à transitions
  spontanées, ou ε-NFA (le concept d'« automate déterministe à
  transitions spontanées » n'aurait tout simplement pas de sens).

\smallbreak

(1a) Le chemin par les états $X,A,A',Y$ accepte les mots exactement
un $a$, c'est-à-dire le langage dénoté par $b{*}ab{*}$.  Le chemin par
les états $X,B,B',Y$ accepte les mots comportant exactement un $b$,
c'est-à-dire le langage dénoté par $a{*}ba{*}$.  L'automate $M$ dans
son ensemble accepte les mots comportant exactement un $a$ ou
(inclusif) exactement un $b$ (i.e. $L = \{w\in\Sigma^* : |w|_a = 1
\penalty0\ \textrm{ou}\penalty0\ |w|_b = 1\}$ si $|w|_x$ désigne le
nombre total d'occurrences de la lettre $x$ dans le mot $w$).  C'est
le langage dénoté par l'expression rationnelle $b{*}ab{*} | a{*}ba{*}$
(nous notons ici et ailleurs $|$ pour la disjonction, qu'on peut aussi
noter $+$).

(1b) Parmi les mots proposés, $a$, $b$, $ab$ et $aab$ appartiennent à
$L$, tandis que $\varepsilon$, $aa$, $aabb$, $abab$ et $ababa$ n'y
appartiennent pas.

\smallbreak

(2) La ε-fermeture (arrière) de l'état $X$ est $\{X,A,B\}$ ; la
ε-fermeture de l'état $A'$ est $\{A',Y\}$ et celle de l'état $B'$ est
$\{B',Y\}$ ; les autres états sont leur propre ε-fermeture (i.e.,
celle-ci est un singleton).  L'élimination des transitions spontanées
conduit donc à l'automate $M_2$ suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$};
\node (A1) at (-40bp,50bp) [draw,circle,state] {$A\phantom{'}$};
\node (A2) at (40bp,50bp) [draw,circle,state,final] {$A'$};
\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B\phantom{'}$};
\node (B2) at (40bp,-50bp) [draw,circle,state,final] {$B'$};
\draw[->] (X) -- node[auto]{$b$} (A1);
\draw[->] (X) -- node[auto,below left]{$a$} (B1);
\draw[->] (X) -- node[auto,below right]{$a$} (A2);
\draw[->] (X) -- node[auto,above right]{$b$} (B2);
\draw[->] (A1) -- node[auto]{$a$} (A2);
\draw[->] (B1) -- node[auto]{$b$} (B2);
\draw[->] (A1) to[loop above] node[auto]{$b$} (A1);
\draw[->] (A2) to[loop above] node[auto]{$b$} (A2);
\draw[->] (B1) to[loop below] node[auto]{$a$} (B1);
\draw[->] (B2) to[loop below] node[auto]{$a$} (B2);
\end{tikzpicture}
\end{center}
(On a supprimé l'état $Y$ qui est devenu inutile car aucune transition
non-spontanée n'y conduit.)

\smallbreak

(3) L'algorithme de déterminisation conduit à l'automate $M_3$ suivant
où, pour plus de lisibilité, les états finaux ont été marqués en les
entourant deux fois plutôt que par une flèche sortante :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$\{X\}$};
\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$\{A',B\}$};
\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$\{B\}$};
\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A,B'\}$};
\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A',B'\}$};
\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{B'\}$};
\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$\{A\}$};
\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$\{A'\}$};
\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$\varnothing$};
\draw[->] (s00) -- node[auto]{$a$} (s01);
\draw[->] (s01) -- node[auto]{$a$} (s02);
\draw[->] (s10) -- node[auto]{$a$} (s11);
\draw[->] (s11) -- node[auto]{$a$} (s12);
\draw[->] (s20) -- node[auto]{$a$} (s21);
\draw[->] (s21) -- node[auto]{$a$} (s22);
\draw[->] (s02) to[loop right] node[auto]{$a$} (s02);
\draw[->] (s12) to[loop right] node[auto]{$a$} (s12);
\draw[->] (s22) to[loop right] node[auto]{$a$} (s22);
\draw[->] (s00) -- node[auto]{$b$} (s10);
\draw[->] (s10) -- node[auto]{$b$} (s20);
\draw[->] (s01) -- node[auto]{$b$} (s11);
\draw[->] (s11) -- node[auto]{$b$} (s21);
\draw[->] (s02) -- node[auto]{$b$} (s12);
\draw[->] (s12) -- node[auto]{$b$} (s22);
\draw[->] (s20) to[loop below] node[auto]{$b$} (s20);
\draw[->] (s21) to[loop below] node[auto]{$b$} (s21);
\draw[->] (s22) to[loop below] node[auto]{$b$} (s22);
\end{tikzpicture}
\end{center}

Pour la commodité de la suite de la correction, on renomme les états
de cet automate $M_3$ de la façon suivante :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$01$};
\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$02$};
\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$10$};
\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$11$};
\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$12$};
\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$20$};
\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$21$};
\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$22$};
\draw[->] (s00) -- node[auto]{$a$} (s01);
\draw[->] (s01) -- node[auto]{$a$} (s02);
\draw[->] (s10) -- node[auto]{$a$} (s11);
\draw[->] (s11) -- node[auto]{$a$} (s12);
\draw[->] (s20) -- node[auto]{$a$} (s21);
\draw[->] (s21) -- node[auto]{$a$} (s22);
\draw[->] (s02) to[loop right] node[auto]{$a$} (s02);
\draw[->] (s12) to[loop right] node[auto]{$a$} (s12);
\draw[->] (s22) to[loop right] node[auto]{$a$} (s22);
\draw[->] (s00) -- node[auto]{$b$} (s10);
\draw[->] (s10) -- node[auto]{$b$} (s20);
\draw[->] (s01) -- node[auto]{$b$} (s11);
\draw[->] (s11) -- node[auto]{$b$} (s21);
\draw[->] (s02) -- node[auto]{$b$} (s12);
\draw[->] (s12) -- node[auto]{$b$} (s22);
\draw[->] (s20) to[loop below] node[auto]{$b$} (s20);
\draw[->] (s21) to[loop below] node[auto]{$b$} (s21);
\draw[->] (s22) to[loop below] node[auto]{$b$} (s22);
\end{tikzpicture}
\end{center}
Ici, l'état $0\bullet$ signifie que l'automate n'a pas rencontré
de $a$, l'état $1\bullet$ qu'il en a rencontré exactement un, et
l'état $2\bullet$ qu'il en a rencontré au moins deux ; les états
$\bullet0$, $\bullet1$ et $\bullet2$ ont la même signification pour la
lettre $b$.

\smallbreak

(4) L'automate $M_3$ est déjà minimal.  En effet, l'algorithme de
minimisation commence par séparer les classes $\{01,10,11,12,21\}$
(états finaux) et $\{00,02,20,22\}$ (états non-finaux) ; ensuite, la
transition étiquetée par $a$ sépare la classe $\{01,10,11,12,21\}$ en
$\{01,21\}$ (qui vont vers un état non-final) et $\{10,11,12\}$ (qui
vont vers un état final), et la classe $\{00,02,20,22\}$ en
$\{00,20\}$ (qui vont vers un état final) et $\{02,22\}$ (qui vont
vers un non-final).  La transition étiquetée par $b$ sépare ensuite en
deux chacune des trois classes $\{00,20\}$, $\{01,21\}$ et $\{02,22\}$
(car le premier élément va dans la classe $\{10,11,12\}$ tandis que le
second reste dans la même classe) et sépare en trois la classe
$\{10,11,12\}$.  On a donc séparé chacun des états.

\smallbreak

(5) Pour reconnaître le complémentaire du langage reconnu par un
automate fini déterministe complet, il suffit d'échanger états finaux
et non-finaux : on peut donc prendre l'automate dessiné en (3) avec,
cette fois, la convention que les états simplement entourés sont
finaux (et les doublement entourés sont non-finaux).
Appelons-le $M_5$.

\emph{Attention :} échanger états finaux et non-finaux ne marche pas
pour reconnaître le complémentaire du langage reconnu par un automate
non-déterministe ou incomplet (car la négation de « il existe un
chemin qui va vers un état final » est « aucun chemin ne va vers un
état final » et pas « il existe un chemin qui va vers un état
non-final »).

\smallbreak

(6) Puisque $L$ est le langage formé des mots comportant exactement un
$a$ ou (inclusif) exactement un $b$, son complémentaire $\overline{L}$
est formé des mots ayant un nombre différent de $1$ de $a$ \emph{et}
un nombre différent de $1$ de $b$ ; si on préfère, il s'agit du
langage comportant ($0$ ou au moins $2$ fois la lettre $a$) \emph{et}
($0$ ou au moins $2$ fois la lettre $b$).

\smallbreak

(7) L'élimination des états n'est pas trop complexe car l'automate
$M_5$ a très peu de boucles.  Éliminons simultanément tous les états
non-finaux ($01$, $10$, $11$, $12$ et $21$), et profitons-en pour
créer un nouvel (et unique) état final $F$ :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
\node (s02) at (100bp,0bp) [draw,rounded corners,state] {$02$};
\node (s20) at (0bp,-60bp) [draw,rounded corners,state] {$20$};
\node (s22) at (100bp,-60bp) [draw,rounded corners,state] {$22$};
\node (F) at (160bp,-60bp) [draw,circle,state,final] {$F$};
\draw[->] (s00) -- node[auto]{$aa$} (s02);
\draw[->] (s20) -- node[auto]{$ab{*}a$} (s22);
\draw[->] (s02) to[loop above] node[auto]{$a$} (s02);
\draw[->] (s00) -- node[auto]{$bb$} (s20);
\draw[->] (s02) -- node[auto]{$ba{*}b$} (s22);
\draw[->] (s20) to[loop left] node[auto]{$b$} (s20);
\draw[->] (s22) to[loop below] node[auto]{$a|b$} (s22);
\draw[->] (s22) -- node[auto]{$\varepsilon$} (F);
\draw[->] (s00) -- node[auto]{$r$} (s22);
\draw[->,out=0,in=90] (s02) to node[auto]{$\varepsilon$} (F);
\draw[->,out=270,in=270] (s20) to node[auto,below]{$\varepsilon$} (F);
\draw[->] (s00) to[out=45,in=180] (100bp,40bp) to[out=0,in=45] node[auto,above]{$\varepsilon$} (F);
\end{tikzpicture}
\end{center}
où $r := abaa{*}b \,|\, abbb{*}a \,|\, baaa{*}b \,|\, babb{*}a$
(correspondant aux quatre façons de passer de $00$ à $22$ dans le
graphe ci-dessus).  Éliminons l'état $02$ et l'état $20$ :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
\node (s22) at (100bp,-60bp) [draw,rounded corners,state] {$22$};
\node (F) at (160bp,-60bp) [draw,circle,state,final] {$F$};
\draw[->] (s22) -- node[auto]{$\varepsilon$} (F);
\draw[->] (s22) to[loop above] node[auto]{$a|b$} (s22);
\draw[->] (s00) -- node[auto]{$r'$} (s22);
\draw[->,out=0,in=90] (s00) to node[auto]{$\varepsilon|aaa{*}|bbb{*}$} (F);
\end{tikzpicture}
\end{center}
où $r' := r \penalty0\,|\, aaa{*}ba{*}b \penalty0\,|\, bbb{*}ab{*}a =
abaa{*}b \penalty0\,|\, abbb{*}a \penalty0\,|\, baaa{*}b
\penalty0\,|\, babb{*}a \penalty0\,|\, aaa{*}ba{*}b \penalty0\,|\,
bbb{*}ab{*}a$.  On obtient finalement l'expression rationnelle
suivante pour $\overline{L}$ :
\[
\varepsilon\,|\,aaa{*}\,|\,bbb{*}\,|\,(abaa{*}b \,|\,
abbb{*}a \,|\, baaa{*}b \,|\, babb{*}a
\,|\, aaa{*}ba{*}b \,|\, bbb{*}ab{*}a)(a|b){*}
\]
Pour comprendre cette expression rationnelle, la disjonction de plus
haut niveau correspond aux quatre possibilités : (i) $0$ fois la
lettre $a$ et $0$ fois la lettre $b$, (ii) au moins $2$ fois la lettre
$a$ et $0$ fois la lettre $b$, (iii) $0$ fois la lettre $a$ et au
moins $2$ fois la lettre $b$, et (iv) au moins $2$ fois la lettre $a$
et au moins $2$ fois la lettre $b$.  Pour mieux comprendre
l'expression du cas (iv), on peut remarquer que $abaa{*}b
\penalty0\,|\, baaa{*}b \penalty0\,|\, aaa{*}ba{*}b$ dénote le langage
formé des mots comportant au moins deux $a$ et exactement deux $b$ et
qui finissent par un $b$, et symétriquement $abbb{*}a \penalty0\,|\,
babb{*}a \penalty0\,|\,bbb{*}ab{*}a$ dénote le langage formé des mots
comportant au moins deux $b$ et exactement deux $a$ et qui finissent
par un $a$ : l'expression du cas (iv) correspond donc à écrire un mot
ayant au moins deux $a$ et au moins deux $b$ comme le premier préfixe
qui vérifie cette propriété suivi d'un suffixe quelconque.  (On
pouvait utiliser directement ce raisonnement pour produire
l'expression.)
\end{corrige}

\begin{commentaire}
Cet exercice a été noté sur $9$ (dans une note finale sur $20$).

(0) De nombreuses copies parlent d'« automate déterministe à
    transitions spontanées ».  Cette notion n'existe tout simplement
  pas et n'a pas de sens.

(1b) De nombreuses erreurs dans la manipulation des automates, qui
  auraient pu être attrapées par l'utilisation ce ces mots-tests ne
  l'ont pas été, et c'est dommage (ces erreurs ont été comptées plus
  sévèrement).

(3) La consigne sur la présentation de l'automate a été presque
  universellement ignorée (pourquoi ?).  Plus grave, certains ont
  oublié de fournir un automate déterministe \emph{complet} (pourtant,
  l'algorithme de déterminisation fournit assez naturellement un
  automate complet).

(5) De nombreuses copies essaient de construire un automate
  reconnaissant $\overline{L}$ autrement qu'en échangeant états finaux
  et non-finaux dans un automate \underline{déterministe complet}.

(6) Beaucoup croient à tort que la négation de « contenir
    unique $a$ ou bien contenir un unique $b$ » est « être le mot vide
    ou bien contenir au moins deux $a$ ou bien au moins deux $b$ » :
  le mot $aab$ de la question (1b) aurait dû permettre d'éviter cette
  erreur.  À l'inverse, certains croient que cette négation est « être
    le mot vide ou bien contenir au moins deux $a$ \emph{et} au moins
    deux $b$ » : le mot $aa$ aurait dû permettre d'éviter cette
  erreur.  Enfin, beaucoup de copies utilisent une description
  tellement vague qu'il est impossible de savoir ce qu'elle veut dire
  (par exemple « les mots pour lesquels le nombre d'occurrence des
    lettres qui s'y trouvent est supérieur ou égal à $2$ »).
\end{commentaire}


%
%
%

\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
informelle.

(1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe
un algorithme $A_1$ qui, étant donnée une expression rationnelle $r$
sur $\Sigma$, décide si le langage $L_r$ dénoté par $r$ est différent
du langage $\Sigma^*$ de tous les mots sur $\Sigma$.  (Autrement dit,
l'algorithme $A_1$ doit prendre en entrée une expression rationnelle
$r$, terminer en temps fini, et répondre « vrai » s'il existe un mot
$w\in\Sigma^*$ tel que $w\not\in L_r$ et « faux » si $L_r = \Sigma^*$.
On ne demande pas que l'algorithme soit efficace.)

(2) Expliquer pourquoi il existe un algorithme $A_2$ qui, étant donnée
une grammaire hors contexte $G$ sur $\Sigma$, « semi-décide » si le
langage $L_G$ engendré par $G$ est différent du langage $\Sigma^*$ de
tous les mots.  (« Semi-décider » signifie que l'algorithme $A_2$ doit
prendre en entrée une grammaire hors contexte $G$, terminer en temps
fini en répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que
$w\not\in L_G$, et ne pas terminer\footnote{On peut admettre qu'il
  termine parfois en répondant « faux », mais ce ne sera pas utile.}
si $L_G = \Sigma^*$.)  Indication : on peut tester tous les mots
possibles.

(3) Expliquer pourquoi il existe un algorithme $A_3$ comme suit : on
lui fournit en entrée un algorithme $T$ qui décide un langage $L_T
\subseteq \Sigma^*$ (c'est-à-dire que $T$ termine toujours en temps
fini quand on lui présente un mot sur $\Sigma$, et répond « vrai » ou
« faux », et $L_T$ est le langage des mots sur lesquels il répond
« vrai »), et l'algorithme $A_3$ doit semi-décider si $L_T$ est
différent de $\Sigma^*$.  (C'est-à-dire que $A_3$ doit terminer en
répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que $w\not\in
L_T$, et ne pas terminer si $L_T = \Sigma^*$.)  Indication : la même
approche permet de traiter les questions (2) et (3).

(4) Expliquer pourquoi il \emph{n'existe pas} d'algorithme $A_4$ qui,
dans les mêmes conditions que $A_3$, décide (au lieu de seulement
semi-décider) si $L_T$ est différent de $\Sigma^*$.  (C'est-à-dire que
$A_4$ est censé terminer toujours, et répondre « vrai » s'il existe un
mot $w\in\Sigma^*$ tel que $w\not\in L_T$, et « faux » si $L_T =
\Sigma^*$.)  Indication : expliquer comment on pourrait utiliser un
tel $A_4$ pour résoudre le problème de l'arrêt, en cherchant à
fabriquer un $T$ qui rejette un mot précisément si un programme donné
s'arrête.

\begin{corrige}
(1) Donnée une expression rationnelle $r$, on sait qu'on peut
  algorithmiquement fabriquer un automate fini non-déterministe à
  transitions spontanées qui reconnaît exactement le langage $L_r$
  dénoté par $r$, et ensuite éliminer les transitions spontanées et
  déterminiser l'automate pour obtenir un automate fini déterministe
  complet reconnaissant $L_r$.  Sur un tel automate, savoir si $L_r
  \neq \Sigma^*$ est trivial : dès lors qu'il existe un état $q$
  non-final accessible, il existe un mot rejeté par l'automate (i.e.,
  n'appartenant pas à $L_r$), à savoir le mot lu en suivant les
  étiquettes d'un chemin quelconque de l'état initial $q_0$
  jusqu'à $q$, et inversement, si tous les états sont finaux, il est
  trivial que l'automate accepte tous les mots.  (On pouvait aussi
  minimiser l'automate et le comparer à l'automate minimal trivial qui
  reconnaît le langage $\Sigma^*$.)

\smallbreak

(2) On sait qu'il existe un algorithme qui, donnée une grammaire
hors-contexte $G$ et un mot $w$, décide si $w \in L_G$.  Pour
semi-décider s'il existe un $w$ tel que $w \not\in L_G$, il suffit de
tester tous les mots possibles : plus exactement, on construit un
algorithme $A_2$ qui effectue une boucle infinie sur tous les
$w\in\Sigma^*$ (il est évidemment algorithmiquement faisable
d'énumérer tous les mots sur $\Sigma$) et, pour chacun, teste si $w
\in L_G$, et si ce n'est pas le cas, termine immédiatement en
répondant « vrai » (on a trouvé un $w$ n'appartenant pas à $L_G$),
tandis que si c'est le cas, l'algorithme $A_2$ ne terminera jamais.

\smallbreak

(3) On procède exactement comme en (2) : par hypothèse on dispose d'un
algorithme $T$ qui, donné un mot $w$, décide si $w \in L_T$.  Pour
semi-décider s'il existe un $w$ tel que $w \not\in L_T$, il suffit de
tester tous les mots possibles : plus exactement, on construit un
algorithme $A_3$ qui effectue une boucle infinie sur tous les
$w\in\Sigma^*$ et, pour chacun, teste si $w \in L_T$ (en lançant
l'algorithme $T$ qui, par hypothèse, termine toujours), et si ce n'est
pas le cas, termine immédiatement en répondant « vrai » (on a trouvé
un $w$ n'appartenant pas à $L_T$), tandis que si c'est le cas,
l'algorithme $A_3$ ne terminera jamais.

\smallbreak

(4) Supposons par l'absurde qu'on dispose d'un algorithme $A_4$ comme
on vient de dire, et montrons pour arriver à une contradiction qu'on
peut s'en servir pour résoudre le problème de l'arrêt.  On se donne
donc un algorithme $S$ et une entrée $x$ de $S$ et on cherche à savoir
(en utilisant $A_4$) si $S$ termine sur l'entrée $x$.  Pour cela, on
va construire un $T$ auquel appliquer $A_4$.

Voici une solution possible : donné un mot $w \in \Sigma^*$, le
programme $T$ ne considère que la longueur $|w|$ de $w$, et lance
(=simule) l'exécution de $S$ sur l'entrée $x$ pour au plus $|w|$
étapes : si l'exécution termine dans le temps imparti, alors $T$
rejette le mot $w$, sinon, il l'accepte (dans tous les cas, $T$
termine et répond « vrai » ou « faux », donc il est une entrée
légitime à $A_4$).  Cette construction fait que $L_T$ rejette au moins
un mot précisément lorsque $S$ termine sur $x$ : si au contraire $S$
ne termine pas sur $x$, alors $L_T = \Sigma^*$.  L'utilisation de
$A_4$ sur $T$ permet donc de savoir algorithmiquement si $S$ termine
sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt.

\textit{Variante de la même idée :} on appelle « trace d'exécution » de $S$ sur
$x$ un mot $w$ qui code le calcul complet de l'exécution de $S$ sur
$x$ (par exemple, si on voit $S$ comme une machine de Turing, l'état
courant et le contenu du ruban à chaque étape), du début à l'arrêt.
Une telle trace d'exécution existe donc précisément si $S$ termine
sur $x$.  Or il est visiblement décidable de savoir si un mot $w$
donné est une trace d'exécution (il suffit de vérifier qu'à chaque
étape la machine a bien fait ce qu'elle devait faire).  On peut donc
écrire un algorithme $T$ qui termine toujours et accepte précisément
les mots qui \emph{ne sont pas} une trace d'exécution de $S$ sur $x$.
Le fait que $L_T$ soit différent de $\Sigma^*$ signifie alors
exactement qu'une trace d'exécution existe, donc que $S$ termine
sur $x$.  Ainsi l'utilisation de $A_4$ permet de savoir
algorithmiquement si $S$ termine sur $x$, ce qui contredit
l'indécidabilité du problème de l'arrêt.
\end{corrige}

\begin{commentaire}
Cet exercice a été noté sur $7$ (dans une note finale sur $20$).

Il a été très peu traité, ce qui est dommage car la question (1)
consistait essentiellement à dire « oui : on a vu dans le cours tous
  les algorithmes nécessaires » et rapportait $2$ points à elle seule.
\end{commentaire}



%
%
%

\exercice

On considère la grammaire hors-contexte $G$ d'axiome $S$ et de
nonterminaux $N = \{S, T\}$ sur l'alphabet $\Sigma = \{a,b,c\}$
donnée par
\[
\begin{aligned}
S &\rightarrow TS \;|\; \varepsilon\\
T &\rightarrow aSbSc\\
\end{aligned}
\]
On notera $L(S) = L_G$ le langage qu'elle engendre, et $L(T)$ le
langage des mots qui dérivent de $T$ (c'est-à-dire, si on préfère, le
langage engendré par la grammaire identique à $G$ mais ayant $T$ pour
axiome).

(0) Donner quelques exemples de mots de $L(S)$ et de $L(T)$ (au
moins deux de chaque).

(1) Expliquer brièvement pourquoi $L(S)$ est l'ensemble des mots de la
forme $u_1\cdots u_k$ avec $u_i \in L(T)$, et pourquoi $L(T)$ est
l'ensemble des mots de la forme $awbw'c$ avec $w,w'\in L(S)$.  (Par
conséquent, $L(T)$ est l'ensemble des mots de la forme $a u_1 \cdots
u_k b u'_1\cdots u'_{\ell} c$ avec
$u_1,\ldots,u_k,u'_1,\ldots,u'_{\ell} \in L(T)$.)

(2) Comment exprimer $L(S)$ à partir de $L(T)$ au moyen d'une ou
plusieurs opérations rationnelles\footnote{C'est-à-dire : union,
  concaténation, étoile de Kleene.} ?  Y a-t-il inclusion de l'un dans
l'autre ?

(3) Montrer que tout mot $w$ appartenant à $L(S)$ ou à $L(T)$ a le
même nombre de $a$, de $b$ et de $c$, c'est-à-dire $|w|_a = |w|_b =
|w|_c$ où $|w|_x$ désigne le nombre total d'occurrences de la
lettre $x$ dans le mot $w$.

(4) Montrer par récurrence sur la longueur $|u|$ d'un mot $u\in
L(T)$ que si $v$ est un préfixe de $u$ de longueur $0<|v|<|u|$,
alors on a $|v|_c < |v|_a$.  Pour cela, on pourra écrire $u$ sous la
forme $a u_1 \cdots u_k b u'_1\cdots u'_{\ell} c$ obtenue en (1),
considérer un préfixe\footnote{\label{prefix-note}On signale à toutes
  fins utiles le fait évident suivant : un préfixe non vide de $t_1
  \cdots t_n$ où $t_1,\ldots,t_n \in\Sigma^*$ s'écrit sous la forme
  $t_1\cdots t_{i-1} y$ où $y\neq\varepsilon$ est un préfixe
  de $t_i$.} d'une telle expression, et appliquer la question (3) et
l'hypothèse de récurrence.

(5) Déduire des questions (3) et (4) que si $u \in L(T)$ et si $v$ est
un préfixe de $u$ autre que $u$ lui-même, alors\footnote{L'énoncé
  d'origine comportait par erreur la question $u \not\in L(T)$ ici.}
$v \not\in L(T)$.  En déduire que $u\in L(T)$ et $z \in \Sigma^*$,
alors $u$ est l'\emph{unique} préfixe du mot $w := uz$ qui appartienne
à $L(T)$ (autrement dit, aucun préfixe de $w$ de longueur ${<}|u|$ ni
${>}|u|$ n'appartient à $L(T)$).

(6) En déduire que si un mot $w$ s'écrit $w = u_1\cdots u_k$ avec
$u_1,\ldots,u_k \in L(T)$ alors cette factorisation est unique.
(Comment peut-on caractériser $u_1$ comme préfixe de $w$ ?)  Montrer
de même la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots
u'_\ell$ (on pourra noter que $bz\not\in L(T)$ quel que
soit $z\in\Sigma^*$).

(7) En déduire que la grammaire $G$ est inambiguë.

\begin{corrige}
(0) Les mots $abc$ et $aabcbc$ et $ababcc$ appartiennent à $L(T)$.
  Les mots $\varepsilon$ et $abc$ et $abcabc$ appartiennent à $L(S)$.

\smallbreak

(1) En bref : il s'agit simplement d'une reformulation des règles de
  la grammaire.  En plus détaillé : si on considère un arbre d'analyse
  d'un mot $w$ de $L(S)$, soit il est la dérivation triviale du mot
  vide, soit sa racine a deux fils étiquetés $T$ et $S$, l'un dont
  descend un arbre d'analyse d'un mot $u_1$ de $L(T)$ et l'autre
  dont descend un arbre d'analyse d'un autre mot $w'$ de $L(S)$, avec
  $w = u_1 w'$ : en répétant cette remarque jusqu'à tomber sur le mot
  vide, on voit que $w = u_1 u_2 \cdots u_k$ pour des mots $u_i \in
  L(T)$ ; et réciproquement, tout mot de cette forme a un arbre
  d'analyse dans $G$ obtenu en mettant ensemble les arbres d'analyse
  des $u_i$ (en les associant deux par deux par la droite).  Le cas
  d'un mot $u$ de $L(T)$ est plus simple : son arbre d'analyse donne
  directement une écriture sous la forme $awbw'c$ avec $w,w'$ les mots
  analysés par les arbres qui descendent des deux fils étiquetés $S$
  de la racine (étiquetée $T$).

\smallbreak

(2) La description faite en (1) signifie notamment que $L(S) =
L(T)^*$ où « $*$ » est l'étoile de Kleene.  (Si on veut, la règle $S
\rightarrow TS \,|\, \varepsilon$ peut s'interpréter comme $S
\rightarrow T{*}$.)  En particulier, on a $L(T) \subseteq L(S)$.

\smallbreak

(3) La propriété $|\gamma|_a = |\gamma|_b = |\gamma|_c$ (ici $\gamma
\in (\Sigma\cup N)^*$) est vérifiée pour $\gamma = S$ et elle est
préservée par toute dérivation immédiate pour $G$ puisqu'elle est
préservée en remplaçant $S$ par $TS$ ou par le mot vide et en
remplaçant $T$ par $aSbSc$.  Elle est donc vérifiée pour tout mot de
$L(S)$ (et en particulier, pour tout mot de $L(T)$), ce qu'il fallait
démontrer.

\textit{Autre possibilité :} il suffit de montrer $|w|_a = |w|_b =
|w|_c$ pour tout mot $w\in L(S)$ (puisque $L(T) \subseteq L(S)$) : on
va procéder par récurrence sur la longueur $|w|$.  D'après (1), on
peut écrire $w = u_1\cdots u_k$ avec $u_i\in L(T)$ : si $k>1$, alors
chaque $u_i$ est de longueur strictement plus petite, donc l'hypothèse
de récurrence assure que la propriété est vraie pour eux, donc elle
l'est pour $w$ car $|w|_x = \sum_{i=1}^k |u_i|_x$ pour chaque
$x\in\{a,b,c\}$.  Reste le cas $k=1$, c'est-à-dire, $w\in L(T)$ : mais
on a alors (toujours d'après (1)) $w = avbv'c$ avec $v,v'\in L(S)$ qui
sont de longueur strictement plus petite que $w$, donc l'hypothèse de
récurrence assure que la propriétée st vraie pour $v$ et $v'$, et
comme $|w|_x = 1 + |v|_x + |v'|_x$ pour chaque $x\in\{a,b,c\}$, on a
la propriété voulue pour $w$.

\smallbreak

(4) On procède par récurrence sur $|u|$, ce qui permet de supposer la
propriété déjà connue pour tout préfixe $v$ d'un mot de longueur
strictement plus courte que $u$.  Si $v$ est un préfixe d'un mot $u
\in L(T)$, qu'on peut écrire sous la forme $u = a u_1 \cdots u_k b
u'_1\cdots u'_{\ell} c$, et si $0<|v|<|u|$, on a soit $v = a u_1
\cdots u_{i-1} y$ où $y \neq \varepsilon$ est un préfixe de $u_i$,
soit $v = a u_1\cdots u_k b u'_1\cdots u'_{i-1} y$ où $y \neq
\varepsilon$ est un préfixe de $u'_i$.  Dans tous les cas, tous les
facteurs $t$ qui interviennent dans cette écriture vérifient $|t|_c
\leq |t|_a$ : c'est trivial pour $a$ et $b$, c'est le cas pour chaque
$u_j$ par la question (3), et pour $y$ cela découle soit de
l'hypothèse de récurrence (lorsque $|y|<|u_i|$ resp. $|y|<|u'_i|$)
soit par la question (3) (lorsque $y$ est en fait égal à $u_i$
resp. $u'_i$).  Comme par ailleurs $|a|_c = 0 < 1 = |a|_a$, une
égalité est stricte et on en déduit $|v|_c < |v|_a$, ce qui conclut la
récurrence.

\smallbreak

(5) Si $u \in L(T)$ et si $v$ est un préfixe de $u$ autre que $u$
lui-même, alors soit $v = \varepsilon$, qui n'appartient pas à
$L(T)$ (par exemple par la question (1)), soit $0<|v|<|u|$, auquel
cas la question (4) donne $|v|_c<|v|_a$, ce qui interdit $v\in L(T)$
d'après (3).  Dans tous les cas, $v\not\in L(T)$.

Si maintenant $u\in L(T)$ et $z\in\Sigma^*$, un préfixe de $w := uz$
est soit un préfixe de $u$ soit de la forme $uz'$ avec $z'$ un préfixe
non vide de $z$ (cf. la note \ref{prefix-note}).  Un préfixe de $w$ de
longueur ${<}|u|$ n'appartient pas à $L(T)$ d'après le paragraphe
précédent, et un mot de la forme $uz'$ ne peut pas y appartenir non
plus car c'est alors $u$ lui-même qui serait un préfixe strict de $uz'
\in L(T)$ appartenant à $L(T)$, ce qui contredit de nouveau le
paragraphe précédent.

\smallbreak

(6) D'après la question précédente, on peut définir $u_1$ comme
l'unique préfixe de $w$ qui appartient à $L(T)$ (tout préfixe
strictement plus court ou strictement plus long n'appartient pas à
$L(T)$).  Une fois que $u_1$ est défini, en appliquant le même
raisonnement au suffixe correspondant $u_2\cdots u_k$, on voit que
$u_2$ est défini de façon unique.  En procédant ainsi (par récurrence
sur $k$ si on veut), les $u_i$ sont définis de façon unique.

Le même raisonnement vaut pour $u_1\cdots u_k b u'_1\cdots u'_\ell$ :
on a une factorisation en mots de $L(T)\cup\{b\}$ et à chaque fois
le premier facteur est défini comme le seul préfixe possible
appartenant à $L(T)\cup\{b\}$.  (On utilise le fait que $bz\not\in
L(T)$, qui découle du (1), pour voir que $bu'_1\cdots u'_\ell$ n'a
pas de préfixe dans $L(T)$.)

\smallbreak

(7) En reprenant l'analyse du (1), il s'agit de montrer que la
factorisation $u_1\cdots u_k$ d'un mot de $L(S)$ est unique et que la
factorisation $a u_1\cdots u_k b u'_1\cdots u'_\ell c$ d'un mot
de $L(T)$ l'est aussi.  La première partie est exactement une
conclusion du (6), et la seconde l'est aussi dès lors qu'on retire le
$a$ initial et le $c$ final.
\end{corrige}

\begin{commentaire}
Cet exercice a été noté sur $9$ (dans une note finale sur $20$).

(3) Les deux démonstrations proposées dans le corrigé ci-dessus ont
  effectivement été trouvées (rédigées de façon généralement
  incorrecte, mais on n'a pas sanctionné trop sévèrement les
  imprécisions).

Un nombre étonnant de copies commettent l'erreur de croire que pour
montrer quelque chose pour tout $w$ de $L(S)$ ou bien $L(T)$,
lorsqu'on a $L(T) \subseteq L(S)$, il suffit de le montrer pour $w\in
L(T)$ : c'est au contraire $w \in L(S)$ qu'on peut supposer.  (Il est
vrai que comme $L(S) = L(T)^*$, il n'est pas non plus difficile de
passer de $L(T)$ à $L(S)$, mais il faut au moins dire un mot.)

(4) Malgré la note \ref{prefix-note} en bas de page, la plupart des
  copies pensent qu'un préfixe de $au_1\cdots u_k bu'_1\cdots u'\ell
  c$ est de la forme $au_1\cdots u_i$ ou bien $au_1\cdots u_k
  bu'_1\cdots u'_i$, et oublient que le dernier facteur peut lui-même
  être coupé (c'était bien ça le sens de la note).  Cette erreur n'a
  pas été sanctionnée trop sévèrement.

(5) Cette question comportait deux sous-questions.  La première (si
  $u\in L(T)$ et $v$ préfixe de $u$ différent de $u$ alors $v\not\in
  L(T)$) a été correctement traitée à ceci près que beaucoup oublient
  le cas $v=\varepsilon$ qui n'était pas couvert par la question (4) ;
  la seconde (concernant les préfixes de $uz$) a été souvent oubliée,
  et certains oublient de considérer le cas d'un préfixe de
  longueur $>|u|$.

En outre, pour l'application à la question (6), certains parlent de
« unique préfixe de $w$ » pour « unique préfixe de $w$ qui appartienne
  à $L(T)$ ».  Il n'est pas clair s'il s'agit d'une confusion ou d'un
oubli.

(6) La seconde sous-question (celle portant sur $u_1\cdots u_k
bu'_1\cdots u'\ell$) n'a quasiment pas été traitée.
\end{commentaire}



%
%
%
\end{document}