path: root/controle-20200123.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}\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{23 janvier 2020}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

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

Dans l'exercice \ref{exercise-on-unary-languages}, les deux parties
peuvent en principe être traitées indépendamment, mais la première
donne un exemple aidant à comprendre la démarche de la seconde.

\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} : 2+(7+6)+5.

\ifcorrige
Ce corrigé comporte \textcolor{red}{(à remplir)} pages (page de garde incluse)
\else
Cet énoncé comporte 3 pages (page de garde incluse)
\fi

\vfill

{\tiny\noindent
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pagebreak


%
%
%

\exercice

Soit $\mathscr{A}$ l'automate suivant sur l'alphabet $\Sigma :=
\{a,b,c\}$ :

\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$};
\draw [->] (S0) -- node[auto,near end] {$\varepsilon$} (S1);
\draw [->] (S0) -- node[auto,below] {$\varepsilon$} (S2);
\draw [->] (S1) to[out=225,in=135] node[auto,left] {$a$} (S2);
\draw [->] (S2) to[out=45,in=315] node[auto,right] {$b$} (S1);
\draw [->] (S2) to[loop below] node[auto] {$c$} (S2);
\draw [->] (S1) -- node[auto] {$\varepsilon$} (S3);
\draw [->] (S2) -- node[auto,below,near end] {$\varepsilon$} (S3);
\end{tikzpicture}
\end{center}

\vskip-\baselineskip\vskip-.5ex\noindent En lui appliquant la méthode
d'élimination des états, déterminer une expression rationnelle
dénotant le langage qu'il reconnaît.

\begin{corrige}
L'élimination de l'état $1$ conduit à l'automate suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (S2) at (70bp,0bp) [draw,circle,state] {$2$};
\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$};
\draw [->] (S0) -- node[auto,below] {$\varepsilon|a$} (S2);
\draw [->] (S2) to[loop below] node[auto] {$c|ba$} (S2);
\draw [->] (S2) -- node[auto,below] {$\varepsilon|b$} (S3);
\draw [->] (S0) to[out=90,in=180] (60bp,35bp) -- node[auto] {$\varepsilon$} (80bp,35bp) to[out=0,in=90] (S3);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-.5ex\noindent — et l'élimination de
l'état $2$ conduit alors à l'expression rationnelle suivante :
$\varepsilon\;|\;(\varepsilon|a)\,(c|ba){*}\,(\varepsilon|b)$ (il se
trouve que le premier terme est inutile et que cette expression
rationnelle est équivalente à
simplement $(\varepsilon|a)\,(c|ba){*}\,(\varepsilon|b)$, mais la
méthode d'élimination conduit à ce qui a été dit).

Si on élimine d'abord l'état $2$, on aboutit à l'automate suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (S1) at (70bp,0bp) [draw,circle,state] {$1$};
\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$};
\draw [->] (S0) -- node[auto,below] {$\varepsilon|c{*}b$} (S1);
\draw [->] (S1) to[loop below] node[auto] {$ac{*}b$} (S1);
\draw [->] (S1) -- node[auto,below] {$\varepsilon|ac{*}$} (S3);
\draw [->] (S0) to[out=90,in=180] (60bp,35bp) -- node[auto] {$c{*}$} (80bp,35bp) to[out=0,in=90] (S3);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-.5ex\noindent — et à l'expression
rationnelle suivante :
$c{*}\;|\;(\varepsilon|c{*}b)\,(ac{*}b){*}\,(\varepsilon|ac{*})$.
Elle est, bien sûr, équivalente à celle obtenue avec l'autre ordre
d'élimination.
\end{corrige}


%
%
%

\exercice\label{exercise-on-unary-languages}

Dans cet exercice, on pose $\Sigma := \{a\}$ (alphabet à une seule lettre).

\medskip

