summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-30 16:49:22 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-30 16:49:22 +0100
commit5bfe437e9e7087fc3ddaf2cbdf49cbef51fe9b31 (patch)
tree9c8ff251d3b799f46083cf7a620ccc505d872410
parent89e92ec19feb388823f66885a633351369c5e809 (diff)
downloadinf105-5bfe437e9e7087fc3ddaf2cbdf49cbef51fe9b31.tar.gz
inf105-5bfe437e9e7087fc3ddaf2cbdf49cbef51fe9b31.tar.bz2
inf105-5bfe437e9e7087fc3ddaf2cbdf49cbef51fe9b31.zip
Re-read exercise sheet.
-rw-r--r--exercices1.tex48
1 files changed, 25 insertions, 23 deletions
diff --git a/exercices1.tex b/exercices1.tex
index f3a7115..d51e3b7 100644
--- a/exercices1.tex
+++ b/exercices1.tex
@@ -104,16 +104,15 @@ expression rationnelle qui le dénote, et montrer qu'il est
reconnaissable en exhibant directement un automate fini qui le
reconnaît.
-(2) On définit la \emph{valeur numérique} d'un mot sur $\Sigma$
-(=: mot binaire) $x_{n-1}\cdots x_0$ comme $\sum_{i=0}^{n-1} x_i 2^i$
-(où $x_i$ vaut $0$ ou $1$ et est numéroté de $0$ pour le chiffre le
-plus à droite à $n-1$ pour le plus à gauche) ; la valeur numérique du
-mot vide $\varepsilon$ est $0$.
+(2) On définit la \emph{valeur numérique} d'un mot binaire
+$x_{n-1}\cdots x_0$ comme $\sum_{i=0}^{n-1} x_i 2^i$ (où $x_i$ vaut
+$0$ ou $1$ et est numéroté de $0$ pour le chiffre le plus à droite
+à $n-1$ pour le plus à gauche) ; la valeur numérique du mot
+vide $\varepsilon$ est $0$.
-Parmi les langages suivants, certains sont rationnels, d'autres ne le
-sont pas. Dire lesquels sont rationnels et justifier brièvement
-pourquoi (on ne demande pas de justifier pourquoi ceux qui ne sont pas
-rationnels ne le sont pas) :
+Parmi les langages suivants, certains sont rationnels. Dire lesquels
+et justifier brièvement pourquoi ils le sont (on ne demande pas de
+justifier pourquoi ceux qui ne sont pas rationnels ne le sont pas) :
(a) le langage $L_a$ des mots binaires dont la valeur numérique est
paire,
@@ -133,8 +132,8 @@ nombre premier,
une puissance de $2$,
\begin{corrige}
-(1) On peut écrire $L_n = L_r$, langage dénoté par l'expression
- rationnelle $r := 0|1(0|1){*}$. Ce langage est reconnu, par
+(1) On peut écrire $L_n = L_{0|1(0|1){*}}$, langage dénoté par
+ l'expression rationnelle $0|1(0|1){*}$. Ce langage est reconnu, par
exemple, par le DFAI suivant :
\begin{center}
%%% begin ex1p1 %%%
@@ -158,7 +157,8 @@ mots binaires qui soit sont le mot vide soit finissent par $0$ : il
est dénoté par l'expression rationnelle
$\underline{\varepsilon}|(0|1){*}0$.\spaceout (b) On a $L_b = L_a \cap
L_n$ et on a vu que $L_a$ et $L_n$ sont rationnels, donc $L_b$ l'est
-aussi.
+aussi (on peut aussi exhiber une expression rationnelle qui le
+dénote : $0|1(0|1){*}0$).
(c) Ajouter un $0$ ou un $1$ à la fin d'un mot binaire de valeur
numérique $n$ le transforme en un mot de valeur numérique $2n+x$
@@ -206,8 +206,8 @@ veut reconnaître les multiples de $3$.)
(d) Le langage $L_d$ n'est pas rationnel (on pourrait le démontrer à
l'aide du lemme de pompage, mais ce n'est pas très facile).
-(e) Le langage $L_e$ est rationnel car il s'agit du langage des dénoté
-par l'expression rationnelle $10{*}$.
+(e) Le langage $L_e$ est rationnel car il s'agit du langage dénoté par
+l'expression rationnelle $10{*}$.
\end{corrige}
@@ -289,7 +289,7 @@ en (0).
(1) L'automate ayant des ε-transitions, il ne peut pas être
déterministe : on a affaire à un εNFA. Avant de le déterminiser, on
- élimine ses ε-transitions : la ε-fermeture de $0$ est $\{1,4\}$,
+ élimine ses ε-transitions : la ε-fermeture de $0$ est $\{0,1,4\}$,
celle de $3$ est $\{3,7\}$ et celle de $6$ est $\{6,7\}$ ; on est
amené au NFA suivant :
\begin{center}
@@ -316,10 +316,12 @@ en (0).
%%% end ex1p2b %%%
\end{center}
-(Les états $1$ et $4$ étant inaccessibles, ils ont été retirés.)
+(Les états $1$ et $4$ étant inaccessibles, ils ont été retirés. Il ne
+faut pas oublier que $3$ et $6$ sont finaux puisqu'il sont l'état
+final $7$ dans leur ε-fermeture.)
-On peut maintenant procéder à la minimisation. Pour abréger les noms
-des états, on note, par exemple, $023$ pour $\{0,2,3\}$. En
+On peut maintenant procéder à la déterminisation. Pour abréger les
+noms des états, on note, par exemple, $023$ pour $\{0,2,3\}$. En
construisant de proche en proche, on obtient le DFA suivant :
\begin{center}
\scalebox{0.8}{%PLEASE! There HAS to be a better way to do this!
@@ -389,9 +391,9 @@ construisant de proche en proche, on obtient le DFA suivant :
}
\end{center}
(À titre d'exemple, la transition étiquetée $b$ partant de l'état
-$023$ conduit à l'état $057$ car les transitions étiquetées $b$ dans
-le NFA précédent et partant des états parmi $\{0,2,3\}$ sont $0\to 0$,
-$0\to 5$, $3\to 7$ et $7\to 7$. Tous les états contenant l'un des
+$0237$ conduit à l'état $057$ car les transitions étiquetées $b$ dans
+le NFA précédent et partant des états parmi $\{0,2,3,7\}$ sont $0\to
+0$, $0\to 5$, $3\to 7$ et $7\to 7$. Tous les états contenant l'un des
symboles $3,6,7$ sont finaux.)
(2) On a affaire à un DFA dont tous les états sont accessibles, on
@@ -400,8 +402,8 @@ partition sépare les états finaux, soit $023, 0237, 027, 056, 0567,
057$ des non-finaux, soit $0, 02, 05$. L'étape suivante distingue
$02$ parce que sa $a$-transition conduit à une classe différente que
celles de $0$ et $05$, et $05$ parce que sa $b$-transition conduit à
-une classe différente de $0$ et $02$. Finalement, on arrive à un
-automate à quatre états :
+une classe différente de $0$ et $02$. Les étapes suivantes ne
+changent rien. Finalement, on arrive à un automate à quatre états :
\begin{center}
%%% begin ex1p2d %%%