diff options
| -rw-r--r-- | controle-20220825.tex | 683 |
1 files changed, 683 insertions, 0 deletions
diff --git a/controle-20220825.tex b/controle-20220825.tex new file mode 100644 index 0000000..c3cf461 --- /dev/null +++ b/controle-20220825.tex @@ -0,0 +1,683 @@ +%% 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 rattrapage — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de rattrapage\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{25 août 2022} +\maketitle + +% NOTE: Initially copied from controle-20180206.tex + +\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 + +Barème \emph{indicatif} : 7 points par 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 s'intéresse au +langage $L$ formé des mots (éléments de $\Sigma^*$) ayant $aa$ ou $bb$ +comme facteur (c'est-à-dire contenant deux $a$ consécutifs, ou bien +deux $b$ consécutifs), ainsi qu'à son +complémentaire $M := \Sigma^* \setminus L$. + +(1) Donner une expression rationnelle dénotant $L$. + +\begin{corrige} +Le langage des mots contenant deux $a$ consécutifs est dénoté par +l'expression rationnelle $(a|b){*}\,aa\,(a|b){*}$, et celui des mots +contenant deux $b$ consécutifs par $(a|b){*}\,bb\,(a|b){*}$. On peut +donc proposer l'expression rationnelle $(a|b){*}\,aa\,(a|b){*} \; | \; +(a|b){*}\,bb\,(a|b){*}$ ou encore, si on préfère, +$(a|b){*}\,(aa|bb)\,(a|b){*}$. +\end{corrige} + +(2) \emph{Indépendamment} de la question (1), expliquer brièvement pourquoi +l'automate $\mathscr{A}_2$ suivant reconnaît le langage $L$ : + +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (A) at (70bp,35bp) [draw,circle,state] {$A$}; +\node (B) at (70bp,-35bp) [draw,circle,state] {$B$}; +\node (T) at (140bp,0bp) [draw,circle,state,final] {$T$}; +\draw [->] (S) to[loop above] node[auto] {$a,b$} (S); +\draw [->] (S) -- node[auto,near end] {$a$} (A); +\draw [->] (S) -- node[auto] {$b$} (B); +\draw [->] (T) to[loop above] node[auto] {$a,b$} (T); +\draw [->] (A) -- node[auto,near start] {$a$} (T); +\draw [->] (B) -- node[auto] {$b$} (T); +\end{tikzpicture} +\end{center} + +De quelle sorte d'automate s'agit-il ? (DFA ? NFA ?...) + +\begin{corrige} +Un chemin de l'unique état initial $S$ à l'unique état final $T$ de +$\mathscr{A}_2$ doit passer soit par l'état $A$ soit par l'état $B$, +donc la lecture de ses étiquettes contient le facteur $aa$ +(correspondant aux transitions $S\to A$ et $A\to T$) ou $bb$ ; et +réciproquement, un mot contenant le facteur $aa$ ou $bb$ peut se lire +en suivant un chemin de $S$ à $T$ dans l'automate (en plaçant le +facteur $aa$ au niveau des transitions $S\to A$ et $A\to T$ ou de +façon analogue pour $bb$). + +Il s'agit là d'un automate non déterministe (l'état $S$ a plusieurs +transitions sortantes étiquetées par $a$), mais sans transitions +spontanées ou en abrégé, NFA. +\end{corrige} + +(3) Déterminiser (si nécessaire) l'automate $\mathscr{A}_2$ représenté +en (2) ; on appellera $\mathscr{A}_3$ l'automate résultant. + +\begin{corrige} +En notant $S$, $SA$, $SB$, $SAT$ et $SBT$ les états de l'automate +déterministe $\mathscr{A}_3$ qui correspondent aux ensembles d'états +de l'automate $\mathscr{A}_2$ donnés par les lettres en question, la +déterminisation conduit à l'automate $\mathscr{A}_3$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$}; +\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$}; +\node (SAT) at (140bp,35bp) [draw,circle,state,final] {$SAT$}; +\node (SBT) at (140bp,-35bp) [draw,circle,state,final] {$SBT$}; +\draw [->] (S) -- node[auto,near end] {$a$} (SA); +\draw [->] (S) -- node[auto,below] {$b$} (SB); +\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB); +\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA); +\draw [->] (SA) -- node[auto] {$a$} (SAT); +\draw [->] (SB) -- node[auto,below] {$b$} (SBT); +\draw [->] (SAT) to[out=300,in=60] node[auto] {$b$} (SBT); +\draw [->] (SBT) to[out=120,in=240] node[auto] {$a$} (SAT); +\draw [->] (SAT) to[loop above] node[auto] {$a$} (SAT); +\draw [->] (SBT) to[loop below] node[auto] {$b$} (SBT); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(4) Minimiser (si nécessaire) l'automate $\mathscr{A}_3$ obtenu +en (3) ; on appellera $\mathscr{A}_4$ l'automate minimal (=canonique) +résultant. + +\begin{corrige} +On part bien d'un automate $\mathscr{A}_3$ déterministe complet sans +état inaccessible. La première étape de l'algorithme de minimisation +sépare deux classes d'états : $S,SA,SB$ (non finaux) d'une part et +$SAT,SBT$ de l'autre. Ensuite on sépare $S$ et $SA$ et $SB$ (car le +premier ne conduit qu'à des états non finaux, le deuxième conduit à un +état final par la transition étiquetée $a$, et le troisième conduit à +un état final par la transition étiquetée $b$). Les étapes suivantes +ne conduisent pas à d'autres séparations d'états. On obtient +finalement un automate $\mathscr{A}_4$ à quatre états, qu'on peut +appeler $S,SA,SB,U$ où $U$ est la classe de $SAT$ et $SBT$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$}; +\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$}; +\node (U) at (140bp,0bp) [draw,circle,state,final] {$U$}; +\draw [->] (S) -- node[auto,near end] {$a$} (SA); +\draw [->] (S) -- node[auto,below] {$b$} (SB); +\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB); +\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA); +\draw [->] (SA) -- node[auto] {$a$} (U); +\draw [->] (SB) -- node[auto,below] {$b$} (U); +\draw [->] (U) to[loop above] node[auto] {$a,b$} (U); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(5) Construire un automate $\mathscr{A}_5$ reconnaissant le +langage $M$ complémentaire de $L$. + +\begin{corrige} +On obtient $\mathscr{A}_5$ en échangeant états finaux et non finaux +dans $\mathscr{A}_4$, c'est-à-dire l'automate $\mathscr{A}_5$ +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$S$}; +\node (SA) at (70bp,35bp) [draw,circle,state,final] {$SA$}; +\node (SB) at (70bp,-35bp) [draw,circle,state,final] {$SB$}; +\node (U) at (140bp,0bp) [draw,circle,state] {$U$}; +\draw [->] (S) -- node[auto,near end] {$a$} (SA); +\draw [->] (S) -- node[auto,below] {$b$} (SB); +\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB); +\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA); +\draw [->] (SA) -- node[auto] {$a$} (U); +\draw [->] (SB) -- node[auto,below,near end] {$b$} (U); +\draw [->] (U) to[loop above] node[auto] {$a,b$} (U); +\end{tikzpicture} +\end{center} +(L'état $U$ est maintenant un puits.) +\end{corrige} + +(6) En appliquant à $\mathscr{A}_5$ la méthode d'élimination des +états, déterminer une expression rationnelle dénotant le langage $M$. + +\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. +L'état $U$ peut être éliminé d'emblée puisqu'il est inutile (il n'est +pas co-accessible : c'est un puits !). On a donc affaire à l'automate +suivant +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$}; +\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$}; +\node (F) at (140bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (S) -- node[auto,near end] {$a$} (SA); +\draw [->] (S) -- node[auto,below] {$b$} (SB); +\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB); +\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA); +\draw [->] (SA) -- node[auto] {$\underline{\varepsilon}$} (F); +\draw [->] (SB) -- node[auto,below,near end] {$\underline{\varepsilon}$} (F); +\draw [->] (S) to[out=270,in=90] (0,-30bp) to[out=270,in=270] node[auto,below] {$\underline{\varepsilon}$} (140bp,-30bp) to[in=270,out=90] (F); +\end{tikzpicture} +\end{center} +On élimine maintenant l'état $SB$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$}; +\node (F) at (140bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (S) -- node[auto,near end] {$a|ba$} (SA); +\draw [->] (SA) -- node[auto] {$\underline{\varepsilon}|b$} (F); +\draw [->] (S) to[out=270,in=270] node[auto,below] {$\underline{\varepsilon}|b$} (F); +\draw [->] (SA) to[loop below] node[auto] {$ba$} (SA); +\end{tikzpicture} +\end{center} +Et l'élimination de l'état $SA$ conduit à l'expression rationnelle +$\underline{\varepsilon}\,|\,b\,|\penalty0\,(a|ba)(ba){*}(\underline{\varepsilon}|b)$ +(il y a bien sûr toutes sortes d'autres expressions rationnelles +équivalentes : par exemple, on peut la réécrire comme +$\underline{\varepsilon}\,|\,b\,|\penalty0\,(\varepsilon|b)a(ba){*}(\underline{\varepsilon}|b)$ +ou encore comme +$(\varepsilon|b)(\underline{\varepsilon}|a(ba){*}(\underline{\varepsilon}|b))$ ; +si on avait éliminé l'état $SA$ en premier, on serait plutôt tombé sur +$\underline{\varepsilon}\,|\,a\,|\penalty0\,(b|ab)(ab){*}(\underline{\varepsilon}|a)$, +et ainsi de suite). +\end{corrige} + + + +% +% +% + +\exercice + +On considère la grammaire hors-contexte $G$ d'axiome $S$ et de +nonterminaux $N = \{S, T, U, V\}$ sur l'alphabet $\Sigma = +\{{\#},{@},{(},{)}, x, y, z\}$ (soit $7$ lettres) donnée par +\[ +\begin{aligned} +S &\rightarrow T \;|\; S\mathbin{\#}T\\ +T &\rightarrow U \;|\; U\mathbin{@}T\\ +U &\rightarrow V \;|\; (\,S\,)\\ +V &\rightarrow x \;|\; y \;|\; z\\ +\end{aligned} +\] +(On pourra imaginer que $\#$ et $@$ sont deux opérations binaires, les +parenthèses servent comme on s'y attend, et $x,y,z$ sont trois opérandes +auxquelles on peut vouloir appliquer ces opérations.) + +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 : +(a) $x\mathbin{\#}y\mathbin{\#}z$, (b) $x\mathbin{\#}y\mathbin{@}z$, +(c) $x\mathbin{@}y\mathbin{\#}z$, (d) $x\mathbin{@}y\mathbin{@}z$, +(e) $(x\mathbin{\#}y)\mathbin{@}z$. + +\begin{corrige} +On obtient les arbres d'analyse suivants : +(a) % S<S<S<T<U<V<x.>>>>#.T<U<V<y.>>>>#.T<U<V<z.>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (53.333bp,0.000bp) [draw=none] {$S$}; +\node (S1) at (20.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (S2) at (0.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (T0) at (0.000bp,-80.000bp) [draw=none] {$T$}; \draw (S2) -- (T0); +\node (U0) at (0.000bp,-100.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (V0) at (0.000bp,-120.000bp) [draw=none] {$V$}; \draw (U0) -- (V0); +\node (x0) at (0.000bp,-140.000bp) [draw=none] {$x$}; \draw (V0) -- (x0); +\node (o0) at (20.000bp,-60.000bp) [draw=none] {$\#$}; \draw (S1) -- (o0); +\node (T1) at (40.000bp,-60.000bp) [draw=none] {$T$}; \draw (S1) -- (T1); +\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (V1) at (40.000bp,-100.000bp) [draw=none] {$V$}; \draw (U1) -- (V1); +\node (y0) at (40.000bp,-120.000bp) [draw=none] {$y$}; \draw (V1) -- (y0); +\node (o1) at (60.000bp,-30.000bp) [draw=none] {$\#$}; \draw (S0) -- (o1); +\node (T2) at (80.000bp,-30.000bp) [draw=none] {$T$}; \draw (S0) -- (T2); +\node (U2) at (80.000bp,-50.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (V2) at (80.000bp,-70.000bp) [draw=none] {$V$}; \draw (U2) -- (V2); +\node (z0) at (80.000bp,-90.000bp) [draw=none] {$z$}; \draw (V2) -- (z0); +\end{tikzpicture} +\hskip1cmplus5cmminus.5cm +(b) % S<S<T<U<V<x.>>>>#.T<U<V<y.>>@.T<U<V<z.>>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (26.667bp,0.000bp) [draw=none] {$S$}; +\node (S1) at (0.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (T0) at (0.000bp,-50.000bp) [draw=none] {$T$}; \draw (S1) -- (T0); +\node (U0) at (0.000bp,-70.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (V0) at (0.000bp,-90.000bp) [draw=none] {$V$}; \draw (U0) -- (V0); +\node (x0) at (0.000bp,-110.000bp) [draw=none] {$x$}; \draw (V0) -- (x0); +\node (o0) at (20.000bp,-30.000bp) [draw=none] {$\#$}; \draw (S0) -- (o0); +\node (T1) at (60.000bp,-30.000bp) [draw=none] {$T$}; \draw (S0) -- (T1); +\node (U1) at (40.000bp,-60.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (V1) at (40.000bp,-80.000bp) [draw=none] {$V$}; \draw (U1) -- (V1); +\node (y0) at (40.000bp,-100.000bp) [draw=none] {$y$}; \draw (V1) -- (y0); +\node (o1) at (60.000bp,-60.000bp) [draw=none] {$@$}; \draw (T1) -- (o1); +\node (T2) at (80.000bp,-60.000bp) [draw=none] {$T$}; \draw (T1) -- (T2); +\node (U2) at (80.000bp,-80.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (V2) at (80.000bp,-100.000bp) [draw=none] {$V$}; \draw (U2) -- (V2); +\node (z0) at (80.000bp,-120.000bp) [draw=none] {$z$}; \draw (V2) -- (z0); +\end{tikzpicture} +\hskip1cmplus5cmminus.5cm +(c) % S<S<T<U<V<x.>>@.T<U<V<y.>>>>>#.T<U<V<z.>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (53.333bp,0.000bp) [draw=none] {$S$}; +\node (S1) at (20.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (T0) at (20.000bp,-50.000bp) [draw=none] {$T$}; \draw (S1) -- (T0); +\node (U0) at (0.000bp,-80.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (V0) at (0.000bp,-100.000bp) [draw=none] {$V$}; \draw (U0) -- (V0); +\node (x0) at (0.000bp,-120.000bp) [draw=none] {$x$}; \draw (V0) -- (x0); +\node (o0) at (20.000bp,-80.000bp) [draw=none] {$@$}; \draw (T0) -- (o0); +\node (T1) at (40.000bp,-80.000bp) [draw=none] {$T$}; \draw (T0) -- (T1); +\node (U1) at (40.000bp,-100.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (V1) at (40.000bp,-120.000bp) [draw=none] {$V$}; \draw (U1) -- (V1); +\node (y0) at (40.000bp,-140.000bp) [draw=none] {$y$}; \draw (V1) -- (y0); +\node (o1) at (60.000bp,-30.000bp) [draw=none] {$\#$}; \draw (S0) -- (o1); +\node (T2) at (80.000bp,-30.000bp) [draw=none] {$T$}; \draw (S0) -- (T2); +\node (U2) at (80.000bp,-50.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (V2) at (80.000bp,-70.000bp) [draw=none] {$V$}; \draw (U2) -- (V2); +\node (z0) at (80.000bp,-90.000bp) [draw=none] {$z$}; \draw (V2) -- (z0); +\end{tikzpicture} +\hskip1cmplus5cmminus.5cm +(d) % S<T<U<V<x.>>@.T<U<V<y.>>@.T<U<V<z.>>>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (26.667bp,0.000bp) [draw=none] {$S$}; +\node (T0) at (26.667bp,-20.000bp) [draw=none] {$T$}; \draw (S0) -- (T0); +\node (U0) at (0.000bp,-50.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (V0) at (0.000bp,-70.000bp) [draw=none] {$V$}; \draw (U0) -- (V0); +\node (x0) at (0.000bp,-90.000bp) [draw=none] {$x$}; \draw (V0) -- (x0); +\node (o0) at (20.000bp,-50.000bp) [draw=none] {$@$}; \draw (T0) -- (o0); +\node (T1) at (60.000bp,-50.000bp) [draw=none] {$T$}; \draw (T0) -- (T1); +\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (V1) at (40.000bp,-100.000bp) [draw=none] {$V$}; \draw (U1) -- (V1); +\node (y0) at (40.000bp,-120.000bp) [draw=none] {$y$}; \draw (V1) -- (y0); +\node (o1) at (60.000bp,-80.000bp) [draw=none] {$@$}; \draw (T1) -- (o1); +\node (T2) at (80.000bp,-80.000bp) [draw=none] {$T$}; \draw (T1) -- (T2); +\node (U2) at (80.000bp,-100.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (V2) at (80.000bp,-120.000bp) [draw=none] {$V$}; \draw (U2) -- (V2); +\node (z0) at (80.000bp,-140.000bp) [draw=none] {$z$}; \draw (V2) -- (z0); +\end{tikzpicture} +\hskip1cmplus5cmminus.5cm +(e) % S<T<U<(.S<S<T<U<V<x.>>>>#.T<U<V<y.>>>>).>@.T<U<V<z.>>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (86.667bp,0.000bp) [draw=none] {$S$}; +\node (T0) at (86.667bp,-20.000bp) [draw=none] {$T$}; \draw (S0) -- (T0); +\node (U0) at (40.000bp,-50.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (p0) at (0.000bp,-80.000bp) [draw=none] {$($}; \draw (U0) -- (p0); +\node (S1) at (40.000bp,-80.000bp) [draw=none] {$S$}; \draw (U0) -- (S1); +\node (S2) at (20.000bp,-110.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (T1) at (20.000bp,-130.000bp) [draw=none] {$T$}; \draw (S2) -- (T1); +\node (U1) at (20.000bp,-150.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (V0) at (20.000bp,-170.000bp) [draw=none] {$V$}; \draw (U1) -- (V0); +\node (x0) at (20.000bp,-190.000bp) [draw=none] {$x$}; \draw (V0) -- (x0); +\node (o0) at (40.000bp,-110.000bp) [draw=none] {$\#$}; \draw (S1) -- (o0); +\node (T2) at (60.000bp,-110.000bp) [draw=none] {$T$}; \draw (S1) -- (T2); +\node (U2) at (60.000bp,-130.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (V1) at (60.000bp,-150.000bp) [draw=none] {$V$}; \draw (U2) -- (V1); +\node (y0) at (60.000bp,-170.000bp) [draw=none] {$y$}; \draw (V1) -- (y0); +\node (p1) at (80.000bp,-80.000bp) [draw=none] {$)$}; \draw (U0) -- (p1); +\node (o1) at (100.000bp,-50.000bp) [draw=none] {$@$}; \draw (T0) -- (o1); +\node (T3) at (120.000bp,-50.000bp) [draw=none] {$T$}; \draw (T0) -- (T3); +\node (U3) at (120.000bp,-70.000bp) [draw=none] {$U$}; \draw (T3) -- (U3); +\node (V2) at (120.000bp,-90.000bp) [draw=none] {$V$}; \draw (U3) -- (V2); +\node (z0) at (120.000bp,-110.000bp) [draw=none] {$z$}; \draw (V2) -- (z0); +\end{tikzpicture} +\end{corrige} + +(2) En considérant que $(w)$ a le même effet ou la même valeur +que $w$ : (a) L'une des deux opérations $\#$ et $@$ est-elle +prioritaire\footnote{On dit qu'une opération binaire $\boxtimes$ est + \emph{prioritaire} sur $\boxplus$ lorsque « $u\boxtimes v\boxplus + w$ » se comprend comme « $(u\boxtimes v)\boxplus w$ » (i.e., les + deux ont le même effet ou la même valeur), et « $u\boxplus + v\boxtimes w$ » comme « $u\boxplus (v\boxtimes w)$ ».} sur +l'autre ? Laquelle ?\quad (b) L'opération $\#$ +s'associe-t-elle\footnote{On dit qu'une opération binaire $\boxdot$ + \emph{s'associe à gauche} lorsque « $u\boxdot v\boxdot w$ » se + comprend comme « $(u\boxdot v)\boxdot w$ », et \emph{s'associe à + droite} lorsque « $u\boxdot v\boxdot w$ » se comprend comme + « $u\boxdot (v\boxdot w)$ ».} à gauche ou à droite ?\quad +(c) L'opération $@$ s'associe-t-elle à gauche ou à droite ? + +\begin{corrige} +(a) Les arbres d'analyse (b) et (c) de la question (1) montrent que + l'opération $@$ est prioritaire sur $\#$ (elle est toujours plus + profonde dans l'arbre, c'est-à-dire appliquée en premier aux + opérandes).\quad (b) L'arbre d'analyse (a) de la question (1) montre + que $\#$ s'associe à gauche (le $\#$ entre les deux opérandes gauche + est plus profond, c'est-à-dire appliqué en premier).\quad + (c) Symétriquement, l'arbre d'analyse (d) de la question (1) montre + que $@$ s'associe à droite. +\end{corrige} + +\smallskip + +(La question (3) est indépendante de (1) et (2). Par ailleurs, on +pourra, si on souhaite s'épargner des confusions, choisir de renommer +en $a$ la lettre « parenthèse ouvrante » de $\Sigma$ et en $b$ la +lettre « parenthèse fermante » afin de les distinguer des parenthèses +mathématiques.) + +(3) Soit $L = L(G)$ le langage engendré par $G$. Soit $M$ le langage +des mots sur $\Sigma$ formés d'un certain nombre de parenthèses +ouvrantes, puis de la lettre $x$, puis d'un certain nombre +(possiblement différent) de parenthèses fermantes : autrement dit, des +mots de la forme « ${(}^i\, x\, {)}^j$ », où on a noté « ${(}^i$ » une +succession de $i$ parenthèses ouvrantes et « ${)}^j$ » une succession +de $j$ parenthèses fermantes (on pourra noter ce mot $a^i x b^j$ si on +préfère).\quad (a) Décrire le langage $L\cap M$ (des mots de $L$ qui +appartiennent aussi à $M$).\quad (b) Ce langage $L\cap M$ est-il +rationnel ?\quad (c) Le langage $L$ est-il rationnel ? + +\begin{corrige} +(a) Cherchons pour quelles valeurs $(i,j) \in \mathbb{N}^2$ le mot + « ${(}^i\, x\, {)}^j$ » de $M$ appartient à $L$. La dérivation $S + \Rightarrow T \Rightarrow U \Rightarrow (S) \Rightarrow (T) + \Rightarrow (U) \Rightarrow ((S)) \Rightarrow \cdots + \Rightarrow{(}^i\, S\, {)}^i \Rightarrow{(}^i\, T\, {)}^i + \Rightarrow{(}^i\, U\, {)}^i \Rightarrow{(}^i\, V\, {)}^i + \Rightarrow{(}^i\, x\, {)}^i$ montre que c'est le cas si $j=i$, + autrement dit s'il y a autant de parenthèses fermantes qu'ouvrantes. + Mais réciproquement, la propriété d'avoir autant de parenthèses + fermantes qu'ouvrantes est préservée par toutes les productions + de $G$ (et est satisfaite par l'axiome), donc est vérifiée par tout + mot de $L=L(G)$. On a donc prouvé que le $L\cap M$ est l'ensemble + des mots de la forme « ${(}^i\, x\, {)}^i$ » où $i\in \mathbb{N}$. + +(b) Le langage $L\cap M$ constitué des mots de la forme « ${(}^n\, + x\, {)}^n$ » où $i\in \mathbb{N}$ n'est pas rationnel. Cela résulte + du lemme de pompage (presque exactement comme l'exemple du langage + $\{a^n b^n : i\in\mathbb{N}\}$ donné en cours) : donnons l'argument + en remplaçant la parenthèse ouvrante par $a$ et la parenthèse + fermante par $b$ pour plus de clarté notationnelle. Appliquons le + lemme de pompage pour les langages rationnels au langage $L \cap M = + \{a^n x b^n : i\in\mathbb{N}\}$ supposé par l'absurde être + rationnel : appelons $k$ l'entier dont le lemme de pompage garantit + l'existence. Considérons le mot $t := a^k x b^k$ : il doit alors + exister une factorisation $t = uvw$ pour laquelle on a (i) $|v|\geq + 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in L\cap M$ 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 x b^k$ est de cette forme) ; disons $u = a^\ell$ et $v = + a^m$, si bien que $w = a^{k-\ell-m} x 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} x b^k$ appartient à $L\cap M$ ; mais dès que + $i\neq 1$, ceci est faux : il suffit donc de prendre $i=0$ pour + avoir une contradiction. + +(c) Le langage $M$ est rationnel puisqu'il est dénoté par l'expression + rationnelle $a{*}xb{*}$ (toujours en notant $a$ la parenthèse + ouvrante et $b$ la parenthèse fermante). Si le langage $L$ était + rationnel, le langage $L\cap M$ le serait aussi (on sait que + l'intersection de deux langages rationnels est rationnelle), ce qui + n'est pas le cas d'après la question (b). Le langage $L$ n'est donc + pas rationnel. +\end{corrige} + + +% +% +% + +\exercice + +(On pourra si on le souhaite remplacer $\mathbb{N}$ partout dans cet +exercice par l'ensemble $\Sigma^*$ des mots sur un alphabet $\Sigma$ +[fini] non vide fixé quelconque : grâce au codage de Gödel, ceci ne +change rien au problème ni aux raisonnements.) + +Dans cet exercice, on appelle « langage » une partie de $\mathbb{N}$ +(cf. le paragraphe précédent). + +On dira que deux langages $L,M$ disjoints (c'est-à-dire tels que +$L\cap M = \varnothing$) sont \emph{calculablement séparables} +lorsqu'il existe un langage $E$ \underline{décidable} tel que $L +\subseteq E$ et $M \subseteq (\mathbb{N}\setminus E)$ (où +$\mathbb{N}\setminus E$ désigne le complémentaire de $E$) ; dans le +cas contraire, on dit que $L$ et $M$ sont \emph{calculablement + inséparables}. + +(1) Expliquer pourquoi deux langages $L,M$ disjoints sont +calculablement séparables si et seulement s'il existe un algorithme +qui, prenant en entrée un élément $x$ de $\mathbb{N}$ : +\begin{itemize} +\item termine toujours en temps fini, +\item répond « vrai » si $x\in L$ et « faux » si $x \in M$ (rien n'est + imposé si $x\not\in L\cup M$ à part de terminer en temps fini). +\end{itemize} + +\begin{corrige} +Si $E$ est décidable tel que $L \subseteq E$ et $M \subseteq +(\mathbb{N}\setminus E)$, alors un algorithme qui décide $E$ +(c'est-à-dire, quand on lui fournit l'entrée $x$, répond « vrai » si +$x\in E$, et « faux » si $x \not\in E$) répond bien aux critères +demandés. Réciproquement, donné un algorithme qui répond aux critères +demandés, si $E$ est l'ensemble des $x$ sur lesquels il répond +« vrai », alors $E$ est bien décidable (on peut toujours modifier +l'algorithme si nécessaire pour qu'il ne réponde que « vrai » ou +« faux »), et on a $L \subseteq E$ et $M \subseteq +(\mathbb{N}\setminus E)$. +\end{corrige} + +(2) Expliquer pourquoi deux langages \emph{décidables} disjoints sont +toujours calculablement séparables. + +\begin{corrige} +Si $L,M$ sont décidables disjoints, on peut poser $E = L$, qui est +décidable et vérifie à la fois $L \subseteq E$ (trivialement) et $M +\subseteq (\mathbb{N}\setminus E)$ (c'est une reformulation du fait +que $M$ est disjoint de $E=L$). +\end{corrige} + +On cherche maintenant à montrer qu'il existe deux langages $L,M$ +\emph{semi-décidables} disjoints et calculablement inséparables. + +Pour cela, on appelle $L$ l'ensemble des couples\footnote{Pour être + rigoureux, on a fixé un codage de Gödel 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}$. 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 et +renvoie la valeur $1$ (ce qui peut se noter $\varphi_e(x) = 1$) ; et +$M$ le langage défini de la même manière mais avec la valeur $2$, +i.e., $\varphi_e(x) = 2$. (Ici, $1$ et $2$ peuvent être remplacés par +deux éléments distincts quelconques de $\mathbb{N}$ : si on a souhaité +remplacer $\mathbb{N}$ par $\Sigma^*$, on peut prendre deux mots +distincts quelconques, par exemple $a$ et $aa$.) + +(3) Pourquoi $L$ et $M$ sont-ils disjoints ? + +\begin{corrige} +Comme $L$ est l'ensemble des couples $(e,x)$ tels que $\varphi_e(x) = +1$ et $M$ l'ensemble des couples $(e,x)$ tels que $\varphi_e(x) = 2$, +aucun couple ne peut appartenir aux deux, c'est-à-dire qu'ils sont +disjoints. +\end{corrige} + +(4) Pourquoi $L$ et $M$ sont-ils semi-décidables ? + +\begin{corrige} +Pour semi-décider si un couple $(e,x)$ appartient à $L$, il suffit de +lancer l'exécution du programme $e$ sur l'entrée $x$ et, si elle +termine en retournant $1$, renvoyer « vrai », tandis que si elle +termine en renvoyant n'importe quelle autre valeur, faire une boucle +infinie (bien sûr, si le programme $e$ ne termine jamais sur +l'entrée $x$, on ne termine pas non plus). Ceci montre que $L$ est +semi-décidable. Le même raisonnement s'applique pour $M$. +\end{corrige} + +(5) En imitant la démonstration du théorème de Turing sur +l'indécidabilité du problème de l'arrêt, montrer qu'il n'existe aucun +algorithme qui, prenant en entrée un couple $(e,x)$, termine toujours +en temps fini et répond « vrai » si $(e,x)\in L$ et « faux » si $(e,x) +\in M$ (indication : si un tel algorithme existait, on pourrait s'en +servir pour faire le contraire de ce qu'il prédit). + +\begin{corrige} +Montrons par l'absurde qu'il n'existe aucun algorithme $T$ comme +annoncé. Définissons un nouvel algorithme $T'$ qui, donné un +entier $e$, effectue les calculs suivants : (1º) interroger +l'algorithme $T$ (supposé exister !) en lui fournissant le couple +$(e,e)$ comme entrée, et ensuite (2º) s'il répond vrai, renvoyer la +valeur $2$, tandis que s'il répond n'importe quoi d'autre, renvoyer la +valeur $1$. L'algorithme $T'$ qui vient d'être décrit aurait un +certain numéro, disons, $p$, et la description de l'algorithme fait +qu'il termine toujours, que la valeur $\varphi_p(e)$ qu'il renvoie +vaut toujours soit $1$ soit $2$, et qu'elle vaut $2$ si $(e,e) \in L$ +(c'est-à-dire si $\varphi_e(e) = 1$) et $1$ si $(e,e) \in M$ +(c'est-à-dire si $\varphi_e(e) = 2$). En particulier, en prenant +$e=p$, on voit que $\varphi_p(p)$ doit valoir $1$ ou $2$, doit valoir +$2$ si $\varphi_p(p) = 1$ et $1$ si $\varphi_p(p) = 2$, ce qui est une +contradiction. +\end{corrige} + +(6) Conclure. + +\begin{corrige} +La question (5) montre (compte tenu de la question (1)) que $L$ et $M$ +ne sont pas calculablement séparables, i.e.., sont calculablement +inséparables, tandis que (4) et (5) montrent que $L$ et $M$ sont +disjoints et semi-décidables. On a donc bien montré l'existence de +langages semi-décidables disjoints et calculablement inséparables. +\end{corrige} + + + +% +% +% +\end{document} |