%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usepackage{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
\renewcommand{\qedsymbol}{\smiley}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\par\smallbreak\else\egroup\par\fi}
\newenvironment{commentaire}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
{{\hbox{}\nobreak\hfill\maltese}%
\ifcorrige\par\smallbreak\else\egroup\par\fi}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\ifcorrige
\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}}
\else
\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
\fi
\author{}
\date{16 juin 2022}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Les exercices sont totalement indépendants (le premier teste
l'application d'algorithmes vus en cours, le second est de nature plus
théorique).  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} : autant de points pour chaque 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 considère
l'expression rationnelle $r := a{*}b{*}a{*}$, et soit $L := L(r)$ le
langage qu'elle dénote.

(0) Pour chacun des mots suivants, dire si oui ou non il appartient
à $L$ (c'est-à-dire s'il vérifie $r$) : $\varepsilon$ (le mot vide),
$a$, $b$, $ab$, $ba$, $aa$, $aba$, $bab$, $abab$.  On ne demande pas
de justifier les réponses.

\begin{corrige}
Les mots $\varepsilon$, $a$, $b$, $ab$, $ba$, $aa$, $aba$
appartiennent à $L$ ; les mots $bab$ et $baba$ n'appartiennent pas
à $L$.
\end{corrige}

\emph{Il est fortement conseillé, dans toutes les questions suivantes,
  d'utiliser les mots qui viennent d'être listés pour vérifier les
  automates successifs qu'on calculera.}  (Par exemple, pour un
automate censé reconnaître le langage $L$, on vérifiera qu'il accepte
bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux
qu'on a identifiés comme n'appartement pas à $L$.)  Les fautes qui
auraient dû être détectées par cette vérification pourront être plus
lourdement sanctionnées.

(1) Traiter l'une \emph{ou} l'autre des questions suivantes :
(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ;
(ii) construire l'automate de Thompson de $r$, puis éliminer les
transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on
retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$
l'automate ainsi obtenu.

(Dans les deux cas, on obtient le même automate fini $\mathscr{A}_1$,
et il a $4$ états.  À défaut de donner l'automate de Glushkov ou de
Thompson, donner un NFA reconnaissant $L$ pourra apporter une partie
des points.)

\begin{corrige}
L'automate $\mathscr{A}_1$ trouvé est le 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 (60bp,0bp) [draw,circle,state,final,accepting below] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state,final,accepting below] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,final] {$3$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) to[loop above] node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
\draw[->] (q0) to[out=295,in=245] node[auto,below]{$b$} (q2);
\draw[->] (q1) to[out=295,in=245] node[auto,below]{$a$} (q3);
\draw[->] (q0) to[out=270,in=270] node[auto,below]{$a$} (q3);
\end{tikzpicture}
\end{center}
(on remarquera notamment que tous ses états sont finaux).
\end{corrige}

(2) Déterminiser l'automate $\mathscr{A}_1$.  On appellera
$\mathscr{A}_2$ l'automate en question.  On rappelle qu'on attend ici
un automate fini \emph{déterministe complet} ; pour information, il a
$5$ états.

\begin{corrige}
L'automate $\mathscr{A}_2$ trouvé est le suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$\scriptstyle\{0\}$};
\node (q1) at (30bp,52bp) [draw,circle,state,final,accepting right] {$\scriptstyle\{1,3\}$};
\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{2\}$};
\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{3\}$};
\node (qF) at (180bp,0bp) [draw,circle,state] {$\varnothing$};
\draw[->] (q0) -- node[auto]{$b$} (q2);
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) to[loop above] node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) to[loop above] node[auto,near end]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (qF);
\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}

(3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du
langage $L$).  Pour information, cet automate a $4$ états : pour la
commodité du correcteur, on les appellera $1,2,3,\bot$ dans l'ordre
dans lequel ils sont parcourus lorsque l'automate consomme le
mot $bab$.

