diff options
Diffstat (limited to 'controle-20220616.tex')
| -rw-r--r-- | controle-20220616.tex | 674 |
1 files changed, 674 insertions, 0 deletions
diff --git a/controle-20220616.tex b/controle-20220616.tex new file mode 100644 index 0000000..7439a45 --- /dev/null +++ b/controle-20220616.tex @@ -0,0 +1,674 @@ +%% 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{16 juin 2022} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants (le premier teste +l'application d'algorithmes vus en cours, le second est de nature plus +théorique). 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. + +\medbreak + +Le sujet étant long pour le temps imparti, il ne sera pas nécessaire +de traiter toutes les questions pour obtenir la totalité des points. + +\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} : autant de points pour chaque exercice. + +\ifcorrige +Ce corrigé comporte 9 pages (page de garde incluse). +\else +Cet énoncé comporte 4 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 + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On considère +l'expression rationnelle $r := a{*}b{*}a{*}$, et soit $L := L(r)$ le +langage qu'elle dénote. + +(0) Pour chacun des mots suivants, dire si oui ou non il appartient +à $L$ (c'est-à-dire s'il vérifie $r$) : $\varepsilon$ (le mot vide), +$a$, $b$, $ab$, $ba$, $aa$, $aba$, $bab$, $abab$. On ne demande pas +de justifier les réponses. + +\begin{corrige} +Les mots $\varepsilon$, $a$, $b$, $ab$, $ba$, $aa$, $aba$ +appartiennent à $L$ ; les mots $bab$ et $baba$ n'appartiennent pas +à $L$. +\end{corrige} + +\emph{Il est fortement conseillé, dans toutes les questions suivantes, + d'utiliser les mots qui viennent d'être listés pour vérifier les + automates successifs qu'on calculera.} (Par exemple, pour un +automate censé reconnaître le langage $L$, on vérifiera qu'il accepte +bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux +qu'on a identifiés comme n'appartement pas à $L$.) Les fautes qui +auraient dû être détectées par cette vérification pourront être plus +lourdement sanctionnées. + +(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 fini $\mathscr{A}_1$, +et il a $4$ é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$ trouvé est le suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,final,accepting below] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,final] {$3$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q0) to[out=295,in=245] node[auto,below]{$b$} (q2); +\draw[->] (q1) to[out=295,in=245] node[auto,below]{$a$} (q3); +\draw[->] (q0) to[out=270,in=270] node[auto,below]{$a$} (q3); +\end{tikzpicture} +\end{center} +(on remarquera notamment que tous ses états sont finaux). +\end{corrige} + +(2) Déterminiser l'automate $\mathscr{A}_1$. On appellera +$\mathscr{A}_2$ l'automate en question. On rappelle qu'on attend ici +un automate fini \emph{déterministe complet} ; pour information, il a +$5$ états. + +\begin{corrige} +L'automate $\mathscr{A}_2$ trouvé est le suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$\scriptstyle\{0\}$}; +\node (q1) at (30bp,52bp) [draw,circle,state,final,accepting right] {$\scriptstyle\{1,3\}$}; +\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{2\}$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{3\}$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (q0) -- node[auto]{$b$} (q2); +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto,near end]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (qF); +\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(3) Minimiser l'automate $\mathscr{A}_2$. On appellera +$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du +langage $L$). Pour information, cet automate a $4$ états : pour la +commodité du correcteur, on les appellera $1,2,3,\bot$ dans l'ordre +dans lequel ils sont parcourus lorsque l'automate consomme le +mot $bab$. + +\begin{corrige} +L'automate $\mathscr{A}_2$ est déterministe complet sans état +inaccessible. On commence l'algorithme de minimisation en séparant +les états finaux $\{0\},\{1,3\},\{2\},\{3\}$ et l'état +non-final $\varnothing$. On sépare ensuite les premiers selon que la +transition étiquetée $b$ conduit à un état non-final, ce qui +sépare $\{3\}$ du reste, et enfin selon que la transition +étiquetée $a$ conduit à cet état $\{3\}$, ce qui sépare $\{2\}$ du +reste. Finalement, on aboutit aux classes suivantes : $\{0\} \equiv +\{1,3\}$, $\{2\}$, $\{3\}$ et $\varnothing$ (qu'on rebaptise +$1,2,3,\bot$ respectivement), et à l'automate minimal $\mathscr{A}_3$ +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$}; +\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$}; +\draw[->] (q1) to[loop above] node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (qF); +\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(4) Donner de même l'automate minimal $\mathscr{A}_4$ du langage $L' +:= L(r')$ dénoté par l'expression rationnelle $r' := b{*}a{*}b{*}$. +Comme cette expression, et donc cet automate, sont simplement obtenus +en échangeant $a$ et $b$ par rapport à ce qui précède, on donnera +directement l'automate sans passer par les questions intermédiaires. + +\begin{corrige} +L'automate minimal $\mathscr{A}_4$ de $L'$ s'obtient simplement en +échangeant $a$ et $b$ dans $\mathscr{A}_3$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$}; +\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$}; +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$a$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$a$} (q2); +\draw[->] (q2) -- node[auto]{$b$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$b$} (q3); +\draw[->] (q3) -- node[auto]{$a$} (qF); +\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(5) En utilisant une construction de type « automate produit », donner +un automate déterministe complet $\mathscr{A}_5$, ayant $4\times 4 = +16$ états, qui reconnaît le langage $M := L \cap L'$ (constitué des +mots vérifiant à la fois $r$ et $r'$). On prendra garde pour la +question suivante au fait que cet automate possède des états +inaccessibles. + +\begin{corrige} +En prenant le produit des automates +$\mathscr{A}_3$ et $\mathscr{A}_4$, on aboutit à l'automate suivant +(où on a noté $q,q'$ l'état correspondant au couple $(q,q')$ d'un état +$q$ de $\mathscr{A}_3$ et $q'$ de $\mathscr{A}_4$ ; par exemple, +$\delta((1,1),a) = (1,2)$ car $\delta_{\mathscr{A}_3}(1,a) = 1$ et +$\delta_{\mathscr{A}_4}(1,a) = 2$) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q11) at (0bp,0bp) [draw,circle,state,initial,accepting by double] {\footnotesize$1,1$}; +\node (q12) at (60bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,2$}; +\node (q13) at (120bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,3$}; +\node (q1F) at (180bp,0bp) [draw,circle,state] {\footnotesize$1,\bot$}; +\node (q21) at (0bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,1$}; +\node (q22) at (60bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,2$}; +\node (q23) at (120bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,3$}; +\node (q2F) at (180bp,-60bp) [draw,circle,state] {\footnotesize$2,\bot$}; +\node (q31) at (0bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,1$}; +\node (q32) at (60bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,2$}; +\node (q33) at (120bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,3$}; +\node (q3F) at (180bp,-120bp) [draw,circle,state] {\footnotesize$3,\bot$}; +\node (qF1) at (0bp,-180bp) [draw,circle,state] {\footnotesize$\bot,1$}; +\node (qF2) at (60bp,-180bp) [draw,circle,state] {\footnotesize$\bot,2$}; +\node (qF3) at (120bp,-180bp) [draw,circle,state] {\footnotesize$\bot,3$}; +\node (qFF) at (180bp,-180bp) [draw,circle,state] {\footnotesize$\bot,\bot$}; +\draw[->] (q11) -- node[auto]{$b$} (q21); +\draw[->] (q11) -- node[auto]{$a$} (q12); +\draw[->] (q12) -- node[auto]{$b$} (q23); +\draw[->] (q12) to[loop above] node[auto]{$a$} (q12); +\draw[->] (q13) -- node[auto]{$b$} (q23); +\draw[->] (q13) -- node[auto]{$a$} (q1F); +\draw[->] (q1F) -- node[auto]{$b$} (q2F); +\draw[->] (q1F) to[loop right] node[auto]{$a$} (q1F); +\draw[->] (q21) to[loop left] node[auto]{$b$} (q21); +\draw[->] (q21) -- node[auto]{$a$} (q32); +\draw[->] (q22) -- node[auto]{$b$} (q23); +\draw[->] (q22) -- node[auto]{$a$} (q32); +\draw[->] (q23) to[loop right] node[auto]{$b$} (q23); +\draw[->] (q23) -- node[auto]{$a$} (q3F); +\draw[->] (q2F) to[loop right] node[auto]{$b$} (q2F); +\draw[->] (q2F) -- node[auto]{$a$} (q3F); +\draw[->] (q31) -- node[auto]{$b$} (qF1); +\draw[->] (q31) -- node[auto]{$a$} (q32); +\draw[->] (q32) -- node[auto]{$b$} (qF3); +\draw[->] (q32) to[loop below] node[auto]{$a$} (q32); +\draw[->] (q33) -- node[auto]{$b$} (qF3); +\draw[->] (q33) -- node[auto]{$a$} (q3F); +\draw[->] (q3F) -- node[auto]{$b$} (qFF); +\draw[->] (q3F) to[loop right] node[auto]{$a$} (q3F); +\draw[->] (qF1) to[loop below] node[auto]{$b$} (qF1); +\draw[->] (qF1) -- node[auto]{$a$} (qF2); +\draw[->] (qF2) -- node[auto]{$b$} (qF3); +\draw[->] (qF2) to[loop below] node[auto]{$a$} (qF2); +\draw[->] (qF3) to[loop below] node[auto]{$b$} (qF3); +\draw[->] (qF3) -- node[auto]{$a$} (qFF); +\draw[->] (qFF) to[loop below] node[auto]{$a,b$} (qFF); +\end{tikzpicture} +\end{center} +Pour plus de lisibilité, on a ici noté les états finaux en les +entourant deux fois plutôt qu'avec une flèche sortante. +\end{corrige} + +(6) Minimiser l'automate $\mathscr{A}_5$. On appellera +$\mathscr{A}_6$ l'automate minimal ainsi obtenu (automate canonique du +langage $M = L \cap L'$). Pour information, cet automate a $6$ états. + +\begin{corrige} +On commence par ne conserver que les états accessibles depuis l'état +initial, c'est-à-dire ceux étiquetés $(1,1)$, $(1,2)$, $(2,1)$, +$(2,3)$, $(3,2)$, $(3,\bot)$, $(\bot,3)$ et $(\bot,\bot)$ dans la +représentation ci-dessus, pour avoir un automate déterministe complet +sans état inaccessible. On applique ensuite l'algorithme de +minimisation de manière semblable à la question (3) : les états +non-finaux vont toujours rester groupés, et les états finaux sont +séparés un par un. Finalement, on aboutit à l'automate +$\mathscr{A}_6$ suivant comme automate minimal du langage $M$ (on a +rebaptisé les états ainsi : $(1,1)\rightsquigarrow 1$, +$(2,1)\rightsquigarrow 2$, $(3,2)\rightsquigarrow 3$, +$(1,2)\rightsquigarrow 2'$, $(2,3)\rightsquigarrow 3'$, et +$(3,\bot)\equiv (\bot,3) \equiv (\bot,\bot) \rightsquigarrow \bot$) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$}; +\node (q2a) at (60bp,42bp) [draw,circle,state,final,accepting below] {$2'$}; +\node (q3a) at (120bp,42bp) [draw,circle,state,final,accepting below] {$3'$}; +\node (q2) at (60bp,-42bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (120bp,-42bp) [draw,circle,state,final,accepting below] {$3$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$}; +\draw[->] (q1) -- node[auto]{$a$} (q2a); +\draw[->] (q1) -- node[auto,below]{$b$} (q2); +\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a); +\draw[->] (q2a) -- node[auto]{$b$} (q3a); +\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a); +\draw[->] (q3a) -- node[auto]{$a$} (qF); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto,below]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto,below]{$b$} (qF); +\draw[->] (qF) to[loop right] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(7) En appliquant l'algorithme d'élimination des états, déduire +de $\mathscr{A}_6$ une expression rationnelle $s$ dénotant le +langage $M$. Pour obtenir une expression raisonnablement simple, on +recommande d'éliminer les états en commençant par ceux qui sont à la +distance la plus éloignée de l'état initial. + +\begin{corrige} +On commence par effacer l'état puits (qui ne sert à rien) et par créer +un unique état final sans transition qui en parte : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$}; +\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$}; +\node (q3a) at (120bp,42bp) [draw,circle,state] {$3'$}; +\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$}; +\node (q3) at (120bp,-42bp) [draw,circle,state] {$3$}; +\node (qT) at (180bp,0bp) [draw,circle,state,final] {$\infty$}; +\draw[->] (q1) -- node[auto]{$a$} (q2a); +\draw[->] (q1) -- node[auto,below]{$b$} (q2); +\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a); +\draw[->] (q2a) -- node[auto]{$b$} (q3a); +\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a); +\draw[->] (q2a) -- node[auto,below]{$\varepsilon$} (qT); +\draw[->] (q3a) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q2) to[loop below] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto,below]{$a$} (q3); +\draw[->] (q3) to[loop below] node[auto]{$a$} (q3); +\draw[->] (q2) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q3) -- node[auto,below]{$\varepsilon$} (qT); +\end{tikzpicture} +\end{center} + +On peut alors éliminer les états $3$ et $3'$ (il n'y a pas +d'interaction entre eux) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$}; +\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$}; +\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$}; +\node (qT) at (120bp,0bp) [draw,circle,state,final] {$\infty$}; +\draw[->] (q1) -- node[auto]{$a$} (q2a); +\draw[->] (q1) -- node[auto,below]{$b$} (q2); +\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a); +\draw[->] (q2a) -- node[auto]{$\varepsilon|bb{*}$} (qT); +\draw[->] (q2) to[loop below] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto,below,near end]{$\varepsilon|aa{*}$} (qT); +\end{tikzpicture} +\end{center} + +Et finalement, en éliminant les états $2$ et $2'$, on trouve +l'expression rationnelle suivante qui dénote le langage $M$ : +\[ +\varepsilon\,|\,aa{*}(\varepsilon|bb{*})\,|\,bb{*}(\varepsilon|aa{*}) +\] +(il y a bien sûr d'autres écritures possibles ; par exemple, si on +élimine d'abord $2$ et $2'$ puis $3$ et $3'$ on obtient : +$\varepsilon\,|\,aa{*}\,|\,bb{*}\,|\,aa{*}bb{*}\,|\,bb{*}aa{*}$ ; +l'expression rationnelle $\varepsilon\,|\,aa{*}b{*}\,|\,bb{*}a{*}$ est +encore équivalente, mais elle ne s'obtient pas par la procédure +d'élimination des états). +\end{corrige} + + +% +% +% + +\exercice + +Les parties (A), (B) et (C) de cet exercice sont indépendantes. On ne +demande pas de justifications très longues. + +\medskip + +\textbf{(A)} On se propose de montrer que la question de savoir si +une grammaire hors contexte $G$ (sur un alphabet $\Sigma$ fixé) +vérifie $L(G) \neq \varnothing$ est décidable. Autrement dit, on +veut montrer qu'il existe un algorithme qui prend en entrée une +grammaire hors contexte $G$, termine toujours en temps fini, et +renvoie « vrai » si $L(G) \neq \varnothing$ et « faux » si $L(G) = +\varnothing$. + +(1) Expliquer pourquoi $L(G) \neq \varnothing$ si et seulement si il +existe un arbre d'analyse $\mathscr{T}$ pour $G$. (Un « arbre +d'analyse pour $G$ » désigne un arbre d'analyse d'un mot quelconque +selon $G$.) + +\begin{corrige} +Tout mot de $L(G)$ a (au moins) un arbre d'analyse pour $G$, et tout +arbre d'analyse pour $G$ est l'arbre d'analyse d'un mot de $L(G)$ : +ainsi, si $L(G) \neq \varnothing$, il existe un arbre d'analyse +pour $G$, et si $L(G) = \varnothing$ il n'existe pas d'arbre d'analyse +pour $G$. +\end{corrige} + +$\bullet$ Pour les questions suivantes, on introduit la terminologie +suivante : si $\mathscr{T}$ est un arbre et $n$ un nœud (=sommet) +de $\mathscr{T}$, on dit qu'un nœud $n'$ est un \textbf{descendant} de +$n$ lorsque $n'$ est soit égal à $n$, soit est un fils de $n$, soit +est un fils d'un fils de $n$, etc., à n'importe quelle profondeur. +L'ensemble des descendants de $n$ (y compris $n$ lui-même) est donc un +arbre ayant $n$ pour racine, qu'on appelle \textbf{sous-arbre qui + descend} de $n$. + +(2) Montrer que s'il existe un arbre d'analyse $\mathscr{T}$ pour $G$, +il en existe un vérifiant la propriété additionnelle suivante : +($\dagger$) « si un nœud $n$ est étiqueté par un nonterminal $X$, +alors aucun nœud $n' \neq n$ descendant de $n$ ne porte la même +étiquette $X$ ». + +\textit{Indication.}\quad Pour cela, on pourra remarquer que si un +arbre $\mathscr{T}$ ne vérifie pas ($\dagger$), on peut en construire +un autre ayant strictement moins de nœuds, en remplaçant le sous-arbre +qui descend de $n$ par celui qui descend de $n'$, et expliquer +pourquoi c'est encore un arbre d'analyse pour $G$ si $\mathscr{T}$ en +est un (pas nécessairement du même mot). + +\begin{corrige} +Si $\mathscr{T}$ est un arbre d'analyse pour $G$ dans lequel un nœud +$n'$ descendant d'un autre nœud $n$ est étiqueté par le même +symbole $X$, alors on peut fabriquer un arbre $\mathscr{T}'$ en +remplaçant le sous-arbre qui descend de $n$ par celui qui descend +de $n'$. Cet arbre $\mathscr{T}'$ a strictement moins de nœuds +que $\mathscr{T}$ car ses nœuds sont exactement ceux de $\mathscr{T}$ +à l'exception de ceux qui descendent de $n$ mais pas de $n'$. Par +ailleurs, c'est toujours un arbre d'analyse pour $G$ car chaque nœud a +des fils étiquetés exactement de la même manière (le seul pour lequel +ce n'est pas évident est le nœud parent de $n$, mais c'est bien vrai +car $n'$ et $n$ ont la même étiquette $X$). + +Si on considère maintenant $\mathscr{T}$ l'arbre d'analyse pour $G$ +ayant le nombre minimal de nœuds, il vérifie forcément ($\dagger$), +sans quoi la construction qu'on vient de donner produirait un arbre +$\mathscr{T}'$ ayant strictement moins de nœuds, contredisant la +minimalité. Il existe donc bien un arbre d'analyse pour $G$ +vérifiant ($\dagger$) (dès lors qu'il existe un arbre d'analyse +pour $G$ tout court). +\end{corrige} + +$\bullet$ Pour la question suivante, on dira qu'un arbre $\mathscr{T}$ +est de \textbf{valence} $\leq k$ lorsque chaque nœud de $\mathscr{T}$ +a au plus $k$ fils. + +(3) Montrer que, quels que soient les entiers naturels $k$ et $m$, il +n'y a qu'un nombre fini d'arbres de valence $\leq k$, dont les sommets +sont étiquetés par des étiquettes prises dans un ensemble +$\{Z_1,\ldots,Z_m\}$ de cardinal $m$, et vérifiant la propriété +($\dagger$) de la question précédente. Plus précisément, on pourra +montrer que le nombre de tels arbres est donné par $N(k,m)$ défini par +la récurrence $N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$ (et $N(k,0) = +0$) en considérant l'étiquette de la racine (parmi $m$ possibles) et +les $r \leq k$ sous-arbres qui descendent de ses fils. + +\begin{corrige} +Un arbre $\mathscr{T}$ de valence $\leq k$ vérifiant ($\dagger$) et +dont les étiquettes sont prises parmi $\{Z_1,\ldots,Z_m\}$ s'obtient +en choisissant l'étiquette $Z_i$ de la racine parmi $m$ possibles, le +nombre $0\leq r\leq k$ de fils de la racine, et les sous-arbres +$\mathscr{T}_1,\ldots,\mathscr{T}_r$ qui en descendent, qui sont +eux-mêmes des arbres de valence $\leq k$ vérifiant ($\dagger$) et dont +les étiquettes sont prises parmi $\{Z_1,\ldots,Z_m\} \setminus +\{Z_i\}$, c'est-à-dire parmi $m-1$ possibles. Par récurrence sur $m$, +on montre donc que ce nombre est fini, et précisément qu'il vérifie +$N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$. +\end{corrige} + +(4) En déduire un algorithme répondant à la question posée. + +\textit{Indication.}\quad Si $k$ est la longueur maximale d'une +production de la grammaire $G$, on pourra chercher à construire tous +les arbres de valence $\leq k$, étiquetés par des terminaux ou +nonterminaux ou $\varepsilon$, vérifiant de plus la +propriété ($\dagger$), et regarder s'il y a un arbre d'analyse parmi +eux. + +\begin{corrige} +Si $k$ est la longueur maximale d'une production de la grammaire $G$ +et $m$ le nombre d'étiquettes possibles d'un arbre d'analyse selon $G$ +(c'est-à-dire le nombre de nonterminaux plus le nombre de terminaux +plus $1$ pour $\varepsilon$, mais peu importe), on commence par +énumérer tous les arbres de valence $\leq k$, étiquetés par les tokens +en question, ce qui est possible d'après la question précédente (et +effectif avec la récursion évidente sur $m$). Il suffit ensuite de +tester tous ces arbres concevables et de vérifie si, à chaque nœud, +les contraintes imposées à un arbre d'analyse sont vérifiées. Soit on +trouve un arbre d'analyse pour $G$, auquel cas on a montré $L(G) \neq +\varnothing$ et on peut répondre « vrai » ; soit il n'y a aucun arbre +d'analyse pour $G$ vérifiant ($\dagger$), donc aucun d'arbre d'analyse +pour $G$ d'après la question (2), donc $L(G) = \varnothing$ +d'après (1) et on peut répondre « faux ». +\end{corrige} + +\medbreak + +\textbf{(B)} Montrer que la question de savoir si (pour un alphabet +$\Sigma$ fixé) une grammaire hors contexte $G$ vérifie $L(G) \neq +\Sigma^*$, est semi-décidable. Autrement dit, montrer qu'il existe un +algorithme qui prend en entrée une grammaire hors contexte $G$, +termine en temps fini et renvoie « vrai » si $L(G) \neq \Sigma^*$, et +ne termine pas si $L(G) = \Sigma^*$. + +\textit{Indication.}\quad On pourra pour cela énumérer tous les mots +possibles à la recherche d'un mot qui \emph{n'appartient pas} +à $L(G)$, et utiliser le fait que tester si $w \in L(G)$ est +décidable. + +\begin{corrige} +L'algorithme suivant convient : énumérer tous les mots $w \in +\Sigma^*$ et, pour chacun, utiliser la procédure de décision connue +pour déterminer en temps fini si $w \in L(G)$. Si ce n'est pas le +cas, on termine immédiatement en renvoyant « vrai » (on a $L(G) \neq +\Sigma^*$) ; si c'est le cas, on continue (on passe au mot suivant). +Cet algorithme termine (et renvoie « vrai » dans ce cas) exactement +lorsque $L(G) \neq \Sigma^*$ : il montre donc la semi-décidabilité du +problème considéré. +\end{corrige} + +\medbreak + +\textbf{(C)} (1) Montrer qu'il existe un algorithme qui, donnés une +expression rationnelle $r_1$ et une grammaire hors contexte $G_1$ (sur +un même alphabet $\Sigma$), calcule (= renvoie) une grammaire hors +contexte $G_2$ telle que $L(G_2) = L(G_1) \cup (\Sigma^* \setminus +L(r_1))$. + +\begin{corrige} +D'après divers résultats du cours : donnée une expression rationnelle +$r_1$, on sait calculer algorithmiquement un NFA $A_1$ tel que $L(r_1) += L(A_1)$ (par exemple avec la construction de Glushkov), on sait +calculer algorithmiquement un DFA $A_2$ tel que $L(A_1) = L(A_2)$ (en +déterminisant $A_1$), on sait calculer algorithmiquement un DFA $A_2$ +tel que $L(A_3) = \Sigma^* \setminus L(A_2)$ (en échangeant états +finaux et non-finaux), on sait calculer algorithmiquement une +grammaire hors contexte $G_3$ telle que $L(G_3) = L(A_3)$ (en +construisant une grammaire régulière), et à partir de $G_1$ et $G_3$ +on sait calculer algorithmiquement une grammaire hors contexte $G_2$ +telle que $L(G_2) = L(G_1) \cup L(G_3)$ (stabilité algorithmique des +langages algébriques par union) : on a alors $L(G_2) = L(G_1) \cup +(\Sigma^* \setminus L(r_1))$ comme annoncé. +\end{corrige} + +(2) On \underline{admet} que le problème suivant n'est pas décidable +(pour un alphabet $\Sigma$ fixé de cardinal $\#\Sigma \geq 2$) : +donnés $G$ une grammaire hors contexte et $r$ une expression +rationnelle, savoir si $L(r) \subseteq L(G)$. En déduire que le +problème suivant (qui en est un cas particulier) n'est lui-même pas +décidable : donnée $G$ une grammaire hors contexte, savoir si $L(G) = +\Sigma^*$. + +\textit{Indication.}\quad Pour cela, on pourra supposer par l'absurde +que le problème de reconnaître si $L(G) = \Sigma^*$ est décidable et, +donnés $G_1$ et $r_1$, construire algorithmiquement une grammaire hors +contexte $G_2$ telle que $L(G_2) = \Sigma^*$ si et seulement si +$L(r_1) \subseteq L(G_1)$. + +\begin{corrige} +Supposons par l'absurde qu'on dispose d'un algorithme $\mathfrak{A}$ +qui prend une grammaire hors contexte $G$ en entrée et décide si $L(G) += \Sigma^*$. Considérons l'algorithme suivant qui prend en entrée une +grammaire hors contexte $G_1$ et une expression rationnelle $r_1$ : on +commence par calculer une grammaire $G_2$ telle que $L(G_2) = L(G_1) +\cup (\Sigma^* \setminus L(r_1))$ comme expliqué en question (1), et +on applique à $G_2$ l'algorithme $\mathfrak{A}$ qu'on a supposé +exister pour décider si $L(G_2) = \Sigma^*$. Comme $L(G_2) = L(G_1) +\cup (\Sigma^* \setminus L(r_1))$, dont le complémentaire est $L(r_1) +\setminus L(G_1)$, on a $L(G_2) = \Sigma^*$ si et seulement si $L(r_1) +\subseteq L(G_1)$ : on peut donc renvoyer « vrai » dans ce cas et +« faux » sinon. Ceci montre l'existence d'un algorithme décidant si +$L(r_1) \subseteq L(G_1)$, ce qui est impossible (résultat admis). +C'est donc que l'hypothèse de l'existence de $\mathfrak{A}$ était +absurde, et le problème en question n'est pas décidable. +\end{corrige} + + +% +% +% +\end{document} |