path: root/controle-20170207.tex

%% 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}
%
%
% 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 délibérément trop long pour le temps imparti, il sera
possible d'obtenir la totalité des points en ne traitant qu'une partie
des exercices.

\medbreak

L'usage de tous les documents (notes de cours manuscrites ou
imprimées, feuilles d'exercices, livres) est autorisé.

L'usage des calculatrices électroniques est interdit.

\medbreak

Durée : 1h30

\pagebreak


%
%
%

\exercice

On considère l'automate fini 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 en question, 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 conseillé 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, s'il y en a.
(On supprimera les états devenus inutiles.)

(3) Déterminiser l'automate ainsi obtenu, si nécessaire.  (On demande
un automate déterministe complet.)  Pour simplifier le travail du
correcteur, on demande de faire en 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 ainsi obtenu, si nécessaire.

(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, le langage ce langage
complémentaire $\overline{L}$.

(7) Donner une expression rationnelle qui reconnaît ce langage
complémentaire $\overline{L}$.  (Cette question est plus difficile.
Ne pas hésiter à introduire des notations intermédiaires.)

\begin{corrige}
(0) Il s'agit d'un automate non-déterministe à transitions spontanées,
  ou ε-NFA (il n'y a pas de notion d'automate déterministe à
  transitions spontanées).

\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 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{*}$.

(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 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 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 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 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 obtenu 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).

\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 (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 ayant 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 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}


%
%
%

\exercice

Soit $\Sigma$ un alphabet (fini, non vide) fixé.  Les questions
suivantes sont indépendantes (mais on remarquera leur parallélisme).

(1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe
un algorithme $A_1$ qui, 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, 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 tel algorithme $A_3$ : 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.

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}


%
%
%

\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(G) = L(G,S)$ le langage qu'elle engendre, et $L(G,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(G)$ et de $L(G,T)$.

(1) Expliquer brièvement pourquoi $L(G)$ est l'ensemble des mots de la
forme $u_1\cdots u_k$ avec $u_i \in L(G,T)$, et pourquoi $L(G,T)$ est
l'ensemble des mots la forme $awbw'c$ avec $w,w'\in L(G)$.  (Par
conséquent, $L(G,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(G,T)$.)

(2) Comment décrire $L(G)$ de manière simple en fonction de $L(G,T)$ ?
Y a-t-il inclusion de l'un dans l'autre ?

(3) Montrer que tout mot $w$ de $L(G)$ 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 $|u|$ que si $v$ est un préfixe d'un
mot $u\in L(G,T)$ de longueur $0<|v|<|u|$, alors on a $|v|_c < |v|_a$.
(On pourra écrire $u$ sous la forme $a u_1 \cdots u_k b u'_1\cdots
u'_{\ell} c$ obtenue en (1).)

(5) En déduire que si $u \in L(G,T)$ et $z \in \Sigma^+$ (c'est-à-dire
$z\in\Sigma^*$ et $z\neq\varepsilon$) alors $uz \not\in L(G,T)$.
Expliquer par ailleurs pourquoi $bz \not\in L(G,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(G,T)$ alors cette factorisation est unique.
(Comment peut-on définir $u_1$ en fonction de $w$ ?)  Montrer de même
la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots u'_\ell$.

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

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

\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(G)$, 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(G,T)$ et l'autre
  dont descend arbre d'analyse d'un autre mot $w'$ de $L(G)$, 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(G,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(G,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(G) =
L(G,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(G,T) \subseteq L(G)$.

\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(G)$ (et en particulier, pour tout mot de $L(G,T)$).

\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(G,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 de 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.

En particulier, on observe pour la question suivante que $v\not\in
L(G,T)$ pour tout préfixe strict $v$ d'un mot de $L(G,T)$ (si $v =
\varepsilon$ c'est clair, et si $0<|v|<|u|$, on vient de montrer
$|v|_c < |v|_a$ alors qu'un mot de $L(G,T)$ vérifie $|u|_c = |u|_a$
d'après (3)).

\smallbreak

(5) Comme $u$ est un préfixe strict de $uz$, si on avait $uz \in
L(G,T)$ alors la question (4) implique $u\not\in L(G,T)$, une
contradiction : c'est donc que $uz \not\in L(G,T)$.

Le fait que $bz \not\in L(G,T)$ est trivial car tout mot de $L(G,T)$
commence par $a$ d'après la question (1).

\smallbreak

(6) On peut définir $u_1$ comme l'unique préfixe de $w$ qui appartient
à $L(G,T)$ (tout préfixe strictement plus court ou strictement plus
long n'appartient pas à $L(G,T)$ d'après les questions (4) et (5)).
Une fois que $u_1$ est défini par $w$, en appliquant le même
raisonnement à $u_2\cdots u_k$ et ainsi de suite, on voit que $u_2$ et
les autres sont uniquement définis.

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(G,T)\cup\{b\}$ et on a vu qu'en
retirant ou en ajoutant des lettres à la fin d'un mot de ce langage on
obtient un mot qui n'est pas dans $L(G,T)\cup\{b\}$.

\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(G)$ est unique et que la
factorisation $a u_1\cdots u_k b u'_1\cdots u'_\ell c$ d'un mot
de $L(G,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}



%
%
%
\end{document}