diff options
| -rw-r--r-- | exercices1.tex | 48 |
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 %%% |