diff options
Diffstat (limited to 'controle-20200123.tex')
| -rw-r--r-- | controle-20200123.tex | 150 |
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 |