From 51080734543552b21da1ba1986928ef5f3db888c Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 21 Jan 2020 11:37:53 +0100
Subject: Update exercise on unary languages.

---
 controle-20200123.tex | 44 +++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 39 insertions(+), 5 deletions(-)

diff --git a/controle-20200123.tex b/controle-20200123.tex
index e0c0c1f..b05f9d0 100644
--- a/controle-20200123.tex
+++ b/controle-20200123.tex
@@ -126,9 +126,14 @@ Git: \input{vcline.tex}
 
 Dans cet exercice, on pose $\Sigma = \{a\}$ (alphabet à une seule lettre).
 
-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.
+\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$ ;
@@ -165,8 +170,37 @@ $\mathscr{A}_3$ l'automate canonique ainsi obtenu.
 := \Sigma^*\setminus L$ complémentaire de $L$.  Ce langage $M$ est
 fini : énumérer exhaustivement les mots qu'il contient.
 
-(5) Quels sont les entiers naturels ne pouvant pas s'écrire sous la
-forme $3m+5n$ avec $m,n\in\mathbb{N}$ ?
+(5) En utilisant la question précédente, dire quels sont les entiers
+naturels ne pouvant pas s'écrire sous la forme $3m+5m'$ avec
+$m,m'\in\mathbb{N}$.
+
+\medbreak
+
+\textbf{Seconde partie : considérations générales.}
+
+(6) Expliquer rapidement pourquoi un automate déterministe complet
+$\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.
+
+(7) Une fois un automate déterministe complet sur $\Sigma$ présenté
+comme décrit à la question (6), à quelle condition le langage qu'il
+reconnaît est-il fini ?
+
+(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}$, 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.
 
 %
 %
-- 
cgit v1.2.3