diff options
Diffstat (limited to 'controle-20200123.tex')
| -rw-r--r-- | controle-20200123.tex | 648 |
1 files changed, 648 insertions, 0 deletions
diff --git a/controle-20200123.tex b/controle-20200123.tex new file mode 100644 index 0000000..28b074c --- /dev/null +++ b/controle-20200123.tex @@ -0,0 +1,648 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +\usepackage{hyperref} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +\newenvironment{commentaire}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}} +{{\hbox{}\nobreak\hfill\maltese}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% NOTE: compile dot files with +% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} +\ifcorrige +\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{23 janvier 2020} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +Dans l'exercice \ref{exercise-on-unary-languages}, les deux parties +peuvent en principe être traitées indépendamment, mais la première +donne un exemple aidant à comprendre la démarche de la seconde. + +\medbreak + +L'usage de tous les documents (notes de cours manuscrites ou +imprimées, feuilles d'exercices, livres) est autorisé. + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 1h30 + +Barème \emph{indicatif} : 2+(7+6)+5. + +\ifcorrige +Ce corrigé comporte 9 pages (page de garde incluse) +\else +Cet énoncé comporte 3 pages (page de garde incluse) +\fi + +\vfill + +{\tiny\noindent +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +Soit $\mathscr{A}$ l'automate fini suivant sur l'alphabet $\Sigma := +\{a,b,c\}$ : + +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (S1) at (70bp,35bp) [draw,circle,state] {$1$}; +\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$}; +\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$}; +\draw [->] (S0) -- node[auto,near end] {$\varepsilon$} (S1); +\draw [->] (S0) -- node[auto,below] {$\varepsilon$} (S2); +\draw [->] (S1) to[out=225,in=135] node[auto,left] {$a$} (S2); +\draw [->] (S2) to[out=45,in=315] node[auto,right] {$b$} (S1); +\draw [->] (S2) to[loop below] node[auto] {$c$} (S2); +\draw [->] (S1) -- node[auto] {$\varepsilon$} (S3); +\draw [->] (S2) -- node[auto,below,near end] {$\varepsilon$} (S3); +\end{tikzpicture} +\end{center} + +\vskip-\baselineskip\vskip-.5ex\noindent En lui appliquant la méthode +d'élimination des états, déterminer une expression rationnelle +dénotant le langage qu'il reconnaît. + +\begin{corrige} +L'élimination de l'état $1$ conduit à l'automate suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (S2) at (70bp,0bp) [draw,circle,state] {$2$}; +\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$}; +\draw [->] (S0) -- node[auto,below] {$\varepsilon|a$} (S2); +\draw [->] (S2) to[loop below] node[auto] {$c|ba$} (S2); +\draw [->] (S2) -- node[auto,below] {$\varepsilon|b$} (S3); +\draw [->] (S0) to[out=90,in=180] (60bp,35bp) -- node[auto] {$\varepsilon$} (80bp,35bp) to[out=0,in=90] (S3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-.5ex\noindent — et l'élimination de +l'état $2$ conduit alors à l'expression rationnelle suivante : +$\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 proprement menée conduit à ce qui a été dit). + +Si on élimine d'abord l'état $2$, on aboutit à l'automate suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (S1) at (70bp,0bp) [draw,circle,state] {$1$}; +\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$}; +\draw [->] (S0) -- node[auto,below] {$\varepsilon|c{*}b$} (S1); +\draw [->] (S1) to[loop below] node[auto] {$ac{*}b$} (S1); +\draw [->] (S1) -- node[auto,below] {$\varepsilon|ac{*}$} (S3); +\draw [->] (S0) to[out=90,in=180] (60bp,35bp) -- node[auto] {$c{*}$} (80bp,35bp) to[out=0,in=90] (S3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-.5ex\noindent — et à l'expression +rationnelle suivante : +$c{*}\;|\;(\varepsilon|c{*}b)\,(ac{*}b){*}\,(\varepsilon|ac{*})$. +Elle est, bien sûr, équivalente à celle obtenue avec l'autre ordre +d'élimination. +\end{corrige} + + +% +% +% + +\exercice\label{exercise-on-unary-languages} + +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 +complémentaire. + +(1) Traiter l'une \emph{ou} l'autre des questions suivantes : +(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ; +(ii) construire l'automate de Thompson de $r$, puis éliminer les +transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on +retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$ +l'automate ainsi obtenu. + +(Dans les deux cas, on obtient le même automate $\mathscr{A}_1$, ayant +$9$ états. À défaut de donner l'automate de Glushkov ou de Thompson, +donner un NFA reconnaissant $L$ pourra apporter une partie des +points.) + +\begin{corrige} +L'automate $\mathscr{A}_1$ obtenu est le suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$}; +\node (S1) at (60bp,35bp) [draw,circle,state] {$1$}; +\node (S2) at (120bp,35bp) [draw,circle,state] {$2$}; +\node (S3) at (180bp,35bp) [draw,circle,state,final] {$3$}; +\node (S1p) at (60bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$1'$\hss}}\phantom{$1$}}; +\node (S2p) at (120bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$2'$\hss}}\phantom{$2$}}; +\node (S3p) at (180bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$3'$\hss}}\phantom{$3$}}; +\node (S4p) at (240bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$4'$\hss}}\phantom{$4$}}; +\node (S5p) at (300bp,-35bp) [draw,circle,state,final] {\vbox to0pt{\vss\hbox to0pt{$5'$\hss}}\phantom{$5$}}; +\draw [->] (S0) -- node[auto] {$a$} (S1); +\draw [->] (S1) -- node[auto] {$a$} (S2); +\draw [->] (S2) -- node[auto] {$a$} (S3); +\draw [->] (S0) -- node[auto,below] {$a$} (S1p); +\draw [->] (S1p) -- node[auto,below] {$a$} (S2p); +\draw [->] (S2p) -- node[auto,below] {$a$} (S3p); +\draw [->] (S3p) -- node[auto,below] {$a$} (S4p); +\draw [->] (S4p) -- node[auto,below] {$a$} (S5p); +\draw [->] (S3) -- node[auto,above,near end] {$a$} (S1p); +\draw [->] (S5p) -- node[auto,below,very near end] {$a$} (S1); +\draw [->] (S3) to[out=90,in=0] (130bp,70bp) -- node[auto,below] {$a$} (110bp,70bp) to[out=180,in=90] (S1); +\draw [->] (S5p) to[out=210,in=0] (190bp,-70bp) -- node[auto,above] {$a$} (170bp,-70bp) to[out=180,in=330] (S1p); +\end{tikzpicture} +\end{center} +C'est l'automate de Glushkov. Si on commence par construire +l'automate de Thompson, celui-ci a $20$ états, et l'élimination des +transitions spontanées conduit à l'automate $\mathscr{A}_1$ qu'on +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 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 +correcteur), on renommera si nécessaire les états de $\mathscr{A}_2$ +de façon que, autant que possible, l'état résultant de la lecture du +mot $a^i$ par l'automate soit numéroté $i$. + +\begin{corrige} +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 (é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 +$1$&$\{1,1'\}$&\\\hline +$2$&$\{2,2'\}$&\\\hline +$3$&$\{3,3'\}$&F\\\hline +$4$&$\{1,1',4'\}$&\\\hline +$5$&$\{2,2',5'\}$&F\\\hline +$6$&$\{1,1',3,3'\}$&F\\\hline +$7$&$\{1,1',2,2',4'\}$&\\\hline +$8$&$\{2,2',3,3',5'\}$&F\\\hline +$9$&$\{1,1',3,3',4'\}$&F\\\hline +$10$&$\{1,1',2,2',4',5'\}$&F\\\hline +$11$&$\{1,1',2,2',3,3',5'\}$&F\\\hline +$12$&$\{1,1',2,2',3,3',4'\}$&F\\\hline +$13$&$\{1,1',2,2',3,3',4',5'\}$&F\\ +\end{tabular} +\end{center} +Le procédé de calcul de la table est le suivant : à chaque ligne à +partir de la deuxième, on incrémente tous les numéros avec et sans +prime, sauf que $3$ ou $5'$ deviennent $1,1'$ (les deux à la fois, +puisqu'il y a des transitions de $3$ et $5'$ vers $1$ et $1'$ +dans $\mathscr{A}_1$). Ceci permet de ne pas se tromper (d'où +l'intérêt d'avoir judicieusement étiqueté les états +de $\mathscr{A}_1$). L'unique transition de l'automate (évidemment +étiquetée $a$) conduit de chaque ligne à la ligne suivante, sauf la +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 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, certains états étant finaux +comme on vient de le dire. + +On renumérote alors les états comme selon la colonne de gauche de la +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) 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} +On a bien affaire pour commencer à un automate $\mathscr{A}_2$ +déterministe complet sans état inaccessible. + +L'algorithme de minimisation commence par partitionner l'ensemble +$\{0,\ldots,13\}$ des états en deux classes, les finaux +$\{0,3,5,6,8,9,10,11,12,13\}$ et les non-finaux $\{1,2,4,7\}$. Une +première itération sépare les finaux en $\{5,8,9,10,11,12,13\}$ et +$\{0,3,6\}$ (selon que l'état vers lequel aboutit l'unique transition +est lui-même final ou non) et les non-finaux en $\{2,4,7\}$ et $\{1\}$ +(idem). La seconde itération sépare chacun de $0$, $2$ et $5$ des +autres états de leur classe respective : les classes sont alors +$\{0\}$, $\{1\}$, $\{2\}$, $\{3,6\}$, $\{4,7\}$ et +$\{8,9,10,11,12,13\}$. La troisième itération sépare $4$ et $7$ +tandis que la quatrième sépare $3$ et $6$. Finalement, on obtient un +automate $\mathscr{A}_3$ canonique ayant $9$ états : un pour chaque +état de l'automate $\mathscr{A}_2$ entre $0$ et $7$ inclus, et un pour +tous les états de $8$ à $13$ inclus. + +On pouvait aussi arguër de manière plus abstraite : il est clair que +tous les états $8$ à $13$ devront être fusionnés puisqu'ils sont +finaux et que leurs transitions arbitrairement itérées ne conduisent +qu'à des états finaux, tandis que les états $0$ à $7$ inclus devront +être tous séparés puisqu'ils sont distingués par le nombre de +transitions à partir desquelles on n'arrive plus qu'à des états +finaux. + +On peut bien sûr tracer graphiquement l'automate $\mathscr{A}_3$ comme +d'habitude : c'est 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 $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) 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 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. + +\begin{corrige} +Il suffit d'échanger états finaux et non-finaux dans un automate +déterministe complet quelconque reconnaissant $L$, disons l'automate +$\mathscr{A}_3$ (on pouvait aussi utiliser $\mathscr{A}_2$ si on n'a +pas réussi à calculer $\mathscr{A}_3$). On peut bien sûr tracer +graphiquement l'automate $\mathscr{A}_4$ comme d'habitude : c'est +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) plus bas, l'automate +$\mathscr{A}_3$ est décrit par $j_2 = 9$, $j_1 = 8$ et $F = +\{1,2,4,7\}$.) + +L'état $8$ (i.e., le dernier) étant un puits dans +l'automate $\mathscr{A}_4$, les seuls mots acceptés le sont avant le +puits, et ce sont les mots $a$, $aa$, $aaaa = a^4$ et $aaaaaaa = a^7$ +comme donnés par les états finaux de $\mathscr{A}_4$. +\end{corrige} + +(5) En utilisant la question précédente, dire quels sont les (quatre) +entiers naturels ne pouvant pas s'écrire sous la forme $3m+5m'$ avec +$m,m'\in\mathbb{N}$. + +\begin{corrige} +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, +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), 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.} + +\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 ces é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} +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 en 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. 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é +comme décrit à la question (6), à quelle condition nécessaire et +suffisante (sur $j_1,j_2,F$) le langage qu'il reconnaît est-il fini ? + +\begin{corrige} +Les états $i$ tels que $j_1\leq i<j_2$ avec la notation introduite +en (6) sont des états résultat de la lecture d'un nombre infini de +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 é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\} = +\varnothing$, ou, ce qui revient au même, $F \subseteq +\{0,\ldots,j_1-1\}$ ; et le cas échéant, le langage est constitué des +$a^i$ pour $i\in F$ (et $i<j_1$). +\end{corrige} + +(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}$, 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 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 +questions précédentes : donnés $\ell_1,\ldots,\ell_r \in \mathbb{N}$, +on fabrique l'expression rationnelle +$(a^{\ell_1}|\cdots|a^{\ell_r}){*}$ sur $\Sigma$, on construit son +automate de Glushkov (ou de Thompson dont on élimine ensuite les +transitions spontanées), on le déterminise, on peut éventuellement le +minimiser même si ce n'est pas nécessaire pour cette question, on +échange états finaux et non-finaux pour obtenir un automate +reconnaissant le langage complémentaire, et enfin on utilise le +critère trouvé en (7) pour savoir si ce langage est fini et, le cas +échéant, l'énumérer. Par le même raisonnement qu'en (5), ceci donne +exactement les $a^n$ pour les $n$ 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}$. + +\emph{Remarque :} En fait, il s'avère que l'ensemble $\mathbb{N} +\setminus \{\ell_1 m_1 + \cdots + \ell_r m_r : (m_1,\ldots,m_r)\in +\mathbb{N}^r\}$ est fini si et seulement si le pgcd de +$\ell_1,\ldots,\ell_r$ vaut $1$ (i.e., si et seulement si ces nombres +sont premiers entre eux dans leur ensemble), ce qui est aussi testable +algorithmiquement ; mais ce n'était pas demandé ici, et ceci ne résout +pas la question d'énumérer explicitement l'ensemble. +\end{corrige} + + +% +% +% + +\exercice + +On considère la grammaire hors-contexte $G$ d'axiome $S$ et de +nonterminaux $N = \{S, T, U\}$ sur l'alphabet $\Sigma = \{a,b,c\}$ +donnée par +\[ +\begin{aligned} +S &\rightarrow T \;|\; TaS\\ +T &\rightarrow U \;|\; UbT\\ +U &\rightarrow c\\ +\end{aligned} +\] +(La grammaire en question est inambiguë : on ne demande pas de le +démontrer.) + +(1) Donner les arbres d'analyse (= de dérivation) des mots suivants : +$cacbcac$ et $cbcacbc$. + +\begin{corrige} +On obtient les arbres d'analyse suivants : + +\hbox to\hsize{ +% S<T<U<c.>>a.S<T<U<c.>b.T<U<c.>>>a.S<T<U<c.>>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (37.778bp,0.000bp) [draw=none] {$S$}; +\node (T0) at (0.000bp,-30.000bp) [draw=none] {$T$}; \draw (S0) -- (T0); +\node (U0) at (0.000bp,-50.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (c0) at (0.000bp,-70.000bp) [draw=none] {$c$}; \draw (U0) -- (c0); +\node (a0) at (20.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S1) at (93.333bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (T1) at (60.000bp,-60.000bp) [draw=none] {$T$}; \draw (S1) -- (T1); +\node (U1) at (40.000bp,-90.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (c1) at (40.000bp,-110.000bp) [draw=none] {$c$}; \draw (U1) -- (c1); +\node (b0) at (60.000bp,-90.000bp) [draw=none] {$b$}; \draw (T1) -- (b0); +\node (T2) at (80.000bp,-90.000bp) [draw=none] {$T$}; \draw (T1) -- (T2); +\node (U2) at (80.000bp,-110.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (c2) at (80.000bp,-130.000bp) [draw=none] {$c$}; \draw (U2) -- (c2); +\node (a1) at (100.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a1); +\node (S2) at (120.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (T3) at (120.000bp,-80.000bp) [draw=none] {$T$}; \draw (S2) -- (T3); +\node (U3) at (120.000bp,-100.000bp) [draw=none] {$U$}; \draw (T3) -- (U3); +\node (c3) at (120.000bp,-120.000bp) [draw=none] {$c$}; \draw (U3) -- (c3); +\end{tikzpicture} +\hss et\hss +% S<T<U<c.>b.T<U<c.>>>a.S<T<U<c.>b.T<U<c.>>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (60.000bp,0.000bp) [draw=none] {$S$}; +\node (T0) at (20.000bp,-30.000bp) [draw=none] {$T$}; \draw (S0) -- (T0); +\node (U0) at (0.000bp,-60.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (c0) at (0.000bp,-80.000bp) [draw=none] {$c$}; \draw (U0) -- (c0); +\node (b0) at (20.000bp,-60.000bp) [draw=none] {$b$}; \draw (T0) -- (b0); +\node (T1) at (40.000bp,-60.000bp) [draw=none] {$T$}; \draw (T0) -- (T1); +\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (c1) at (40.000bp,-100.000bp) [draw=none] {$c$}; \draw (U1) -- (c1); +\node (a0) at (60.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S1) at (100.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (T2) at (100.000bp,-50.000bp) [draw=none] {$T$}; \draw (S1) -- (T2); +\node (U2) at (80.000bp,-80.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (c2) at (80.000bp,-100.000bp) [draw=none] {$c$}; \draw (U2) -- (c2); +\node (b1) at (100.000bp,-80.000bp) [draw=none] {$b$}; \draw (T2) -- (b1); +\node (T3) at (120.000bp,-80.000bp) [draw=none] {$T$}; \draw (T2) -- (T3); +\node (U3) at (120.000bp,-100.000bp) [draw=none] {$U$}; \draw (T3) -- (U3); +\node (c3) at (120.000bp,-120.000bp) [draw=none] {$c$}; \draw (U3) -- (c3); +\end{tikzpicture} +} + +(On les trouve plus facilement si on se convainc d'abord que la +grammaire peut être vue comme décrivant une expression de termes $c$ +reliés par deux opérations binaires $a$ et $b$, toutes les deux +associatives à droite, et l'opération $b$ étant prioritaire sur $a$. +Autrement dit, l'expression dérivant de $S$ est coupée d'abord au +niveau des $a$ en des sous-expressions dérivant de $T$, elles-mêmes +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$.) + +\begin{corrige} +Le langage $L' = L(G,T)$ est celui décrit par la grammaire $T +\rightarrow c \;|\; cbT$ d'axiome $T$ (le nonterminal $U$ est +visiblement inutile et peut être directement remplacé par $c$ pour y +voir plus clair). Il s'agit visiblement du langage dénoté par +l'expression rationnelle $(cb){*}c$ (ceci se démontre par exemple en +remarquant que ses dérivations sont toutes de la forme $T \Rightarrow +cbT \Rightarrow \cdots \Rightarrow (cb)^k T \Rightarrow (cb)^k c$, ou +en raisonnant sur les arbres d'analyse qui sont formés en empilant des +$T$ ayant pour fils gauche $c$ et $b$ et pour fils droite un autre $T$ +jusqu'à un dernier $T$ qui a pour seul fils $c$ ; on peut aussi +remarquer qu'il s'agit essentiellement d'une grammaire régulière) : si +on préfère, $L'$ est le plus petit langage tel que $L' = \{c\} \cup +(\{c\}\{b\}L')$, ce que dénote justement $(cb){*}c$. Bref, un mot de +$L'$ est une succession de $c$ séparés par des $b$, ce que dénote +justement $(cb){*}c$. + +Le langage $L = L(G,S)$ est construit selon exactement le même modèle +à partir de $L'$ que $L'$ à partir de $c$ : si on préfère, $L$ est le +plus petit langage tel que $L = L' \cup (L'\{a\}L)$, donc on s'attend +à avoir ce qu'il soit dénoté par $((cb){*}ca){*}(cb){*}c$. On peut +par exemple raisonner sur les arbres d'analyse : ils sont formés en +empilant des $S$ ayant pour fils gauche $T$ et $a$ et pour fils droite +un autre $S$ jusqu'à un dernier $S$ qui a pour seul fils $T$, et enfin +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$ 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 +langage. +\end{corrige} + + +% +% +% +\end{document} |