summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2020-01-21 20:28:06 +0100
committerDavid A. Madore <david+git@madore.org>2020-01-21 20:28:06 +0100
commitca644c1d85015e1c4bce66d42db4922edd8729b0 (patch)
tree2f1815477a33fc02b4a1afaef36d070bf320b0d6
parentd491f645ae3b16b37b83e0b94d03fbcf5005c674 (diff)
downloadinf105-ca644c1d85015e1c4bce66d42db4922edd8729b0.zip
inf105-ca644c1d85015e1c4bce66d42db4922edd8729b0.tar.gz
inf105-ca644c1d85015e1c4bce66d42db4922edd8729b0.tar.bz2
Re-read test and answers.
-rw-r--r--controle-20200123.tex150
1 files changed, 87 insertions, 63 deletions
diff --git a/controle-20200123.tex b/controle-20200123.tex
index 374f3d3..00792d7 100644
--- a/controle-20200123.tex
+++ b/controle-20200123.tex
@@ -106,7 +106,7 @@ Durée : 1h30
Barème \emph{indicatif} : 2+(7+6)+5.
\ifcorrige
-Ce corrigé comporte 8 pages (page de garde incluse)
+Ce corrigé comporte 9 pages (page de garde incluse)
\else
Cet énoncé comporte 3 pages (page de garde incluse)
\fi
@@ -128,7 +128,7 @@ Git: \input{vcline.tex}
\exercice
-Soit $\mathscr{A}$ l'automate suivant sur l'alphabet $\Sigma :=
+Soit $\mathscr{A}$ l'automate fini suivant sur l'alphabet $\Sigma :=
\{a,b,c\}$ :
\begin{center}
@@ -170,7 +170,7 @@ $\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).
+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}
@@ -198,12 +198,16 @@ d'élimination.
\exercice\label{exercise-on-unary-languages}
-Dans cet exercice, on pose $\Sigma := \{a\}$ (alphabet à une seule lettre).
+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
@@ -255,12 +259,11 @@ 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
+$\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
@@ -272,8 +275,8 @@ mot $a^i$ par l'automate soit numéroté $i$.
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) :
+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
@@ -303,10 +306,13 @@ de $\mathscr{A}_1$). L'unique transition de l'automate (évidemment
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
+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, avec certains états finaux
+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
@@ -314,15 +320,13 @@ 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
+(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}
@@ -358,11 +362,11 @@ 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
+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 déterministe complet $\mathscr{A}_4$
+(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.
@@ -377,7 +381,7 @@ 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
+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\}$.)
@@ -395,46 +399,63 @@ $m,m'\in\mathbb{N}$.
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
+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) 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$.
+$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.}
-(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.
+\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 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$.
+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 an 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.)
+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é
@@ -448,8 +469,7 @@ 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$).
+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\} =
@@ -462,10 +482,14 @@ 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.
+\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
@@ -565,10 +589,10 @@ 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$.)
+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
@@ -598,10 +622,10 @@ 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
+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