\begin{corrige}
L'automate $\mathscr{A}_2$ est déterministe complet sans état
inaccessible.  On commence l'algorithme de minimisation en séparant
les états finaux $\{0\},\{1,3\},\{2\},\{3\}$ et l'état
non-final $\varnothing$.  On sépare ensuite les premiers selon que la
transition étiquetée $b$ conduit à un état non-final, ce qui
sépare $\{3\}$ du reste, et enfin selon que la transition
étiquetée $a$ conduit à cet état $\{3\}$, ce qui sépare $\{2\}$ du
reste.  Finalement, on aboutit aux classes suivantes : $\{0\} \equiv
\{1,3\}$, $\{2\}$, $\{3\}$ et $\varnothing$ (qu'on rebaptise
$1,2,3,\bot$ respectivement), et à l'automate minimal $\mathscr{A}_3$
suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$};
\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$};
\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$};
\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$};
\draw[->] (q1) to[loop above] node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (qF);
\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}

(4) Donner de même l'automate minimal $\mathscr{A}_4$ du langage $L'
:= L(r')$ dénoté par l'expression rationnelle $r' := b{*}a{*}b{*}$.
Comme cette expression, et donc cet automate, sont simplement obtenus
en échangeant $a$ et $b$ par rapport à ce qui précède, on donnera
directement l'automate sans passer par les questions intermédiaires.

\begin{corrige}
L'automate minimal $\mathscr{A}_4$ de $L'$ s'obtient simplement en
échangeant $a$ et $b$ dans $\mathscr{A}_3$ :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$};
\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$};
\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$};
\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$};
\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
\draw[->] (q1) -- node[auto]{$a$} (q2);
\draw[->] (q2) to[loop above] node[auto]{$a$} (q2);
\draw[->] (q2) -- node[auto]{$b$} (q3);
\draw[->] (q3) to[loop above] node[auto]{$b$} (q3);
\draw[->] (q3) -- node[auto]{$a$} (qF);
\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}

(5) En utilisant une construction de type « automate produit », donner
un automate déterministe complet $\mathscr{A}_5$, ayant $4\times 4 =
16$ états, qui reconnaît le langage $M := L \cap L'$ (constitué des
mots vérifiant à la fois $r$ et $r'$).  On prendra garde pour la
question suivante au fait que cet automate possède des états
inaccessibles.

