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 9 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 fini 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 proprement menée 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), de sorte que $\Sigma^* = \{a^n : n\in\mathbb{N}\}$ ; on va
appliquer les automates finis à un problème arithmétique.

\medskip

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

\nobreak

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 allégées 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 (étiquetée par $a$) à considérer, 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 les a marqués par un F dans la colonne de droite de
la table ci-dessus.

On peut bien sûr préférer 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, certains états étant 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) plus bas, 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) plus bas, 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 fini 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) plus bas, 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,
si le mot $a^n$ appartient à $L$, c'est-à-dire vérifie $r$, i.e.,
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), il a pour longueur $n =
3m+5m'$.  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.}

\nobreak

(6) Expliquer rapidement pourquoi un automate fini déterministe
complet sans état inaccessible $\mathscr{A}$ sur $\Sigma = \{a\}$
prend nécessairement la forme suivante : si on note $j_2$ son nombre
d'états, on peut numéroter ces é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}
Appelons $q_0$ l'état initial de $\mathscr{A}$, et par récurrence
sur $i$, posons $q_{i+1} = \delta(q_i,a)$ l'état vers lequel pointe la
transition sortante depuis l'état $q_i$ étiquetée par la lettre $a$
(cette transition étant unique puisqu'on a affaire à un automate
déterministe complet) ; ou, pour dire les choses autrement, appelons
$q_i = \delta^*(q_0, a^i)$ (pour tout $i\in \mathbb{N}$) l'état
résultant de la lecture du mot $a^i$ par l'automate.  L'automate
$\mathscr{A}$ étant fini, les états $q_0,q_1,q_2,\ldots$ ne peuvent
pas être tous distincts : il existe $j_1\neq j_2$ tels que $q_{j_1} =
q_{j_2}$ ; appelons $j_2$ l'indice de la première répétition, i.e., le
plus petit entier tel que $q_{j_2}$ coïncide avec un état $q_{j_1}$
avec $0\leq j_1<j_2$.  Alors (puisque $j_2$ est l'indice de la
première répétition) les états $q_0,\ldots,q_{j_2-1}$ sont tous
distincts.  En nommant simplement $i$ l'état $q_i$ (pour $0\leq i<j_2$
uniquement), on a, par construction, $\delta(i,a) = i+1$ pour $0\leq
i<j_2-1$ tandis que $\delta(j_2-1,a) = j_1$, comme annoncé.  De plus,
les états $0,\ldots,j_2-1$ étant tous ceux qu'on peut atteindre en
partant de $0$ et en suivant les transitions, ce sont tous les états
de l'automate (car on l'a supposé sans état inaccessible), donc $j_2$
est le nombre d'états, et l'automate a bien la forme demandée.

(Les notations choisies sont censées rappeler la démonstration du
lemme de pompage, qui utilise la même idée.  Aussi dans le même ordre
d'idées, il est utile pour la question suivante de remarquer que $q_i
= q_{i+(j_2-j_1)}$ dès que $i\geq j_1$, et donc plus généralement $q_i
= q_{i+k(j_2-j_1)}$ pour tout $k\in\mathbb{N}$.)
\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 égal à $\{a^i : i\in F\}$.

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 si l'ensemble\footnote{Autrement dit, il
  s'agit de l'ensemble $\mathbb{N} \setminus \{\ell_1 m_1 + \cdots +
  \ell_r m_r : (m_1,\ldots,m_r)\in \mathbb{N}^r\}$ complémentaire de
  l'image de $\mathbb{N}^r \to \mathbb{N},\penalty0\; (m_1,\ldots,m_r)
  \mapsto \ell_1 m_1 + \cdots + \ell_r m_r$.} des 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}$ est fini, 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}$.

\emph{Remarque :} En fait, il s'avère que l'ensemble $\mathbb{N}
\setminus \{\ell_1 m_1 + \cdots + \ell_r m_r : (m_1,\ldots,m_r)\in
\mathbb{N}^r\}$ est fini si et seulement si le pgcd de
$\ell_1,\ldots,\ell_r$ vaut $1$ (i.e., si et seulement si ces nombres
sont premiers entre eux dans leur ensemble), ce qui est aussi testable
algorithmiquement ; mais ce n'était pas demandé ici, et ceci ne résout
pas la question d'énumérer explicitement l'ensemble.
\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$ peut aussi être 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}