diff options
Diffstat (limited to 'rattrapage-20230621.tex')
| -rw-r--r-- | rattrapage-20230621.tex | 575 |
1 files changed, 575 insertions, 0 deletions
diff --git a/rattrapage-20230621.tex b/rattrapage-20230621.tex new file mode 100644 index 0000000..27d0168 --- /dev/null +++ b/rattrapage-20230621.tex @@ -0,0 +1,575 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\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 (rattrapage) — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de connaissances (rattrapage)\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{21 juin 2023} +\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. + +\medbreak + +Documents autorisés : uniquement une feuille A4 recto-verso +(manuscrite ou typographiée). + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 1h30 + +\ifcorrige +Ce corrigé comporte 6 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 + +% NOTE: Initially copied from controle-20180322.tex + +Dans cet exercice, on pose $\Sigma = \{a,b,c\}$. On appelle $L$ le +langage des mots sur $\Sigma$ qui ont $abc$ comme sous-mot, +c'est-à-dire, qui contiennent un $a$, un $b$ et un $c$ dans cet ordre +mais non nécessairement consécutivement (à titre d'exemple, $abac \in +L$). + +\textbf{(1)} Proposer un automate non-déterministe (NFA), sans +transition spontanée, $\mathscr{A}_1$ qui reconnaît le langage $L$. +On justifiera rapidement pourquoi l'automate proposé convient. + +\begin{corrige} +On peut proposer l'automate $\mathscr{A}_1$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3$}; +\draw [->] (q0) to[loop below] node[auto] {$a,b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,b,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b,c$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +Pour se convaincre qu'il convient, on remarque qu'un chemin de +l'unique état initial ($0$) à l'unique état final ($3$) dans cet +automate est formé par trois transitions $0\to 1$, $1\to 2$ et $2\to +3$, étiquetées par les lettres $a$, $b$ et $c$ respectivement, +intercalées d'un nombre quelconque de transitions d'un état vers +lui-même, étiquetées par une lettre quelconque : la lecture de ses +étiquettes donne bien un mot ayant $abc$ comme sous-mot ; et +réciproquement, tout tel mot étiquette un chemin de $0$ à $3$ (une +fois choisies les lettres $a,b,c$ dans l'ordre qui correspondront aux +transitions changeant d'état). + +\emph{Remarque :} il est correct de donner directement l'automate +déterministe $\mathscr{A}_2$ représenté ci-dessous (puisque tout DFA +est, en particulier, un NFA), à condition de justifier proprement +qu'il convient. +\end{corrige} + +\textbf{(2)} Déterminiser (si nécessaire) l'automate $\mathscr{A}_1$ +trouvé en (1) ; on appellera $\mathscr{A}_2$ l'automate résultant. + +\begin{corrige} +En notant $0':=\{0\}$, $1' := \{0,1\}$, $2' := \{0,1,2\}$ et $3' := +\{0,1,2,3\}$ les états de l'automate déterministe $\mathscr{A}_2$ qui +correspondent aux ensembles d'états de l'automate $\mathscr{A}_1$ +qu'on vient d'indiquer, la déterminisation conduit à l'automate +$\mathscr{A}_2$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$}; +\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3'$}; +\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +\textbf{(3)} Minimiser (si nécessaire) l'automate $\mathscr{A}_2$ +obtenu en (2) ; on appellera $\mathscr{A}_3$ l'automate minimal +(=canonique) résultant. + +\begin{corrige} +On part bien d'un automate $\mathscr{A}_2$ déterministe complet sans +état inaccessible. La première étape de l'algorithme de minimisation +sépare deux classes d'états : $0',1',2'$ (non finaux) d'une part et +$3'$ (final) de l'autre. Ensuite on sépare $0',1'$ d'une part et $2'$ +de l'autre (car les premiers ne conduisent qu'à des états non finaux, +tandis que $2'$ conduit à un état final par la transition +étiquetée $c$). L'étape suivante sépare $0'$ et $1'$ (car le premier +ne conduit qu'à un état de la classe $\{0',1'\}$ de l'étape +précédente, tandis que $1'$ conduit à un état de la classe $\{2'\}$ +par la transition étiquetée $b$). On a donc séparé tous les états, ce +qui montre que $\mathscr{A}_3 = \mathscr{A}_2$ est minimal. + +\emph{Remarque :} on pouvait aussi invoquer l'argument suivant : +puisque le mot $abc$ doit être accepté et qu'aucun de ses sous-mots +stricts ne l'est (ce qui exclut qu'il y ait une boucle dans le chemin +d'acceptation), il faut au moins $|abc|+1 = 4$ états dans n'importe +quel automate reconnaissant $L$. Comme $\mathscr{A}_2$ a +effectivement $4$ états, il est forcément minimal. +\end{corrige} + +\textbf{(4)} Construire un automate $\mathscr{A}_4$ reconnaissant le +langage $M := \Sigma^*\setminus L$ complémentaire de $L$. + +\begin{corrige} +On obtient $\mathscr{A}_4$ en échangeant états finaux et non finaux +dans $\mathscr{A}_3 = \mathscr{A}_2$, c'est-à-dire l'automate +$\mathscr{A}_4$ 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 (70bp,0bp) [draw,circle,state,final,accepting above] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state,final,accepting above] {$2'$}; +\node (q3) at (210bp,0bp) [draw,circle,state] {$3'$}; +\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +\textbf{(5)} En appliquant à $\mathscr{A}_4$ la méthode d'élimination +des états, déterminer une expression rationnelle dénotant le +langage $M$. (Si on souhaite obtenir une expression plus compacte, il +est recommandé de commencer l'élimination des états par ceux qui sont +le plus loin de l'état initial.) + +\begin{corrige} +On va manipuler des automates finis à transitions étiquetées par des +expressions rationnelles (ou « RNFA »). Dans un premier temps, on +donne à l'automate un unique état final $F$ en faisant pointer vers +lui une transition spontanée (i.e., étiquetée +par $\underline{\varepsilon}$) depuis tout état qui était final, et un +unique état initial $I$ depuis lequel on fait partir une transition +spontanée vers $0'$. L'état $3'$ peut être éliminé d'emblée puisqu'il +est inutile (il n'est pas co-accessible : c'est un puits !). Par +ailleurs, deux transitions entre les mêmes états sont remplacées par +une seule étiquetée par la disjonction des étiquettes (par exemple, +les deux transitions $0'\to 0'$ étiquetées $b$ et $c$ sont remplacées +par une seule étiquetée $b|c$). On a donc affaire à l'automate +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a|b$} (q2); +\draw [->] (q2) -- node[auto] {$\underline{\varepsilon}$} (qF); +\draw [->] (q1) to[out=45,in=135] node[auto] {$\underline{\varepsilon}$} (qF); +\draw [->] (q0) to[out=90,in=180] (70bp,60bp) to node[auto] {$\underline{\varepsilon}$} (140bp,60bp) to[out=0,in=90] (qF); +\end{tikzpicture} +\end{center} +On élimine maintenant l'état $2'$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1); +\draw [->] (q1) -- node[auto] {$\underline{\varepsilon}|b(a|b){*}$} (qF); +\draw [->] (q0) to[out=90,in=180] (70bp,40bp) to node[auto] {$\underline{\varepsilon}$} (140bp,40bp) to[out=0,in=90] (qF); +\end{tikzpicture} +\end{center} +(on a fait usage du fait évident que l'expression rationnelle +$r\underline{\varepsilon}$ est équivalente à $r$). On élimine +ensuite l'état $1'$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$\underline{\varepsilon}|a(a|c){*}(\underline{\varepsilon}|b(a|b){*})$} (qF); +\end{tikzpicture} +\end{center} +Enfin, l'élimination de l'état $0'$ conduit au RNFA ayant seulement +deux états $I$ et $F$ reliés par une transition étiquetée par +\[ +(b|c){*}\Big(\underline{\varepsilon}|a(a|c){*}\big(\underline{\varepsilon}|b(a|b){*}\big)\Big) +\] +qui est l'expression rationnelle recherchée (dénotant $M$). + +L'élimination des états dans l'ordre $0',1',2'$ conduirait à +l'expression rationnelle moins compacte +\[ +\underline{\varepsilon}\;|\;(b|c){*}\;|\;(b|c){*}a(a|c){*}\;|\;(b|c){*}a(a|c){*}b(a|b){*} +\] +qui est cependant sans doute plus lisible. + +\emph{Remarque :} le langage $M$ est aussi dénoté par l'expression +rationnelle plus simple $(b|c){*}\,(a|c){*}\,(a|b){*}$, mais celle-ci +ne répond pas à la question car elle ne peut pas s'obtenir par +élimination des états à partir de $\mathscr{A}_4$. +\end{corrige} + + +% +% +% + +\exercice + +% NOTE: Initially copied from controle-20180322.tex + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On appelle $L = L(G)$ +le langage défini par la grammaire hors-contexte $G$ d'axiome $S$ et de +nonterminaux $N = \{S\}$ sur l'alphabet $\Sigma$ donnée par +\[ +\begin{aligned} +S &\rightarrow aSbS \;|\; aS \;|\; \varepsilon\\ +\end{aligned} +\] + +Les questions de cet exercice sont essentiellement indépendantes, si +ce n'est que la question (6) fait appel à la conclusion (énoncée) des +questions (2) à (5). + +\smallskip + +\textbf{(1)} Donner deux arbres d'analyse (pour $G$) différents du +mot $aab$. Que peut-on dire de la grammaire $G$ ? + +\begin{corrige} +On peut proposer les arbres d'analyse suivants :\\ +% S<a.S<a.S<e.>>b.S<e.>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (42.500bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S1) at (30.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a1); +\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S2) -- (e0); +\node (b0) at (60.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (S3) at (80.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S3); +\node (e1) at (80.000bp,-50.000bp) [draw=none] {$\varepsilon$}; \draw (S3) -- (e1); +\end{tikzpicture} +d'une part,\hfill et +% S<a.S<a.S<e.>b.S<e.>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (25.000bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S1) at (50.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a1); +\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S2) -- (e0); +\node (b0) at (60.000bp,-60.000bp) [draw=none] {$b$}; \draw (S1) -- (b0); +\node (S3) at (80.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S3); +\node (e1) at (80.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S3) -- (e1); +\end{tikzpicture} +d'autre part\\ +(en fait, on peut se convaincre que ce sont les seuls possibles). +La grammaire $G$ est donc ambiguë. +\end{corrige} + +L'objet des questions suivantes est de montrer que $L$ n'est pas +rationnel. + +Soit $M$ le langage $\{a^i b^j : i,j\in\mathbb{N}\}$ constitué des +mots de la forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels +quelconques. + +\textbf{(2)} Donner une expression rationnelle qui dénote $M$. + +\begin{corrige} +Le langage $M$ est dénoté par l'expression rationnelle $a{*}b{*}$. +\end{corrige} + +Soit $P$ le langage $\{a^i b^j : i\geq j\}$ constitué des mots de la +forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels vérifiant $i\geq +j$ (autrement dit, les mots de $M$ qui ont au moins autant de $a$ que +de $b$). + +\textbf{(3)} Montrer que $P \subseteq L$. + +\begin{corrige} +Soient $i\geq j$ deux entiers naturels : on va expliquer comment +produire le mot $a^i b^j$ selon les règles de $G$. À partir de +l'axiome $S$, on commence par appliquer $i-j$ fois la règle $a +\rightarrow aS$, ce qui donne $a \Rightarrow aS \Rightarrow aaS +\Rightarrow \cdots \Rightarrow a^{i-j} S$. Appliquons maintenant $j$ +fois la règle $S\rightarrow aSbS$, suivie à chaque fois de +$S\rightarrow\varepsilon$ sur le $S$ de droite : on obtient ainsi +$a^{i-j} S \Rightarrow a^{i-j+1} S bS \Rightarrow a^{i-j+1} S b +\Rightarrow a^{i-j+2} S b S b \Rightarrow a^{i-j+2} S bb \Rightarrow +\cdots \Rightarrow a^i S b^j$. Il suffit de terminer par une +application de $S \rightarrow \varepsilon$ : on obtient ainsi une +dérivation $S \mathrel{\Rightarrow^*} a^i b^j$ qui prouve que $a^i b^j +\in L$. + +(On pouvait aussi, plus informellement, esquisser l'allure d'un arbre +de dérivation de $a^i b^j$ un peu à la manière de l'un ou l'autre de +ceux de la question (1), mais en appliquant $i-j$ fois la règle $a +\rightarrow aS$ et $j$ fois la règle $S \rightarrow aSbS$.) +\end{corrige} + +\textbf{(4)} Montrer que $L\cap M \subseteq P$. + +\begin{corrige} +Considérons la propriété « avoir (au total) au moins autant de $a$ que +de $b$ », ou si on veut $|\xi|_a\geq |\xi|_b$, sur un pseudo-mot $\xi$ +(un « pseudo-mot » signifiant, par définition, un mot sur $\Sigma\cup +N = \{a,b,S\}$). Cette propriété est vérifiée par le pseudo-mot $S$. +Elle est préservée si on remplace $S$ par $aSbS$ ou $aS$ ou +$\varepsilon$ puisque dans chacun de ces cas le nombre de $a$ augmente +d'au moins autant que le nombre de $b$. Elle est donc possédée par +tout pseudo-mot, et en particulier tout mot, qui dérive de $S$ +selon $G$. On vient donc de prouver que tout mot de $L$ a au moins +autant de $a$ que de $b$. Notamment, tout mot de $L\cap M$ est un mot +de la forme $a^i b^j$ (par définition de $M$), et qui vérifie $i\geq +j$ (c'est ce qu'on vient de prouver). Il est donc dans $P$. +\end{corrige} + +\textbf{(5)} Montrer que $P$ n'est pas rationnel. + +\begin{corrige} +Supposons par l'absurde que $P = \{a^i b^j : i\geq j\}$ soit +rationnel. Appliquons le lemme de pompage pour les langages +rationnels au langage $P$ : appelons $k$ l'entier dont le lemme de +pompage garantit l'existence. Considérons le mot $t := a^k b^k$ (qui +appartient bien à $P$ et est bien de longueur $\geq k$) : il doit +alors exister une factorisation $t = uvw$ (avec $u,v,w \in \Sigma^*$, +non nécessairement dans $P$) pour laquelle on a +(i) $|v|\geq 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in P$ pour +tout $i\geq 0$. La propriété (ii) assure que $uv$ est formé d'un +certain nombre de répétitions de la lettre $a$ (car tout préfixe de +longueur $\leq k$ de $a^k b^k$ est de cette forme) ; disons $u = +a^\ell$ et $v = a^m$, si bien que $w = a^{k-\ell-m} b^k$. La +propriété (i) donne $m\geq 1$. Enfin, la propriété (iii) affirme que +le mot $uv^iw = a^{k+(i-1)m} b^k$ appartient à $P$ ; or pour $i=0$, +ceci est faux puisque $a^{k-m} b^k$ vérifie $k-m < k$. On a donc +abouti à une contradiction, et c'est que $P$ n'est pas rationnel. +\end{corrige} + +\textbf{(6)} Déduire des questions (2) à (5) que $L$ n'est pas +rationnel (on explicitera très soigneusement le raisonnement). + +\begin{corrige} +On a vu à la question (3) que $P \subseteq L$ ; il est par ailleurs +trivial que $P \subseteq M$, et on a donc $P \subseteq L\cap M$. Mais +on a vu à la question (4) que $L\cap M \subseteq P$ : on a donc $L\cap +M = P$. Le langage $M$ est rationnel d'après la question (2). Si le +langage $L$ était lui aussi rationnel, le langage $L\cap M$ +(c'est-à-dire $P$) le serait car l'intersection de deux langages +rationnels est rationnelle. Or on a vu à la question (5) que $P$ +n'est pas rationnel. C'est donc que $L$ ne l'est pas. +\end{corrige} + + +% +% +% + +\exercice + +% NOTE: Initially copied from controle-20210618.tex + +(Les deux questions suivantes sont indépendantes.) + +\smallskip + +\textbf{(1)} Le langage $\{a^n b^n c^n : n\in\mathbb{N}\}$ n'est pas +algébrique\footnote{Ce fait est démontré dans le poly, dans la section + consacrée au lemme de pompage pour les langages algébriques et comme + illustration de ce dernier ; on ne demande pas ici de le + redémontrer : on peut le tenir pour admis.}. Est-il rationnel ? +Est-il décidable ? Est-il semi-décidable ? On justifiera +soigneusement les réponses. + +\begin{corrige} +Le langage proposé n'est pas rationnel car il n'est pas algébrique. + +Il est décidable car il est évident qu'on peut algorithmiquement d'une +part vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci +correspond à l'expression rationnelle $a{*}b{*}c{*}$, c'est faisable +par automate fini) et d'autre part vérifier qu'il a autant de $a$ que +de $b$ que de $c$. + +Étant décidable, il est notamment semi-décidable. +\end{corrige} + +\smallskip + +\textbf{(2)} On rappelle la définition du problème de l'arrêt : c'est +l'ensemble $H$ des couples\footnote{Pour être rigoureux, on a fixé un + codage permettant de représenter les programmes $e$, les entrées $x$ + à ces programmes, et les couples $(e,x)$, comme des éléments + de $\mathbb{N}$ (ou bien de $\Sigma^*$ sur un alphabet + $\Sigma\neq\varnothing$ arbitraire). Il n'est pas nécessaire de + faire apparaître ce codage dans la description des algorithmes + proposés, qui peut rester informelle.} $(e,x)$ formés d'un programme +(= algorithme) $e$ et d'une entrée $x$, tels que l'exécution du +programme $e$ sur l'entrée $x$ termine en temps fini. On a vu en +cours que $H$ était semi-décidable mais non décidable. + +On considère l'ensemble $J$ des triplets $(e_1,e_2,x)$ tels que +$(e_1,x) \in H$ et $(e_2,x) \not\in H$. Autrement dit, le programme +$e_1$ termine en temps fini quand on l'exécute sur l'entrée $x$ mais +le programme $e_2$, lui, ne termine pas sur cette même entrée. +L'ensemble $J$ est-il décidable ? Semi-décidable ? On justifiera +soigneusement. + +\begin{corrige} +L'ensemble $J$ n'est pas semi-décidable. + +Pour le montrer, supposons par l'absurde qu'on dispose d'un algorithme +$T$ qui semi-décide $J$ (où « semi-décider » un ensemble $Z$ +signifie : terminer en renvoyant $1$ (=vrai) si l'entrée $z$ fournie +appartient à $Z$, et ne pas terminer sinon). Fixons une fois pour +toutes (le code d')un programme $f$ qui, donnée une entrée $x$, +termine immédiatement (en ignorant $x$). Alors trivialement $(f,x) +\in H$ quel que soit $x$ ; donc, par définition de $J$, on a $(f,e,x) +\in J$ si et seulement si $(e,h) \not \in H$. + +On considère alors l'algorithme $T'$, défini de la manière suivante : +donnés $(e,x)$, on applique l'algorithme $T$ (qu'on a supposé exister) +au triplet $(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in +J$), on renvoie $1$ (sinon, bien sûr, on ne termine jamais). Par +construction, $T'$ termine en renvoyant $1$ sur l'entrée $(e,x)$ si +$(f,e,x) \in J$, c'est-à-dire $(e,x) \not\in H$, et sinon il ne +termine pas. Ceci signifie que $T'$ semi-décide le complémentaire +de $H$. + +Or le complémentaire de $H$ n'est pas semi-décidable (car si le +complémentaire de $H$ était semi-décidable, on aurait à la fois $H$ et +son complémentaire semi-décidables, donc $H$ serait décidable, et on +sait qu'il ne l'est pas), donc un tel algorithme $T'$ ne peut pas +exister. C'est une contradiction : $J$ n'est donc pas semi-décidable. + +\textit{A fortiori}, $J$ n'est pas décidable. +\end{corrige} + + +% +% +% +\end{document} |