\begin{corrige}
En prenant le produit des automates
$\mathscr{A}_3$ et $\mathscr{A}_4$, on aboutit à l'automate suivant
(où on a noté $q,q'$ l'état correspondant au couple $(q,q')$ d'un état
$q$ de $\mathscr{A}_3$ et $q'$ de $\mathscr{A}_4$ ; par exemple,
$\delta((1,1),a) = (1,2)$ car $\delta_{\mathscr{A}_3}(1,a) = 1$ et
$\delta_{\mathscr{A}_4}(1,a) = 2$) :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q11) at (0bp,0bp) [draw,circle,state,initial,accepting by double] {\footnotesize$1,1$};
\node (q12) at (60bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,2$};
\node (q13) at (120bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,3$};
\node (q1F) at (180bp,0bp) [draw,circle,state] {\footnotesize$1,\bot$};
\node (q21) at (0bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,1$};
\node (q22) at (60bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,2$};
\node (q23) at (120bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,3$};
\node (q2F) at (180bp,-60bp) [draw,circle,state] {\footnotesize$2,\bot$};
\node (q31) at (0bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,1$};
\node (q32) at (60bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,2$};
\node (q33) at (120bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,3$};
\node (q3F) at (180bp,-120bp) [draw,circle,state] {\footnotesize$3,\bot$};
\node (qF1) at (0bp,-180bp) [draw,circle,state] {\footnotesize$\bot,1$};
\node (qF2) at (60bp,-180bp) [draw,circle,state] {\footnotesize$\bot,2$};
\node (qF3) at (120bp,-180bp) [draw,circle,state] {\footnotesize$\bot,3$};
\node (qFF) at (180bp,-180bp) [draw,circle,state] {\footnotesize$\bot,\bot$};
\draw[->] (q11) -- node[auto]{$b$} (q21);
\draw[->] (q11) -- node[auto]{$a$} (q12);
\draw[->] (q12) -- node[auto]{$b$} (q23);
\draw[->] (q12) to[loop above] node[auto]{$a$} (q12);
\draw[->] (q13) -- node[auto]{$b$} (q23);
\draw[->] (q13) -- node[auto]{$a$} (q1F);
\draw[->] (q1F) -- node[auto]{$b$} (q2F);
\draw[->] (q1F) to[loop right] node[auto]{$a$} (q1F);
\draw[->] (q21) to[loop left] node[auto]{$b$} (q21);
\draw[->] (q21) -- node[auto]{$a$} (q32);
\draw[->] (q22) -- node[auto]{$b$} (q23);
\draw[->] (q22) -- node[auto]{$a$} (q32);
\draw[->] (q23) to[loop right] node[auto]{$b$} (q23);
\draw[->] (q23) -- node[auto]{$a$} (q3F);
\draw[->] (q2F) to[loop right] node[auto]{$b$} (q2F);
\draw[->] (q2F) -- node[auto]{$a$} (q3F);
\draw[->] (q31) -- node[auto]{$b$} (qF1);
\draw[->] (q31) -- node[auto]{$a$} (q32);
\draw[->] (q32) -- node[auto]{$b$} (qF3);
\draw[->] (q32) to[loop below] node[auto]{$a$} (q32);
\draw[->] (q33) -- node[auto]{$b$} (qF3);
\draw[->] (q33) -- node[auto]{$a$} (q3F);
\draw[->] (q3F) -- node[auto]{$b$} (qFF);
\draw[->] (q3F) to[loop right] node[auto]{$a$} (q3F);
\draw[->] (qF1) to[loop below] node[auto]{$b$} (qF1);
\draw[->] (qF1) -- node[auto]{$a$} (qF2);
\draw[->] (qF2) -- node[auto]{$b$} (qF3);
\draw[->] (qF2) to[loop below] node[auto]{$a$} (qF2);
\draw[->] (qF3) to[loop below] node[auto]{$b$} (qF3);
\draw[->] (qF3) -- node[auto]{$a$} (qFF);
\draw[->] (qFF) to[loop below] node[auto]{$a,b$} (qFF);
\end{tikzpicture}
\end{center}
Pour plus de lisibilité, on a ici noté les états finaux en les
entourant deux fois plutôt qu'avec une flèche sortante.
\end{corrige}

(6) Minimiser l'automate $\mathscr{A}_5$.  On appellera
$\mathscr{A}_6$ l'automate minimal ainsi obtenu (automate canonique du
langage $M = L \cap L'$).  Pour information, cet automate a $6$ états.

\begin{corrige}
On commence par ne conserver que les états accessibles depuis l'état
initial, c'est-à-dire ceux étiquetés $(1,1)$, $(1,2)$, $(2,1)$,
$(2,3)$, $(3,2)$, $(3,\bot)$, $(\bot,3)$ et $(\bot,\bot)$ dans la
représentation ci-dessus, pour avoir un automate déterministe complet
sans état inaccessible.  On applique ensuite l'algorithme de
minimisation de manière semblable à la question (3) : les états
non-finaux vont toujours rester groupés, et les états finaux sont
séparés un par un.  Finalement, on aboutit à l'automate
$\mathscr{A}_6$ suivant comme automate minimal du langage $M$ (on a
rebaptisé les états ainsi : $(1,1)\rightsquigarrow 1$,
$(2,1)\rightsquigarrow 2$, $(3,2)\rightsquigarrow 3$,
$(1,2)\rightsquigarrow 2'$, $(2,3)\rightsquigarrow 3'$, et
$(3,\bot)\equiv (\bot,3) \equiv (\bot,\bot) \rightsquigarrow \bot$) :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$};
\node (q2a) at (60bp,42bp) [draw,circle,state,final,accepting below] {$2'$};
\node (q3a) at (120bp,42bp) [draw,circle,state,final,accepting below] {$3'$};
\node (q2) at (60bp,-42bp) [draw,circle,state,final,accepting below] {$2$};
\node (q3) at (120bp,-42bp) [draw,circle,state,final,accepting below] {$3$};
\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$};
\draw[->] (q1) -- node[auto]{$a$} (q2a);
\draw[->] (q1) -- node[auto,below]{$b$} (q2);
\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
\draw[->] (q2a) -- node[auto]{$b$} (q3a);
\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a);
\draw[->] (q3a) -- node[auto]{$a$} (qF);
\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto,below]{$a$} (q3);
\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto,below]{$b$} (qF);
\draw[->] (qF) to[loop right] node[auto]{$a,b$} (qF);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}

