diff options
| -rw-r--r-- | controle-20220616.tex | 2 | ||||
| -rw-r--r-- | controle-20220825.tex | 683 | ||||
| -rw-r--r-- | controle-20230615.tex | 870 | ||||
| -rw-r--r-- | programme-inf105.tex | 35 | ||||
| -rw-r--r-- | rattrapage-20230621.tex | 575 |
5 files changed, 2139 insertions, 26 deletions
diff --git a/controle-20220616.tex b/controle-20220616.tex index 16b7abf..7439a45 100644 --- a/controle-20220616.tex +++ b/controle-20220616.tex @@ -509,7 +509,7 @@ 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. +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 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} diff --git a/controle-20230615.tex b/controle-20230615.tex new file mode 100644 index 0000000..d9bc00d --- /dev/null +++ b/controle-20230615.tex @@ -0,0 +1,870 @@ +%% 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 — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{15 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 + +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} et \emph{approximatif} : exercice 1 : +(a) $1.5$, (b) $1.5$, (c) $1$, (d) $4$, (e) $3$, (f) $3$ (soit au +total $14$) ; exercice 2 : (a) $1$, (b) $2$, (c) $1$, (d) $2$ (soit au +total $6$). + +\ifcorrige +Ce corrigé comporte 8 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 les huit +automates suivants +($A_{\mathrm{s}},A_{\mathrm{t}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{w}},A_{\mathrm{x}},A_{\mathrm{y}},A_{\mathrm{z}}$) +sur l'alphabet $\Sigma$ : + +\begin{center} +\begin{tabular}{|c|c|} +\hline +$A_{\mathrm{s}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{t}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{u}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{v}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{w}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0); +\draw[->] (q1) to[loop above] node[auto]{$a,b$} (q1); +\draw[->] (q2) to[loop above] node[auto]{$a,b$} (q2); +\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3); +\draw[->] (q4) to[loop above] node[auto]{$a,b$} (q4); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{x}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting below] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting below] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting below] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting below] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting below] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting below] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{y}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,initial above] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,initial above] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,initial above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,initial above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,initial above,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{z}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial above,accepting below] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,initial above,accepting below] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,initial above,accepting below] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,initial above,accepting below] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,initial above,accepting below] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,initial above,accepting below] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +\end{tabular} +\end{center} + +On définit aussi les douze langages suivants, où $w_0$ désigne le +mot $ababb$ : +\begin{itemize} +\item $L_0 = \varnothing$ : le langage vide. +\item $L_1 = \{w_0\}$ : le langage constitué du seul mot $w_0$. +\item $L_2$ : le langage constitué des mots qui sont un sous-mot de + $w_0$. +\item $L_3$ : le langage constitué des mots qui ont $w_0$ comme + sous-mot. +\item $L_4$ : le langage constitué des mots qui sont un facteur de + $w_0$. +\item $L_5$ : le langage constitué des mots qui ont $w_0$ comme + facteur. +\item $L_6$ : le langage constitué des mots qui sont un préfixe de + $w_0$. +\item $L_7$ : le langage constitué des mots qui ont $w_0$ comme + préfixe. +\item $L_8$ : le langage constitué des mots qui sont un suffixe de + $w_0$. +\item $L_9$ : le langage constitué des mots qui ont $w_0$ comme + suffixe. +\item $L_{10} = \{w_0^i : i\in\mathbb{N}\}$ : le langage constitué des + mots qui sont une répétition d'un nombre quelconque ($i$) de copies + de $w_0$ (par exemple, $ababbababb$). +\item $L_{11} = \{b^i w_0 a^i : i\in\mathbb{N}\}$ : le langage + constitué des mots obtenus en précédant $w_0$ d'un nombre + quelconque ($i$) de copies de la lettre $b$ et en le suivant du même + nombre de copies de la lettre $a$ (par exemple, $bbababbaa$). +\end{itemize} + +\textbf{(a)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire lequel ou +lesquels parmi les douze langages $L_0,\ldots,L_{11}$ est celui +reconnu par l'automate $A$. On ne demande pas de justifier la +réponse. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ reconnaît le langage $L_1 = \{w_0\}$. + +L'automate $A_{\mathrm{t}}$ reconnaît le langage $L_9$ des mots ayant +$w_0$ comme suffixe (car un chemin dans $A_{\mathrm{t}}$ finit par un +chemin consommant $w_0$). + +L'automate $A_{\mathrm{u}}$ reconnaît le langage $L_7$ des mots ayant +$w_0$ comme préfixe (car un chemin dans $A_{\mathrm{u}}$ commence +par un chemin consommant $w_0$). + +L'automate $A_{\mathrm{v}}$ reconnaît le langage $L_5$ des mots ayant +$w_0$ comme facteur (car un chemin dans $A_{\mathrm{u}}$ passe par un +chemin consommant $w_0$). + +L'automate $A_{\mathrm{w}}$ reconnaît le langage $L_3$ des mots ayant +$w_0$ comme sous-mot (car un chemin dans $A_{\mathrm{u}}$ consomme les +lettres $a,b,a,b,b$ dans cet ordre, intercalées par un nombre +quelconque de lettres quelconques). + +L'automate $A_{\mathrm{x}}$ reconnaît le langage $L_6$ des préfixes +de $w_0$ (car un chemin dans $A_{\mathrm{x}}$ consomme le début +de $w_0$). + +L'automate $A_{\mathrm{y}}$ reconnaît le langage $L_8$ des suffixes +de $w_0$ (car un chemin dans $A_{\mathrm{y}}$ consomme la fin +de $w_0$). + +L'automate $A_{\mathrm{z}}$ reconnaît le langage $L_4$ des facteurs +de $w_0$ (car un chemin dans $A_{\mathrm{z}}$ consomme un intervalle +de lettres consécutives de $w_0$). + +(Les justifications entre parenthèses n'étaient pas demandées.) +\end{corrige} + +\textbf{(b)} Pour chacun des sept automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}\}$ (cette question-ci n'est pas posée +pour $A_{\mathrm{z}}$), donner une expression rationnelle dénotant le +langage $L$ reconnu par $A$. On ne demande pas de justifier la +réponse, et il n'est pas obligatoire d'appliquer un algorithme vu en +cours. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ reconnaît le langage dénoté par $ababb$. + +L'automate $A_{\mathrm{t}}$ reconnaît le langage dénoté +par $(a|b){*}ababb$. + +L'automate $A_{\mathrm{u}}$ reconnaît le langage dénoté +par $ababb(a|b){*}$. + +L'automate $A_{\mathrm{v}}$ reconnaît le langage dénoté +par $(a|b){*}ababb(a|b){*}$. + +L'automate $A_{\mathrm{w}}$ reconnaît le langage dénoté +par $(a|b){*}a(a|b){*}b(a|b){*}a(a|b){*}b(a|b){*}b(a|b){*}$. + +L'automate $A_{\mathrm{x}}$ reconnaît le langage dénoté +par $\underline{\varepsilon}|a|ab|aba|abab|ababb$ (simple énumération +de tous les préfixes de $w_0$) ou, si on préfère, par +$\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|b))))$ +(obtenue en éliminant les états de $A_{\mathrm{x}}$ dans +l'ordre $5,4,3,2,1,0$). + +L'automate $A_{\mathrm{y}}$ reconnaît le langage dénoté +par $\underline{\varepsilon}|b|bb|abb|babb|ababb$ (simple énumération +de tous les suffixes de $w_0$) ou, si on préfère, par +$\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|a)b)a)b)b$ +(obtenue en éliminant les états de $A_{\mathrm{y}}$ dans +l'ordre $0,1,2,3,4,5$). +\end{corrige} + +\textbf{(c)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire de quel type +d'automate vu en cours (DFA complet, DFA à spécification incomplète, +NFA ou bien NFA à transitions spontanées) est l'automate $A$. On +donnera à chaque fois le type le plus particulier applicable. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{t}}$ est un NFA (à cause de la double +transition étiquetée $a$ depuis l'état $0$). + +L'automate $A_{\mathrm{u}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{v}}$ est un NFA. + +L'automate $A_{\mathrm{w}}$ est un NFA. + +L'automate $A_{\mathrm{x}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{y}}$ est un NFA (à cause des multiples états +initiaux). + +L'automate $A_{\mathrm{z}}$ est un NFA. +\end{corrige} + +\textbf{(d)} Pour chacun des cinq automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{x}}, A_{\mathrm{z}}\}$ +(cette question-ci n'est pas posée pour $A_{\mathrm{t}}, +A_{\mathrm{w}}, A_{\mathrm{y}}$), donner un DFA complet sans état +inaccessible qui soit équivalent à $A$ (c'est-à-dire, reconnaissant le +langage $L$). On appliquera un algorithme vu en cours en le nommant. + +{\footnotesize Conseil sur la présentation graphique : pour s'éviter + des maux de tête dans le placement des états (et en éviter aussi au + correcteur), il est conseillé de commencer par placer + horizontalement de gauche à droite les états successifs rencontrés + lors de la consommation du mot $w_0 = ababb$ par l'automate + construit, et d'ajouter ensuite les autres états éventuellement + nécessaires.\par} + +\begin{corrige} +S'agissant de $A_{\mathrm{s}}$, comme c'est un DFAi, il s'agit +simplement de lui ajouter un état « puits », noté $\bot$ ci-dessous, +où aboutissent toutes les transitions manquantes : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax +La construction est analogue pour $A_{\mathrm{u}}$ : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax S'agissant de $A_{\mathrm{v}}$, on a affaire à +un « vrai » non-déterminisme et on applique donc l'algorithme de +déterminisation vu en cours, qui donne (en omettant les accolades dans +le nommage des états) : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {\small $0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {\small $0,1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {\small $0,2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {\small $0,1,3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {\small $0,2,4$}; +\node (q5) at (300bp,-45bp) [draw,circle,state,final] {\small $0,5$}; +\node (q1X) at (30bp,-90bp) [draw,circle,state,accepting below] {\small $0,1,5$}; +\node (q2X) at (110bp,-90bp) [draw,circle,state,accepting below] {\small $0,2,5$}; +\node (q3X) at (190bp,-90bp) [draw,circle,state,accepting below] {\small $0,1,3,5$}; +\node (q4X) at (270bp,-90bp) [draw,circle,state,accepting below] {\small $0,2,4,5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop below] node[auto]{$b$} (q0); +\draw[->] (q1) to[loop below] node[auto]{$a$} (q1); +\draw[->] (q2) to[out=120,in=60] node[auto,swap]{$b$} (q0); +\draw[->] (q3) to[out=120,in=60] node[auto,swap]{$a$} (q1); +\draw[->] (q4) to[out=120,in=60] node[auto,swap]{$a$} (q3); +\draw[->] (q5) to[loop above] node[auto]{$b$} (q5); +\draw[->] (q5) to[out=165,in=45] node[auto,swap,near end]{$a$} (q1X); +\draw[->] (q1X) -- node[auto]{$b$} (q2X); +\draw[->] (q2X) -- node[auto]{$a$} (q3X); +\draw[->] (q3X) -- node[auto]{$b$} (q4X); +\draw[->] (q4X) -- node[auto,swap]{$b$} (q5); +\draw[->] (q1X) to[loop left] node[auto]{$a$} (q1X); +\draw[->] (q2X) to[out=45,in=195] node[auto]{$b$} (q5); +\draw[->] (q3X) to[out=240,in=300] node[auto]{$a$} (q1X); +\draw[->] (q4X) to[out=240,in=300] node[auto]{$a$} (q3X); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax {\footnotesize\textbf{Note:} Une version + précédente de ce corrigé donnait un automate certes correct (DFA + complet sans état inaccessible qui soit équivalent à $A$) mais qui + n'est pas celui, représenté ci-dessus, obtenu en appliquant + l'algorithme de déterminisation. (L'automate qui était représenté + était, en fait, l'automate minimal obtenu en identifiant tous les + états contenant $5$ dans celui ci-dessus.)\par} +La construction pour $A_{\mathrm{x}}$ est exactement comme pour +$A_{\mathrm{s}}$ sauf que les états $0$ à $5$ sont tous marqués +finaux : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax +S'agissant de $A_{\mathrm{z}}$, on a de nouveau affaire à un « vrai » +non-déterminisme et on applique donc l'algorithme de déterminisation +vu en cours, qui donne (en omettant les accolades dans le nommage des +états) : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)] +\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2,4$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (q245) at (120bp,-120bp) [draw,circle,state,accepting below] {\small $2,4,5$}; +\node (qbot) at (300bp,-90bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (qI) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (qI) to[out=270,in=150] node[auto,swap]{$b$} (q245); +\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot); +\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5); +\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto,near start]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (q245) to[out=60,in=240] node[auto]{$a$} (q3); +\draw[->] (q245) to[out=30,in=240] node[auto,swap,very near end]{$b$} (q5); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +où on a noté $I$ au lieu de $\{0,1,2,3,4,5\}$. +\end{corrige} + +\textbf{(e)} Pour $A = A_{\mathrm{z}}$ (et seulement celui-ci), +minimiser le DFA trouvé à la question (d). + +\begin{corrige} +On a affaire à un DFA complet sans état inaccessible : on va le +minimiser avec l'algorithme de Moore. + +Dans une première étape, on fait deux classes d'état : celle des états +finaux, c'est-à-dire $I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ +et celle des états non-finaux, c'est-à-dire le seul +état $\varnothing$. + +Séparons maintenant les états selon la cible de la transition +étiquetée par $a$ : la classe formée de +$I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ se scinde en deux : +$I,\{2,4\},\{2,4,5\}$ d'une part, où elle mène à un état final, et +$\{1,3\},\{3\},\{4\},\{5\}$ d'autre part, où elle mène à un état +non-final. La cible de la transition étiquetée par $b$, pour sa part, +sépare $\{5\}$ de tous les autres états (le seul où elle mène à un +état non-final). À ce stade, on a quatre classes : la classe formée +de $I,\{2,4\},\{2,4,5\}$, celle de $\{1,3\},\{3\},\{4\}$, et deux +classes singleton, $\{5\}$ et $\varnothing$. + +À l'étape suivante, la cible de la transition étiquetée par $a$ ne +sépare rien (les états de la première classe mènent à la seconde et +les états de la seconde mènent au puits). La cible de la transition +étiquetée par $b$, en revanche, sépare la classe formée de +$I,\{2,4\},\{2,4,5\}$ en $I$ d'une part (qui mène à cette même classe) +et $\{2,4\},\{2,4,5\}$ de l'autre (qui mène à $\{5\}$) ; et elle +sépare la classe formée de $\{1,3\},\{3\},\{4\}$ en trois (puisque les +cibles sont dans trois classes distinctes). À ce stade, les seuls +états qui n'ont pas été séparés sont $\{2,4\}$ et $\{2,4,5\}$. Or +comme ils ont exactement les mêmes cibles de transitions étiquetées +par $a$ et $b$, ils ne sont pas séparés, donc l'algorithme s'applique +ici : il fusionne exactement deux états, à savoir +$\{2,4\}$ et $\{2,4,5\}$, en un seul, que nous noterons $B$ : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)] +\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$B$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (qI) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (qI) to[out=60,in=120] node[auto]{$b$} (q2); +\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot); +\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5); +\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +\textbf{(f)} Parmi les douze langages $L_0,\ldots,L_{11}$, lesquels +sont rationnels ? Lesquels sont algébriques ? Lesquels sont +décidables ? Lesquels sont semi-décidables ? On justifiera la +réponse à chaque fois (par exemple en donnant une expression +rationnelle, un automate, une grammaire hors-contexte, un algorithme, +ou n'importe quel autre type d'argument permettant de conclure). + +\begin{corrige} +Les langages $L_1,L_3,L_4,L_5,L_6,L_7,L_8,L_9$ sont rationnels car ils +sont reconnaissables : on a vu que les automates $A_{\mathrm{s}}, +A_{\mathrm{w}}, A_{\mathrm{z}}, A_{\mathrm{v}}, A_{\mathrm{x}}, +A_{\mathrm{u}}, A_{\mathrm{y}}, A_{\mathrm{t}}$ respectivement les +reconnaissent. Il reste donc à traiter le cas de +$L_0,L_2,L_{10},L_{11}$. + +Les langages $L_0$ et $L_2$ sont rationnels car ils sont finis (on +peut donner des expressions rationnelles pour les deux, à savoir +$\bot$ pour $L_0$ et, en énumérant systématiquement tous les +sous-mots, $\varepsilon | b | bb | a | ab | abb | bbb | ba | bab | +babb | aa | aab | aabb | abbb | aba | abab | ababb$ pour $L_2$, mais +ce n'est pas très intéressant et ce n'était pas demandé). + +Le langage $L_{10} = \{w_0^i : i\in\mathbb{N}\} = L_1^*$ est rationnel +car il est l'étoile de Kleene d'un langage rationnel (si on préfère, +il est dénoté par l'expression rationnelle $(ababb){*}$). + +Tous les langages $L_0$ à $L_{10}$ sont donc rationnels, et, en +particulier, algébriques, décidables et semi-décidables. + +Reste à évoquer le cas du langage $L_{11} = \{b^i w_0 a^i : +i\in\mathbb{N}\}$. Montrons qu'il n'est pas rationnel, et montrons +qu'il est algébrique. + +Il n'est pas rationnel par le lemme de pompage. En effet, supposons +par l'absurde que $\{b^i w_0 a^i : i\in\mathbb{N}\}$ soit rationnel, +et soit $k$ tel que donné par le lemme de pompage. Considérons le mot +$t := b^k ababb a^k \in L_{11}$. D'après la propriété de $k$, il +existe une factorisation $t = uvw$ vérifiant les propriétés garanties +par le lemme de pompage. Le fait que $|uv|\leq k$, comme le préfixe +de longueur $k$ de $t$ est formé uniquement de la lettre $b$, assure +que $u = b^{\ell_1}$ et $v = b^{\ell_2}$ pour certains $\ell_1,\ell_2$ +avec, de plus, $\ell_2 > 0$ (car $v\neq\varepsilon$) et +$\ell_1+\ell_2\leq k$. On a alors $w = b^{k-\ell_1-\ell_2} ababb +a^k$, et $uv^iw = b^{k+(i-1)\ell_2} ababb a^k$. Comme les mots de +$L_{11}$ ont la propriété nécessaire que leur nombre initial de $b$ +(i.e., la longueur de leur plus long préfixe formé uniquement de la +lettre $b$) est égale à leur nombre final de $a$ (i.e., la longueur de +leur plus long suffixe formé uniquement de la lettre $a$), on devrait +avoir $k+(i-1)\ell_2 = k$, ce qui est une contradiction dès que $i\neq +1$. + +En revanche, le langage $L_{11}$ est algébrique, car il est engendré +par la grammaire suivante d'axiome $S$ : +\[ +S \rightarrow ababb \;|\; bSa +\] +Étant algébrique, le langage $L_{11}$ est décidable et semi-décidable. +(Au demeurant, il est facile de donner un algorithme qui décide si un +mot appartient à $L_{11}$ : on vérifie que son nombre initial de $b$ +est égal à son nombre final de $a$ et, une fois ce fait vérifié, on +vérifie qu'une fois retiré le préfixe et le suffixe en question il +reste exactement le mot $ababb$.) + +Pour résumer, tous les langages dont on a parlé sont algébriques, +décidables et semi-décidables, et tous sauf $L_{11}$ sont rationnels. +\end{corrige} + + +% +% +% + +\exercice + +{\footnotesize Dans cet exercice, les questions (1) et (2) sont + indépendantes, et la question (4) ne dépend que de la + question (2).\par} + +\textbf{(1)} La fonction $h\colon \mathbb{N} \to \mathbb{N}$ suivante +est-elle calculable ? +\[ +h(0) = 1\;\;,\;\; +h(1) = 10\;\;,\;\; +h(2) = 10^{10}\;\;,\;\; +h(3) = 10^{10^{\scriptstyle 10}}\;\;,\;\; +h(4) = 10^{10^{\scriptstyle 10^{\scriptstyle 10}}}\;\;,\;\; +\] +\[ +\left.\begin{matrix} h(n) = 10^{\scriptstyle 10^{\scriptstyle \cdots^{\scriptstyle 10}}}\end{matrix}\right\} n +\] +(Autrement dit, $h(n)$ est une tour d'exponentielle de hauteur $n$ sur +le nombre $10$. Bien sûr, $10^{10^{\scriptstyle 10}}$ se comprend +comme $10^{\big(10^{\scriptstyle 10}\big)}$.) + +\begin{corrige} +La fonction $g\colon n\mapsto 10^n$ est calculable : en effet, on peut +exécuter une boucle à $n$ itérations en multipliant par $10$ la valeur +d'une variable en partant de $1$. On en déduit que la fonction $h$ +est calculable : en effet, on peut exécuter une boucle à $n$ +itérations en appliquant la fonction $g$ à une variable en partant +de $1$. +\end{corrige} + +\medskip + +Fixons maintenant une numérotation (« codage de Gödel ») des +algorithmes prenant en entrée un entier et renvoyant un entier, et +appelons $\varphi_e(n)$ le résultat de l'exécution du programme codé +par l'entier $e$ sur l'entrée $n$, si cette exécution termine (et +$\varphi_e(n)$ non défini si cette exécution ne termine pas). +Considérons la fonction $b\colon \mathbb{N} \to \mathbb{N}$ suivante : +\[ +b(n) = \max\{\varphi_e(n) : 0\leq e\leq n +\text{~et~}\varphi_e(n)\text{~défini}\} +\] +(Autrement dit, $b(n)$ est la plus grande des valeurs $\varphi_e(n)$ +qui sont définies lorsque $e$ parcourt les entiers de $0$ à $n$.) + +\textbf{(2)} On veut montrer que pour toute fonction calculable +$f\colon \mathbb{N} \to \mathbb{N}$, il existe un $n_0$ tel que pour +tout $n\geq n_0$ on ait $b(n) > f(n)$. Supposons donc $f\colon +\mathbb{N} \to \mathbb{N}$ calculable.\quad\textbf{(a)} Expliquer +pourquoi il existe $p$ tel que $\varphi_p = f+1$ (c'est-à-dire +$\varphi_p(n) = f(n)+1$ pour tout $n$).\quad\textbf{(b)} En déduire +que $b(n) > f(n)$ lorsque $n\geq p$, et conclure. + +\begin{corrige} +\textbf{(a)} La fonction $n \mapsto f(n)+1$ est calculable puisque $f$ +l'est et que l'addition l'est. Il existe donc un algorithme qui la +calcule, c'est-à-dire un $p$ tel que $\varphi_p = f+1$. + +\textbf{(b)} Sachant que $\varphi_p = f+1$, si $n \geq p$, la valeur +$b(n)$ est le maximum des valeurs $\varphi_e(n)$ qui sont définies +lorsque $e$ et $n$ parcourent les entiers de $0$ à $n$. En +particulier, puisque $0\leq p\leq n$, parmi ces entiers se trouve la +valeur $\varphi_p(n) = f(n)+1$ (qui est bien définie car $f$ est une +fonction totale ici). On a donc $b(n) \geq \varphi_p(n) = f(n)+1 > +f(n)$. On a bien montré que si $n \geq p$ alors $b(n) > f(n)$, ce qui +était voulu (pour $n_0 = p$). +\end{corrige} + +\textbf{(3)} Montrer que (pour les fonctions $h$ et $b$ introduites +ci-dessus) : +\[ +\lim_{n\to+\infty} \frac{b(n)}{h(n)} = +\infty +\] + +\begin{corrige} +On souhaite montrer que pour tout $C>0$ il existe $n_0$ tel que si +$n\geq n_0$ alors $\frac{b(n)}{h(n)} > C$. Pour cela, soit $C$ un +réel $>0$, et, quitte à l'augmenter encore un peu, on peut supposer +$C$ entier. La fonction $C\cdot h$ (c'est-à-dire $n \mapsto C\cdot +h(n)$) est calculable car $h$ l'est (question (1)) et que la +multiplication l'est. D'après la question (2), il existe $n_0$ tel +que pour tout $n\geq n_0$ on ait $b(n) > C\cdot h(n)$ : c'est ce qu'on +voulait montrer. +\end{corrige} + +\textbf{(4)} On se propose ici de redémontrer l'indécidabilité du +problème de l'arrêt de manière légèrement différente de ce qui a été +vu en cours. Supposons donc par l'absurde que le problème de l'arrêt +$H = \{(e,n) : \varphi_e(n)\text{~défini}\}$ soit +décidable.\quad\textbf{(a)} Montrer soigneusement, sous cette +hypothèse, que $b$ est calculable.\quad\textbf{(b)} Conclure. + +\begin{corrige} +\textbf{(a)} Supposons par l'absurde qu'il existe un algorithme $T$ +qui décide le problème de l'arrêt : autrement dit, donnés $e$ et $n$, +cet algorithme est censé terminer en temps fini et répondre « oui » si +le programme codé par $e$ termine sur l'entrée $n$, « non » sinon. On +peut alors calculer $b(n)$ de la manière suivante : on démarre avec +$m=0$ et on effectue une boucle pour $e$ allant de $0$ à $n$, et pour +chacune des valeurs en question, on utilise $T$ pour savoir si +$\varphi_e(n)$ est défini, puis, \emph{si} c'est le cas, on caclcule +cette valeur $\varphi_e(n)$ au moyen de la machine universelle (ce +calcul termine en temps fini justement puisque $\varphi_e(n)$ est +défini), et on remplace la variable $m$ par $\max(m, \varphi_e(n))$. +À la fin de la boucle, on a bien calculé le max de toutes les valeurs +$\varphi_e(n)$ qui sont définies, c'est-à-dire $b(m)$. La fonction +$b$ est donc calculable (de nouveau, sous l'hypothèse que le problème +de l'arrêt l'est). + +\textbf{(b)} On a vu en (2) que pour toute fonction calculable $f$ il +existe un $n_0$ tel que pour tout $n\geq n_0$ on ait $b(n) > f(n)$. +Comme on vient de voir que (sous l'hypothèse que le problème de +l'arrêt est calculable) la fonction $b$ est calculable, en appliquant +ce résultat à $f = b$, il doit exister un $n_0$ tel que tout $n\geq +n_0$ on ait $b(n) > b(n)$, ce qui est absurde. C'est donc que +l'hypothèse était absurde : le problème de l'arrêt n'est pas +décidable. +\end{corrige} + + +% +% +% +\end{document} diff --git a/programme-inf105.tex b/programme-inf105.tex index 909924c..a65fc55 100644 --- a/programme-inf105.tex +++ b/programme-inf105.tex @@ -102,39 +102,23 @@ peut décider algorithmiquement si deux expressions rationnelles sont \thingy TD sur les automates finis et langages rationnels. -\thingy Grammaires hors contexte\footnote{Je propose pour gagner du - temps de ne faire que mentionner au passage le fait qu'il existe des - grammaires plus générales, sans entrer dans les détails.}, langages -algébriques (=définis par une grammaire hors contexte). Dérivations, -dérivations gauches et droites. Arbre d'analyse (=de dérivation). -Ambiguïté (grammaires inambiguës et ambiguës, exemple sans -démonstration de langage intrinsèquement ambigu). +\thingy Grammaires hors contexte, langages algébriques (=définis par +une grammaire hors contexte). Dérivations\footnote{On pourra même + sauter complètement la notion de dérivation et définir le langage + engendré par une grammaire à travers les arbres d'analyse.}. Arbre +d'analyse (=de dérivation). Ambiguïté (grammaires inambiguës et +ambiguës). Stabilité des langages algébriques par réunion, concaténation et étoile de Kleene. Les langages rationnels sont algébriques : d'après ce qu'on vient de dire et directement en associant une grammaire à un DFA ou NFA. -\thingy L'intersection d'un langage algébrique et d'un langage +L'intersection d'un langage algébrique et d'un langage rationnel est algébrique (admis sans démonstration). -Lemme de pompage pour les langages algébriques (admis sans -démonstration, mais on peut esquisser l'idée). - L'appartenance d'un mot au langage défini par une grammaire hors -contexte est algorithmiquement décidable (l'énoncer et éventuellement -expliquer une approche possible\footnote{Par ex., en montrant qu'on - peut trouver une grammaire monotone équivalente ; ou bien esquisser - comment on peut mettre la grammaire sous forme normale de Chomsky et - utiliser l'algorithme de programmation dynamique (CYK) ?} si le -temps le permet). - -Selon le temps disponible : quelques notions sur l'analyse syntaxique -en pratique : notion d'analyseurs descendants et ascendants (sans -entrer dans les détails). - - -\thingy TD sur les grammaires hors contexte et langages algébriques. +contexte est algorithmiquement décidable (admis sans démonstration). \thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas @@ -154,7 +138,8 @@ semi-décidables. Un ensemble est semi-décidable ssi il est (vide ou) \thingy Notion de machine universelle. Indécidabilité du problème de l'arrêt. -Petit TD sur la calculabilité. +\thingy TD sur les grammaires hors contexte / langages algébriques, et +sur la calculabilité. % 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} |