\textbf{Première partie : étude d'un cas particulier.}

Dans cette partie, on considère l'expression rationnelle $r$
suivante : $(aaa|aaaaa){*}$ (sur l'alphabet $\Sigma$).  On appelle $L
:= L(r)$ le langage qu'elle dénote et $M := \Sigma^* \setminus L$ son
complémentaire.

(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 $\mathscr{A}_1$, ayant
$9$ é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$ obtenu est le suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
\node (S1) at (60bp,35bp) [draw,circle,state] {$1$};
\node (S2) at (120bp,35bp) [draw,circle,state] {$2$};
\node (S3) at (180bp,35bp) [draw,circle,state,final] {$3$};
\node (S1p) at (60bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$1'$\hss}}\phantom{$1$}};
\node (S2p) at (120bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$2'$\hss}}\phantom{$2$}};
\node (S3p) at (180bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$3'$\hss}}\phantom{$3$}};
\node (S4p) at (240bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$4'$\hss}}\phantom{$4$}};
\node (S5p) at (300bp,-35bp) [draw,circle,state,final] {\vbox to0pt{\vss\hbox to0pt{$5'$\hss}}\phantom{$5$}};
\draw [->] (S0) -- node[auto] {$a$} (S1);
\draw [->] (S1) -- node[auto] {$a$} (S2);
\draw [->] (S2) -- node[auto] {$a$} (S3);
\draw [->] (S0) -- node[auto,below] {$a$} (S1p);
\draw [->] (S1p) -- node[auto,below] {$a$} (S2p);
\draw [->] (S2p) -- node[auto,below] {$a$} (S3p);
\draw [->] (S3p) -- node[auto,below] {$a$} (S4p);
\draw [->] (S4p) -- node[auto,below] {$a$} (S5p);
\draw [->] (S3) -- node[auto,above,near end] {$a$} (S1p);
\draw [->] (S5p) -- node[auto,below,very near end] {$a$} (S1);
\draw [->] (S3) to[out=90,in=0] (130bp,70bp) -- node[auto,below] {$a$} (110bp,70bp) to[out=180,in=90] (S1);
\draw [->] (S5p) to[out=210,in=0] (190bp,-70bp) -- node[auto,above] {$a$} (170bp,-70bp) to[out=180,in=330] (S1p);
\end{tikzpicture}
\end{center}
C'est l'automate de Glushkov.  Si on commence par construire
l'automate de Thompson, celui-ci a $20$ états, et l'élimination des
transitions spontanées conduit à l'automate $\mathscr{A}_1$ qu'on
vient d'écrire.
\end{corrige}

(2) Déterminiser l'automate $\mathscr{A}_1$.  On appellera
$\mathscr{A}_2$ l'automate (déterministe complet) en question.

(On obtient un automate $\mathscr{A}_2$ ayant $14$ états.  On
n'hésitera pas à introduire des notations simplificatrices si on le
juge utile ; il pourra être judicieux de réfléchir au préalable à une
façon de nommer les états de $\mathscr{A}_1$ qui rend la construction
de $\mathscr{A}_2$ plus facile à mener sans se tromper.)

Pour simplifier les questions suivantes (ainsi que le travail du
correcteur), on renommera si nécessaire les états de $\mathscr{A}_2$
de façon que, autant que possible, l'état résultant de la lecture du
mot $a^i$ par l'automate soit numéroté $i$.

\begin{corrige}
On travaille sur des ensembles d'états en suivant l'algorithme de
déterminisation : partant de l'ensemble $\{0\}$ des états initiaux de
l'automate $\mathscr{A}_1$, il n'y a à chaque fois qu'une seule
transition à construire, ce qui construit successivement les états
suivants (colonne du milieu de la table) :
\begin{center}
\begin{tabular}{c|l|c}
$0$&$\{0\}$&F\\\hline
$1$&$\{1,1'\}$&\\\hline
$2$&$\{2,2'\}$&\\\hline
$3$&$\{3,3'\}$&F\\\hline
$4$&$\{1,1',4'\}$&\\\hline
$5$&$\{2,2',5'\}$&F\\\hline
$6$&$\{1,1',3,3'\}$&F\\\hline
$7$&$\{1,1',2,2',4'\}$&\\\hline
$8$&$\{2,2',3,3',5'\}$&F\\\hline
$9$&$\{1,1',3,3',4'\}$&F\\\hline
$10$&$\{1,1',2,2',4',5'\}$&F\\\hline
$11$&$\{1,1',2,2',3,3',5'\}$&F\\\hline
$12$&$\{1,1',2,2',3,3',4'\}$&F\\\hline
$13$&$\{1,1',2,2',3,3',4',5'\}$&F\\
\end{tabular}
\end{center}
Le procédé de calcul de la table est le suivant : à chaque ligne à
partir de la deuxième, on incrémente tous les numéros avec et sans
prime, sauf que $3$ ou $5'$ deviennent $1,1'$ (les deux à la fois,
puisqu'il y a des transitions de $3$ et $5'$ vers $1$ et $1'$
dans $\mathscr{A}_1$).  Ceci permet de ne pas se tromper (d'où
l'intérêt d'avoir judicieusement étiqueté les états
de $\mathscr{A}_1$).  L'unique transition de l'automate (évidemment
étiquetée $a$) conduit de chaque ligne à la ligne suivante, sauf la
dernière ligne qui boucle sur elle-même.  Les états finaux sont ceux
qui contiennent un des états finaux de $\mathscr{A}_1$, c'est-à-dire
$0$ ou $3$ ou $5'$ (ou encore, les lignes qui précèdent une ligne
avec $1,1'$).  On peut bien sûr tracer graphiquement l'automate comme
d'habitude : c'est juste une ligne de $14$ états, toutes les
transitions étant étiquetées $a$, menant de chaque état vers le
suivant, sauf du dernier sur lui-même, avec certains états finaux
comme on vient de le dire.

On renumérote alors les états comme selon la colonne de gauche de la
table, c'est-à-dire en suivant l'ordre des lignes.  La transition
étiquetée $a$ mène alors de l'état $i$ vers l'état $i+1$ sauf pour
$i=13$ où elle mène vers lui-même.  L'ensemble des états finaux est $F
= \{0,3,5,6,8,9,10,11,12,13\}$ comme indiqué par la table.

(Dans la notation introduite à la question (6) ci-dessous, l'automate
$\mathscr{A}_2$ est décrit par $j_2 = 14$, $j_1 = 13$ et $F =
\{0,3,5,6,8,9,10,11,12,13\}$.)
\end{corrige}

(3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
$\mathscr{A}_3$ l'automate canonique ainsi obtenu.

(On obtient un automate ayant $9$ états.)

\begin{corrige}
On a bien affaire pour commencer à un automate $\mathscr{A}_2$
déterministe complet sans état inaccessible.

L'algorithme de minimisation commence par partitionner l'ensemble
$\{0,\ldots,13\}$ des états en deux classes, les finaux
$\{0,3,5,6,8,9,10,11,12,13\}$ et les non-finaux $\{1,2,4,7\}$.  Une
première itération sépare les finaux en $\{5,8,9,10,11,12,13\}$ et
$\{0,3,6\}$ (selon que l'état vers lequel aboutit l'unique transition
est lui-même final ou non) et les non-finaux en $\{2,4,7\}$ et $\{1\}$
(idem).  La seconde itération sépare chacun de $0$, $2$ et $5$ des
autres états de leur classe respective : les classes sont alors
$\{0\}$, $\{1\}$, $\{2\}$, $\{3,6\}$, $\{4,7\}$ et
$\{8,9,10,11,12,13\}$.  La troisième itération sépare $4$ et $7$
tandis que la quatrième sépare $3$ et $6$.  Finalement, on obtient un
automate $\mathscr{A}_3$ canonique ayant $9$ états : un pour chaque
état de l'automate $\mathscr{A}_2$ entre $0$ et $7$ inclus, et un pour
tous les états de $8$ à $13$ inclus.

On pouvait aussi arguër de manière plus abstraite : il est clair que
tous les états $8$ à $13$ devront être fusionnés puisqu'ils sont
finaux et que leurs transitions arbitrairement itérées ne conduisent
qu'à des états finaux, tandis que les états $0$ à $7$ inclus devront
être tous séparés puisqu'ils sont distingués par le nombre de
transitions à partir desquelles on n'arrive plus qu'à des états
finaux.

On peut bien sûr tracer graphiquement l'automate $\mathscr{A}_3$ comme
d'habitude : c'est juste une ligne de $9$ états, toutes les
transitions étant étiquetées $a$, menant de chaque état vers le
suivant, sauf du dernier sur lui-même, les états finaux étant ceux
numérotés $0,3,5,6,8$ si on numérote les états de $0$ à $8$ dans
l'ordre des transitions.  (Dans la notation introduite à la
question (6) ci-dessous, l'automate $\mathscr{A}_3$ est décrit par
$j_2 = 9$, $j_1 = 8$ et $F = \{0,3,5,6,8\}$.)
\end{corrige}

(4) Construire un automate déterministe complet $\mathscr{A}_4$
reconnaissant le langage $M := \Sigma^*\setminus L$ complémentaire
de $L$.  Ce langage $M$ est fini : énumérer exhaustivement les mots
qu'il contient.

\begin{corrige}
Il suffit d'échanger états finaux et non-finaux dans un automate
déterministe complet quelconque reconnaissant $L$, disons l'automate
$\mathscr{A}_3$ (on pouvait aussi utiliser $\mathscr{A}_2$ si on n'a
pas réussi à calculer $\mathscr{A}_3$).  On peut bien sûr tracer
graphiquement l'automate $\mathscr{A}_4$ comme d'habitude : c'est
juste une ligne de $9$ états, toutes les transitions étant
étiquetées $a$, menant de chaque état vers le suivant, sauf du dernier
sur lui-même, les états finaux étant ceux numérotés $1,2,4,7$ si on
numérote les états de $0$ à $8$ dans l'ordre des transitions.  (Dans
la notation introduite à la question (6) ci-dessous, l'automate
$\mathscr{A}_3$ est décrit par $j_2 = 9$, $j_1 = 8$ et $F =
\{1,2,4,7\}$.)

L'état $8$ (i.e., le dernier) étant un puits dans
l'automate $\mathscr{A}_4$, les seuls mots acceptés le sont avant le
puits, et ce sont les mots $a$, $aa$, $aaaa = a^4$ et $aaaaaaa = a^7$
comme donnés par les états finaux de $\mathscr{A}_4$.
\end{corrige}

(5) En utilisant la question précédente, dire quels sont les (quatre)
entiers naturels ne pouvant pas s'écrire sous la forme $3m+5m'$ avec
$m,m'\in\mathbb{N}$.

\begin{corrige}
Si $n = 3m+5m'$ alors le mot $a^n = (aaa)^m(aaaaa)^{m'}$ appartient
à $L$, c'est-à-dire qu'il vérifie $r$ puisqu'il est manifestement
concaténation de mots de la forme $aaa$ ou $aaaaa$.  Réciproquement,
la longueur d'un mot de $L$, c'est-à-dire vérifiant $r$, donc
concaténation de mots de la forme $aaa$ et de la forme $aaaaa$, disons
$m$ de l'un et $m'$ de l'autre (en tout) a pour longueur $n := 3m+5m'$
et sur l'alphabet $\{a\}$ le seul mot de cette longueur est le
mot $a^n$.  Bref, les mots de $L$ sont exactement les $a^n$ avec $n$
de la forme $3m+5m'$ ; et les mots qui ne sont pas dans $L$ (i.e.,
sont dans $M$) sont exactement les $a^n$ avec $n$ ne pouvant pas
s'écrire de la forme $3m+5m'$ : on a vu que ce sont $a$, $aa$, $aaaa =
a^4$ et $aaaaaaa = a^7$.  Ainsi, les quatre entiers naturels ne
pouvant pas s'écrire sous la forme $3m+5m'$ avec $m,m'\in\mathbb{N}$
sont : $1$, $2$, $4$ et $7$.
\end{corrige}

\medbreak

\textbf{Seconde partie : considérations générales.}

(6) Expliquer rapidement pourquoi un automate déterministe complet
sans état inaccessible $\mathscr{A}$ sur $\Sigma$ prend nécessairement
la forme suivante : si on note $j_2$ son nombre d'états, on peut
numéroter ses états de $0$ à $j_2-1$, avec $0$ l'état initial, et de
façon qu'il y ait une unique transition étiquetée $a$ de l'état $i$
vers l'état $i+1$ pour chaque $0\leq i<j_2-1$, ainsi qu'une transition
étiquetée $a$ de l'état $j_2-1$ vers l'état $j_1$ pour un
certain $0\leq j_1<j_2$.  Remarquer que l'automate $\mathscr{A}$ est
alors complètement décrit par les entiers $0\leq j_1<j_2$ et par le
sous-ensemble $F$ de $\{0,\ldots,j_2-1\}$ formé des états finaux.

\begin{corrige}
Numérotons les états de $\mathscr{A}$ à partir de l'état initial $0$
et en numérotant successivement les états selon la fonction de
transition $q\mapsto \delta(q,a)$, c'est-à-dire qu'on numérote $i$
l'état $\delta^*(0,a^i)$ résultant de la lecture du mot $a^i$ par
l'automate, et ce, jusqu'à retomber sur un état $j_1$ déjà rencontré
(=numéroté).  Si $j_2$ est le nombre total d'états, on a ainsi
complètement décrit l'automate par $\delta(i,a) = i+1$ sauf pour le
dernier état $j_2 - 1$ qui est envoyé sur $\delta(j_2 - 1, a) = j_1$.

(Les notations choisies sont censées rappeler la démonstration du
lemme de pompage, qui utilise la même idée.)
\end{corrige}

(7) Une fois un automate déterministe complet sur $\Sigma$ présenté
comme décrit à la question (6), à quelle condition nécessaire et
suffisante (sur $j_1,j_2,F$) le langage qu'il reconnaît est-il fini ?

\begin{corrige}
Les états $i$ tels que $j_1\leq i<j_2$ avec la notation introduite
en (6) sont des états résultat de la lecture d'un nombre infini de
mots distincts (à savoir $a^i$, $a^{i+(j_2-j_1)}$, et plus
généralement $a^{i+k(j_2-j_1)}$ pour tout $k\in\mathbb{N}$).  Si l'un
quelconque de ces états est acceptant (=final), le langage reconnu par
l'automate est infini.  À l'inverse, si aucun de ces états n'est
acceptant, le langage est fini et est constitué des $a^i$ pour $i\in
F$ (et $i<j_1$).

Bref, la condition nécessaire et suffisante de finitude du langage
reconnu par $\mathscr{A}$ est que $F \cap \{j_1,\ldots,j_2-1\} =
\varnothing$, et le cas échéant, le langage est constitué des $a^i$
pour $i\in F$ (et $i<j_1$).
\end{corrige}

(8) Déduire de l'ensemble de cet exercice que le problème suivant est
calculable algorithmiquement\footnote{Autrement dit, montrer qu'il
  existe un algorithme qui, prenant en entrée $\ell_1,\ldots,\ell_r
  \in \mathbb{N}$, termine toujours en temps fini et répond au
  problème posé.} : donné des entiers naturels $\ell_1,\ldots,\ell_r
\in \mathbb{N}$, décider s'il y a un nombre fini d'entiers naturels
qui ne peuvent pas s'écrire sous la forme $\ell_1 m_1 + \cdots +
\ell_r m_r$ avec $m_1,\ldots,m_r \in \mathbb{N}$, et, le cas échéant,
les énumérer.

\begin{corrige}
Il suffit d'appliquer la même méthode qui a été utilisée dans les
questions précédentes : donnés $\ell_1,\ldots,\ell_r \in \mathbb{N}$,
on fabrique l'expression rationnelle
$(a^{\ell_1}|\cdots|a^{\ell_r}){*}$ sur $\Sigma$, on construit son
automate de Glushkov (ou de Thompson dont on élimine ensuite les
transitions spontanées), on le déterminise, on peut éventuellement le
minimiser même si ce n'est pas nécessaire pour cette question, on
échange états finaux et non-finaux pour obtenir un automate
reconnaissant le langage complémentaire, et enfin on utilise le
critère trouvé en (7) pour savoir si ce langage est fini et, le cas
échéant, l'énumérer.  Par le même raisonnement qu'en (5), ceci donne
exactement les $a^n$ pour les $n$ qui ne peuvent pas s'écrire sous la
forme $\ell_1 m_1 + \cdots + \ell_r m_r$ avec $m_1,\ldots,m_r \in
\mathbb{N}$.
\end{corrige}


%
%
%

\exercice

On considère la grammaire hors-contexte $G$ d'axiome $S$ et de
nonterminaux $N = \{S, T, U\}$ sur l'alphabet $\Sigma = \{a,b,c\}$
donnée par
\[
\begin{aligned}
S &\rightarrow T \;|\; TaS\\
T &\rightarrow U \;|\; UbT\\
U &\rightarrow c\\
\end{aligned}
\]
(La grammaire en question est inambiguë : on ne demande pas de le
démontrer.)

(1) Donner les arbres d'analyse (= de dérivation) des mots suivants :
$cacbcac$ et $cbcacbc$.

\begin{corrige}
On obtient les arbres d'analyse suivants :

\hbox to\hsize{
% S<T<U<c.>>a.S<T<U<c.>b.T<U<c.>>>a.S<T<U<c.>>>>>
\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
\node (S0) at (37.778bp,0.000bp) [draw=none] {$S$};
\node (T0) at (0.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T0);
\node (U0) at (0.000bp,-50.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
\node (c0) at (0.000bp,-70.000bp) [draw=none] {$c$};  \draw (U0) -- (c0);
\node (a0) at (20.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
\node (S1) at (93.333bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
\node (T1) at (60.000bp,-60.000bp) [draw=none] {$T$};  \draw (S1) -- (T1);
\node (U1) at (40.000bp,-90.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
\node (c1) at (40.000bp,-110.000bp) [draw=none] {$c$};  \draw (U1) -- (c1);
\node (b0) at (60.000bp,-90.000bp) [draw=none] {$b$};  \draw (T1) -- (b0);
\node (T2) at (80.000bp,-90.000bp) [draw=none] {$T$};  \draw (T1) -- (T2);
\node (U2) at (80.000bp,-110.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
\node (c2) at (80.000bp,-130.000bp) [draw=none] {$c$};  \draw (U2) -- (c2);
\node (a1) at (100.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
\node (S2) at (120.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
\node (T3) at (120.000bp,-80.000bp) [draw=none] {$T$};  \draw (S2) -- (T3);
\node (U3) at (120.000bp,-100.000bp) [draw=none] {$U$};  \draw (T3) -- (U3);
\node (c3) at (120.000bp,-120.000bp) [draw=none] {$c$};  \draw (U3) -- (c3);
\end{tikzpicture}
\hss et\hss
% S<T<U<c.>b.T<U<c.>>>a.S<T<U<c.>b.T<U<c.>>>>>
\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
\node (S0) at (60.000bp,0.000bp) [draw=none] {$S$};
\node (T0) at (20.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T0);
\node (U0) at (0.000bp,-60.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
\node (c0) at (0.000bp,-80.000bp) [draw=none] {$c$};  \draw (U0) -- (c0);
\node (b0) at (20.000bp,-60.000bp) [draw=none] {$b$};  \draw (T0) -- (b0);
\node (T1) at (40.000bp,-60.000bp) [draw=none] {$T$};  \draw (T0) -- (T1);
\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
\node (c1) at (40.000bp,-100.000bp) [draw=none] {$c$};  \draw (U1) -- (c1);
\node (a0) at (60.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
\node (S1) at (100.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
\node (T2) at (100.000bp,-50.000bp) [draw=none] {$T$};  \draw (S1) -- (T2);
\node (U2) at (80.000bp,-80.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
\node (c2) at (80.000bp,-100.000bp) [draw=none] {$c$};  \draw (U2) -- (c2);
\node (b1) at (100.000bp,-80.000bp) [draw=none] {$b$};  \draw (T2) -- (b1);
\node (T3) at (120.000bp,-80.000bp) [draw=none] {$T$};  \draw (T2) -- (T3);
\node (U3) at (120.000bp,-100.000bp) [draw=none] {$U$};  \draw (T3) -- (U3);
\node (c3) at (120.000bp,-120.000bp) [draw=none] {$c$};  \draw (U3) -- (c3);
\end{tikzpicture}
}

(On les trouve plus facilement si on se convainc d'abord que la
grammaire peut être vue comme décrivant une expression de termes $c$
reliés par deux opérations binaires $a$ et $b$, toutes les deux
associatives à droite, et l'opération $b$ étant prioritaire sur $a$.
Autrement dit, l'expression dérivant de $S$ est coupée d'abord au
niveau des $a$ en des sous-expressions dérivant de $T$, elles-mêmes
coupées au niveau des $b$.)
\end{corrige}

(2) Le langage $L := L(G)$ engendré par $G$ est, en fait, rationnel :
expliquer brièvement pourquoi et donner une expression rationnelle qui
le dénote.  (On pourra commencer par décrire le langage $L' := L(G,T)
:= \{w \in \Sigma^* : T \mathrel{\Rightarrow^*_G} w\}$ des mots qui
dérivent de $T$ selon $G$.)

\begin{corrige}
Le langage $L' = L(G,T)$ est celui décrit par la grammaire $T
\rightarrow c \;|\; cbT$ d'axiome $T$ (le nonterminal $U$ est
visiblement inutile et peut être directement remplacé par $c$ pour y
voir plus clair).  Il s'agit visiblement du langage dénoté par
l'expression rationnelle $(cb){*}c$ (ceci se démontre par exemple en
remarquant que ses dérivations sont toutes de la forme $T \Rightarrow
cbT \Rightarrow \cdots \Rightarrow (cb)^k T \Rightarrow (cb)^k c$, ou
en raisonnant sur les arbres d'analyse qui sont formés en empilant des
$T$ ayant pour fils gauche $c$ et $b$ et pour fils droite un autre $T$
jusqu'à un dernier $T$ qui a pour seul fils $c$ ; on peut aussi
remarquer qu'il s'agit essentiellement d'une grammaire régulière) : si
on préfère, $L'$ est le plus petit langage tel que $L' = \{c\} \cup
(\{c\}\{b\}L')$, ce que dénote justement $(cb){*}c$.  Bref, un mot de
$L'$ est une succession de $c$ séparés par des $b$, ce que dénote
justement $(cb){*}c$.

Le langage $L = L(G,S)$ est construit selon exactement le même modèle
à partir de $L'$ que $L'$ à partir de $c$ : si on préfère, $L$ est le
plus petit langage tel que $L = L' \cup (L'\{a\}L)$, donc on s'attend
à avoir ce qu'il soit dénoté par $((cb){*}ca){*}(cb){*}c$.  On peut
par exemple raisonner sur les arbres d'analyse : ils sont formés en
empilant des $S$ ayant pour fils gauche $T$ et $a$ et pour fils droite
un autre $S$ jusqu'à un dernier $S$ qui a pour seul fils $T$, et enfin
en insérant un arbre d'analyse d'un mot de $L'$ comme descendance de
chaque $T$.  Bref, un mot de $L$ est une succession de mots de $L'$
séparés par des $a$, ce que dénote justement $((cb){*}ca){*}(cb){*}c$.

Tout ceci étant dit, en fait, le langage $L$ est dénoté par une
expression rationnelle plus simple, à savoir $(c(a|b)){*}c$ (ou encore
$c((a|b)c){*}$ ou encore $c(ac|bc){*}$ ou toutes sortes d'autres
variantes), puisqu'il s'agit d'une succession de $c$ séparés
indifféremment par des $a$ ou des $b$.  Cette expression rationnelle
perd le découpage en deux niveaux (d'abord par $a$ puis par $b$)
effectué par la grammaire $G$, mais est correcte comme description du
langage.
\end{corrige}


%
%
%
\end{document}