(7) En appliquant l'algorithme d'élimination des états, déduire
de $\mathscr{A}_6$ une expression rationnelle $s$ dénotant le
langage $M$.  Pour obtenir une expression raisonnablement simple, on
recommande d'éliminer les états en commençant par ceux qui sont à la
distance la plus éloignée de l'état initial.

\begin{corrige}
On commence par effacer l'état puits (qui ne sert à rien) et par créer
un unique état final sans transition qui en parte :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$};
\node (q3a) at (120bp,42bp) [draw,circle,state] {$3'$};
\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$};
\node (q3) at (120bp,-42bp) [draw,circle,state] {$3$};
\node (qT) at (180bp,0bp) [draw,circle,state,final] {$\infty$};
\draw[->] (q1) -- node[auto]{$a$} (q2a);
\draw[->] (q1) -- node[auto,below]{$b$} (q2);
\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT);
\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
\draw[->] (q2a) -- node[auto]{$b$} (q3a);
\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a);
\draw[->] (q2a) -- node[auto,below]{$\varepsilon$} (qT);
\draw[->] (q3a) -- node[auto]{$\varepsilon$} (qT);
\draw[->] (q2) to[loop below] node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto,below]{$a$} (q3);
\draw[->] (q3) to[loop below] node[auto]{$a$} (q3);
\draw[->] (q2) -- node[auto]{$\varepsilon$} (qT);
\draw[->] (q3) -- node[auto,below]{$\varepsilon$} (qT);
\end{tikzpicture}
\end{center}

On peut alors éliminer les états $3$ et $3'$ (il n'y a pas
d'interaction entre eux) :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$};
\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$};
\node (qT) at (120bp,0bp) [draw,circle,state,final] {$\infty$};
\draw[->] (q1) -- node[auto]{$a$} (q2a);
\draw[->] (q1) -- node[auto,below]{$b$} (q2);
\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT);
\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
\draw[->] (q2a) -- node[auto]{$\varepsilon|bb{*}$} (qT);
\draw[->] (q2) to[loop below] node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto,below,near end]{$\varepsilon|aa{*}$} (qT);
\end{tikzpicture}
\end{center}

Et finalement, en éliminant les états $2$ et $2'$, on trouve
l'expression rationnelle suivante qui dénote le langage $M$ :
\[
\varepsilon\,|\,aa{*}(\varepsilon|bb{*})\,|\,bb{*}(\varepsilon|aa{*})
\]
(il y a bien sûr d'autres écritures possibles ; par exemple, si on
élimine d'abord $2$ et $2'$ puis $3$ et $3'$ on obtient :
$\varepsilon\,|\,aa{*}\,|\,bb{*}\,|\,aa{*}bb{*}\,|\,bb{*}aa{*}$ ;
l'expression rationnelle $\varepsilon\,|\,aa{*}b{*}\,|\,bb{*}a{*}$ est
encore équivalente, mais elle ne s'obtient pas par la procédure
d'élimination des états).
\end{corrige}


%
%
%

\exercice

Les parties (A), (B) et (C) de cet exercice sont indépendantes.  On ne
demande pas de justifications très longues.

\medskip

\textbf{(A)} On se propose de montrer que la question de savoir si
une grammaire hors contexte $G$ (sur un alphabet $\Sigma$ fixé)
vérifie $L(G) \neq \varnothing$ est décidable.  Autrement dit, on
veut montrer qu'il existe un algorithme qui prend en entrée une
grammaire hors contexte $G$, termine toujours en temps fini, et
renvoie « vrai » si $L(G) \neq \varnothing$ et « faux » si $L(G) =
\varnothing$.

(1) Expliquer pourquoi $L(G) \neq \varnothing$ si et seulement si il
existe un arbre d'analyse $\mathscr{T}$ pour $G$.  (Un « arbre
d'analyse pour $G$ » désigne un arbre d'analyse d'un mot quelconque
selon $G$.)

\begin{corrige}
Tout mot de $L(G)$ a (au moins) un arbre d'analyse pour $G$, et tout
arbre d'analyse pour $G$ est l'arbre d'analyse d'un mot de $L(G)$ :
ainsi, si $L(G) \neq \varnothing$, il existe un arbre d'analyse
pour $G$, et si $L(G) = \varnothing$ il n'existe pas d'arbre d'analyse
pour $G$.
\end{corrige}

$\bullet$ Pour les questions suivantes, on introduit la terminologie
suivante : si $\mathscr{T}$ est un arbre et $n$ un nœud (=sommet)
de $\mathscr{T}$, on dit qu'un nœud $n'$ est un \textbf{descendant} de
$n$ lorsque $n'$ est soit égal à $n$, soit est un fils de $n$, soit
est un fils d'un fils de $n$, etc., à n'importe quelle profondeur.
L'ensemble des descendants de $n$ (y compris $n$ lui-même) est donc un
arbre ayant $n$ pour racine, qu'on appelle \textbf{sous-arbre qui
  descend} de $n$.

(2) Montrer que s'il existe un arbre d'analyse $\mathscr{T}$ pour $G$,
il en existe un vérifiant la propriété additionnelle suivante :
($\dagger$) « si un nœud $n$ est étiqueté par un nonterminal $X$,
alors aucun nœud $n' \neq n$ descendant de $n$ ne porte la même
étiquette $X$ ».

\textit{Indication.}\quad Pour cela, on pourra remarquer que si un
arbre $\mathscr{T}$ ne vérifie pas ($\dagger$), on peut en construire
un autre ayant strictement moins de nœuds, en remplaçant le sous-arbre
qui descend de $n$ par celui qui descend de $n'$, et expliquer
pourquoi c'est encore un arbre d'analyse pour $G$ si $\mathscr{T}$ en
est un (pas nécessairement du même mot).

\begin{corrige}
Si $\mathscr{T}$ est un arbre d'analyse pour $G$ dans lequel un nœud
$n'$ descendant d'un autre nœud $n$ est étiqueté par le même
symbole $X$, alors on peut fabriquer un arbre $\mathscr{T}'$ en
remplaçant le sous-arbre qui descend de $n$ par celui qui descend
de $n'$.  Cet arbre $\mathscr{T}'$ a strictement moins de nœuds
que $\mathscr{T}$ car ses nœuds sont exactement ceux de $\mathscr{T}$
à l'exception de ceux qui descendent de $n$ mais pas de $n'$.  Par
ailleurs, c'est toujours un arbre d'analyse pour $G$ car chaque nœud a
des fils étiquetés exactement de la même manière (le seul pour lequel
ce n'est pas évident est le nœud parent de $n$, mais c'est bien vrai
car $n'$ et $n$ ont la même étiquette $X$).

Si on considère maintenant $\mathscr{T}$ l'arbre d'analyse pour $G$
ayant le nombre minimal de nœuds, il vérifie forcément ($\dagger$),
sans quoi la construction qu'on vient de donner produirait un arbre
$\mathscr{T}'$ ayant strictement moins de nœuds, contredisant la
minimalité.  Il existe donc bien un arbre d'analyse pour $G$
vérifiant ($\dagger$) (dès lors qu'il existe un arbre d'analyse
pour $G$ tout court).
\end{corrige}

$\bullet$ Pour la question suivante, on dira qu'un arbre $\mathscr{T}$
est de \textbf{valence} $\leq k$ lorsque chaque nœud de $\mathscr{T}$
a au plus $k$ fils.

(3) Montrer que, quels que soient les entiers naturels $k$ et $m$, il
n'y a qu'un nombre fini d'arbres de valence $\leq k$, dont les sommets
sont étiquetés par des étiquettes prises dans un ensemble
$\{Z_1,\ldots,Z_m\}$ de cardinal $m$, et vérifiant la propriété
($\dagger$) de la question précédente.  Plus précisément, on pourra
montrer que le nombre de tels arbres est donné par $N(k,m)$ défini par
la récurrence $N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$ (et $N(k,0) =
0$) en considérant l'étiquette de la racine (parmi $m$ possibles) et
les $r \leq k$ sous-arbres qui descendent de ses fils.

\begin{corrige}
Un arbre $\mathscr{T}$ de valence $\leq k$ vérifiant ($\dagger$) et
dont les étiquettes sont prises parmi $\{Z_1,\ldots,Z_m\}$ s'obtient
en choisissant l'étiquette $Z_i$ de la racine parmi $m$ possibles, le
nombre $0\leq r\leq k$ de fils de la racine, et les sous-arbres
$\mathscr{T}_1,\ldots,\mathscr{T}_r$ qui en descendent, qui sont
eux-mêmes des arbres de valence $\leq k$ vérifiant ($\dagger$) et dont
les étiquettes sont prises parmi $\{Z_1,\ldots,Z_m\} \setminus
\{Z_i\}$, c'est-à-dire parmi $m-1$ possibles.  Par récurrence sur $m$,
on montre donc que ce nombre est fini, et précisément qu'il vérifie
$N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$.
\end{corrige}

(4) En déduire un algorithme répondant à la question posée.

\textit{Indication.}\quad Si $k$ est la longueur maximale d'une
production de la grammaire $G$, on pourra chercher à construire tous
les arbres de valence $\leq k$, étiquetés par des terminaux ou
nonterminaux ou $\varepsilon$, vérifiant de plus la
propriété ($\dagger$), et regarder s'il y a un arbre d'analyse parmi
eux.

\begin{corrige}
Si $k$ est la longueur maximale d'une production de la grammaire $G$
et $m$ le nombre d'étiquettes possibles d'un arbre d'analyse selon $G$
(c'est-à-dire le nombre de nonterminaux plus le nombre de terminaux
plus $1$ pour $\varepsilon$, mais peu importe), on commence par
énumérer tous les arbres de valence $\leq k$, étiquetés par les tokens
en question, ce qui est possible d'après la question précédente (et
effectif avec la récursion évidente sur $m$).  Il suffit ensuite de
tester tous ces arbres concevables et de vérifie si, à chaque nœud,
les contraintes imposées à un arbre d'analyse sont vérifiées.  Soit on
trouve un arbre d'analyse pour $G$, auquel cas on a montré $L(G) \neq
\varnothing$ et on peut répondre « vrai » ; soit il n'y a aucun arbre
d'analyse pour $G$ vérifiant ($\dagger$), donc aucun d'arbre d'analyse
pour $G$ d'après la question (2), donc $L(G) = \varnothing$
d'après (1) et on peut répondre « faux ».
\end{corrige}

\medbreak

\textbf{(B)} Montrer que la question de savoir si (pour un alphabet
$\Sigma$ fixé) une grammaire hors contexte $G$ vérifie $L(G) \neq
\Sigma^*$, est semi-décidable.  Autrement dit, montrer qu'il existe un
algorithme qui prend en entrée une grammaire hors contexte $G$,
termine en temps fini et renvoie « vrai » si $L(G) \neq \Sigma^*$, et
ne termine pas si $L(G) = \Sigma^*$.

\textit{Indication.}\quad On pourra pour cela énumérer tous les mots
possibles à la recherche d'un mot qui \emph{n'appartient pas}
à $L(G)$, et utiliser le fait que tester si $w \in L(G)$ est
décidable.

\begin{corrige}
L'algorithme suivant convient : énumérer tous les mots $w \in
\Sigma^*$ et, pour chacun, utiliser la procédure de décision connue
pour déterminer en temps fini si $w \in L(G)$.  Si ce n'est pas le
cas, on termine immédiatement en renvoyant « vrai » (on a $L(G) \neq
\Sigma^*$) ; si c'est le cas, on continue (on passe au mot suivant).
Cet algorithme termine (et renvoie « vrai » dans ce cas) exactement
lorsque $L(G) \neq \Sigma^*$ : il montre donc la semi-décidabilité du
problème considéré.
\end{corrige}

\medbreak

\textbf{(C)} (1) Montrer qu'il existe un algorithme qui, donnés une
expression rationnelle $r_1$ et une grammaire hors contexte $G_1$ (sur
un même alphabet $\Sigma$), calcule (= renvoie) une grammaire hors
contexte $G_2$ telle que $L(G_2) = L(G_1) \cup (\Sigma^* \setminus
L(r_1))$.

\begin{corrige}
D'après divers résultats du cours : donnée une expression rationnelle
$r_1$, on sait calculer algorithmiquement un NFA $A_1$ tel que $L(r_1)
= L(A_1)$ (par exemple avec la construction de Glushkov), on sait
calculer algorithmiquement un DFA $A_2$ tel que $L(A_1) = L(A_2)$ (en
déterminisant $A_1$), on sait calculer algorithmiquement un DFA $A_2$
tel que $L(A_3) = \Sigma^* \setminus L(A_2)$ (en échangeant états
finaux et non-finaux), on sait calculer algorithmiquement une
grammaire hors contexte $G_3$ telle que $L(G_3) = L(A_3)$ (en
construisant une grammaire régulière), et à partir de $G_1$ et $G_3$
on sait calculer algorithmiquement une grammaire hors contexte $G_2$
telle que $L(G_2) = L(G_1) \cup L(G_3)$ (stabilité algorithmique des
langages algébriques par union) : on a alors $L(G_2) = L(G_1) \cup
(\Sigma^* \setminus L(r_1))$ comme annoncé.
\end{corrige}

(2) On \underline{admet} que le problème suivant n'est pas décidable
(pour un alphabet $\Sigma$ fixé de cardinal $\#\Sigma \geq 2$) :
donnés $G$ une grammaire hors contexte et $r$ une expression
rationnelle, savoir si $L(r) \subseteq L(G)$.  En déduire que le
problème suivant (qui en est un cas particulier) n'est lui-même pas
décidable : donnée $G$ une grammaire hors contexte, savoir si $L(G) =
\Sigma^*$.

\textit{Indication.}\quad Pour cela, on pourra supposer par l'absurde
que le problème de reconnaître si $L(G) = \Sigma^*$ est décidable et,
donnés $G_1$ et $r_1$, construire algorithmiquement une grammaire hors
contexte $G_2$ telle que $L(G_2) = \Sigma^*$ si et seulement si
$L(r_1) \subseteq L(G_1)$.

\begin{corrige}
Supposons par l'absurde qu'on dispose d'un algorithme $\mathfrak{A}$
qui prend une grammaire hors contexte $G$ en entrée et décide si $L(G)
= \Sigma^*$.  Considérons l'algorithme suivant qui prend en entrée une
grammaire hors contexte $G_1$ et une expression rationnelle $r_1$ : on
commence par calculer une grammaire $G_2$ telle que $L(G_2) = L(G_1)
\cup (\Sigma^* \setminus L(r_1))$ comme expliqué en question (1), et
on applique à $G_2$ l'algorithme $\mathfrak{A}$ qu'on a supposé
exister pour décider si $L(G_2) = \Sigma^*$.  Comme $L(G_2) = L(G_1)
\cup (\Sigma^* \setminus L(r_1))$, dont le complémentaire est $L(r_1)
\setminus L(G_1)$, on a $L(G_2) = \Sigma^*$ si et seulement si $L(r_1)
\subseteq L(G_1)$ : on peut donc renvoyer « vrai » dans ce cas et
« faux » sinon.  Ceci montre l'existence d'un algorithme décidant si
$L(r_1) \subseteq L(G_1)$, ce qui est impossible (résultat admis).
C'est donc que l'hypothèse de l'existence de $\mathfrak{A}$ était
absurde, et le problème en question n'est pas décidable.
\end{corrige}


%
%
%
\end{document}