diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 2588 |
1 files changed, 2586 insertions, 2 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 737ff57..ef982a0 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -30,6 +30,8 @@ \newtheorem{comcnt}{Tout}[subsection] \newcommand\thingy{% \refstepcounter{comcnt}\medskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}} \newtheorem{defn}[comcnt]{Définition} \newtheorem{prop}[comcnt]{Proposition} \newtheorem{lem}[comcnt]{Lemme} @@ -60,6 +62,15 @@ \hbox to0pt{\hskip-\hangindent\dbend\hfill}} % \newcommand{\defin}[2][]{\def\latexsucks{#1}\ifx\latexsucks\empty\index{#2}\else\index{\latexsucks}\fi\textbf{#2}} +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +% +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\footnotesize\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\relax\else\egroup\fi\par} % % % NOTE: compile dot files with @@ -5696,7 +5707,7 @@ hors contexte $G$ (absolument quelconque) est la suivante : Énonçons précisément le résultat en question : \begin{thm}\label{algebraic-languages-are-decidable} -Il existe un algorithme qui, donnée une grammaire hors-contexte $G$ +Il existe un algorithme qui, donnée une grammaire hors contexte $G$ (sur un alphabet $\Sigma$) et un mot $w \in \Sigma^*$, décide si $w \in L(G)$. Autrement dit, les langages algébriques sont \emph{décidables} au sens @@ -5705,7 +5716,7 @@ de \ref{definition-computable-function-or-set}. Plus exactement, on montre : \begin{itemize} \item Il existe un algorithme qui, donnée une grammaire - hors-contexte $G$ (sur un alphabet $\Sigma$), calcule une grammaire + hors contexte $G$ (sur un alphabet $\Sigma$), calcule une grammaire $G'$ (sur le même alphabet $\Sigma$ et ayant le même ensemble $N$ de nonterminaux que $G$) dont toutes les productions sont soit de la forme $T \rightarrow \alpha$ avec $|\alpha| \geq 1$, et une partie @@ -6732,6 +6743,2579 @@ construire un algorithme résolvant le problème de l'arrêt. lequel on travaille.)\par} +% +% +% + +\appendix +\section{Exercices}\label{section-exercises} + +\subsection{Langages rationnels et automates} + +\exercice + +Soit $\Sigma = \{0,1\}$. On appelle \emph{mot binaire} un mot sur +l'alphabet $\Sigma$, et mot binaire \emph{normalisé} un mot binaire +qui \emph{soit} commence par $1$, \emph{soit} est exactement égal +à $0$. + +(1) Montrer que le langage $L_n = \{0, 1, 10, 11, 100, 101,\ldots\}$ +des mots binaires normalisés est rationnel en exhibant directement une +expression rationnelle qui le dénote, et montrer qu'il est +reconnaissable en exhibant directement un automate fini qui le +reconnaît. + +(2) On définit la \emph{valeur numérique} d'un mot binaire +$x_{n-1}\cdots x_0$ comme $\sum_{i=0}^{n-1} x_i 2^i$ (où $x_i$ vaut +$0$ ou $1$ et est numéroté de $0$ pour le chiffre le plus à droite +à $n-1$ pour le plus à gauche) ; la valeur numérique du mot +vide $\varepsilon$ est $0$. + +Parmi les langages suivants, certains sont rationnels. Dire lesquels +et justifier brièvement pourquoi ils le sont (on ne demande pas de +justifier pourquoi ceux qui ne sont pas rationnels ne le sont pas) : + +(a) le langage $L_a$ des mots binaires dont la valeur numérique est +paire, + +(b) le langage $L_b$ des mots binaires \emph{normalisés} dont la +valeur numérique est paire, + +(c) le langage $L_c$ des mots binaires dont la valeur numérique est +multiple de $3$ (indication : selon que $n$ est congru à $0$, $1$ ou +$2$ modulo $3$, et selon que $x$ vaut $0$ ou $1$, à quoi est congru +$2n+x$ modulo $3$ ?), + +(d) le langage $L_d$ des mots binaires dont la valeur numérique est un +nombre premier, + +(e) le langage $L_e$ des mots binaires dont la valeur numérique est +une puissance de $2$, i.e., de la forme $2^i$ pour $i\in\mathbb{N}$, + +\begin{corrige} +(1) On peut écrire $L_n = L_{0|1(0|1){*}}$, langage dénoté par + l'expression rationnelle $0|1(0|1){*}$. Ce langage est reconnu, par + exemple, par le DFAI suivant : +\begin{center} +%%% begin ex1p1 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (qY) at (97bp,105bp) [draw,circle,state,final] {$Y$}; + \node (qX) at (18bp,74bp) [draw,circle,state,initial] {$X$}; + \node (qZ) at (97bp,18bp) [draw,circle,state,final] {$Z$}; + \draw [->] (qX) ..controls (45.279bp,84.58bp) and (58.943bp,90.081bp) .. node[auto] {$0$} (qY); + \draw [->] (qX) ..controls (44.52bp,55.44bp) and (60.758bp,43.63bp) .. node[auto] {$1$} (qZ); + \draw [->] (qZ) to[loop below] node[auto] {$0,1$} (qZ); +% +\end{tikzpicture} + +%%% end ex1p1 %%% +\end{center} + +(2) (a) Le langage $L_a$ est rationnel car il s'agit du langage des +mots binaires qui soit sont le mot vide soit finissent par $0$ : il +est dénoté par l'expression rationnelle +$\underline{\varepsilon}|(0|1){*}0$.\spaceout (b) On a $L_b = L_a \cap +L_n$ et on a vu que $L_a$ et $L_n$ sont rationnels, donc $L_b$ l'est +aussi (on peut aussi exhiber une expression rationnelle qui le +dénote : $0|1(0|1){*}0$). + +(c) Ajouter un $0$ ou un $1$ à la fin d'un mot binaire de valeur +numérique $n$ le transforme en un mot de valeur numérique $2n+x$ +où $x$ est le chiffre affixé. Considérons les six combinaisons entre +les trois cas possibles de la valeur numérique $n$ modulo $3$ et les +deux cas possibles de la valeur de $x$ : +\begin{center} +\begin{tabular}{c|c|c} +$n\equiv?\pmod{3}$&$x=?$&$2n+x\equiv?\pmod{3}$\\\hline +$0$&$0$&$0$\\ +$0$&$1$&$1$\\ +$1$&$0$&$2$\\ +$1$&$1$&$0$\\ +$2$&$0$&$1$\\ +$2$&$1$&$2$\\ +\end{tabular} +\end{center} +Ceci définit un DFA dont les trois états correspondent aux trois +valeurs possibles de $n$ modulo $3$, la transition $n\to n'$ étiquetée +par $x$ correspond au passage de $n$ à $2n+x$ modulo $3$, +c'est-à-dire : +\begin{center} +%%% begin example6 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$0$}; + \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$}; + \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp) .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp) .. node[auto] {$1$} (q0); + \draw [->] (q2) to[loop above] node[auto] {$1$} (q2); + \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp) .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp) .. node[auto] {$0$} (q1); + \draw [->] (q0) to[loop above] node[auto] {$0$} (q0); + \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp) .. node[auto] {$1$} (q1); + \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp) .. node[auto] {$0$} (q2); +% +\end{tikzpicture} + +%%% end example6 %%% +\end{center} +(On a marqué l'état $0$ comme initial car le mot vide a une valeur +numérique congrue à $0$ modulo $3$, et seul $0$ comme final car on +veut reconnaître les multiples de $3$.) + +(d) Le langage $L_d$ n'est pas rationnel (on pourrait le démontrer à +l'aide du lemme de pompage, mais ce n'est pas très facile). + +(e) Le langage $L_e$ est rationnel car il s'agit du langage dénoté par +l'expression rationnelle $0{*}10{*}$. +\end{corrige} + +% + +\exercice + +Soit $\Sigma = \{a\}$. Montrer que le langage $L = \{a^2, a^3, a^5, +a^7, a^{11}, a^{13}\ldots\}$ constitué des mots ayant un nombre +\emph{premier} de $a$, n'est pas rationnel. + +\begin{corrige} +Supposons par l'absurde que $L$ soit rationnel. D'après le lemme de +pompage, il existe un certain $k$ tel que tout mot de $L$ de longueur +$\geq k$ se factorise sous la forme $uvw$ avec (i) $|v|\geq 1$, +(ii) $|uv|\leq k$ et (iii) $uv^iw \in L$ pour tout $i\geq 0$. Soit +$p$ un nombre premier supérieur ou égal à $k$ (qui existe car +l'ensemble des nombres premiers est infini) : le mot $a^p \in L$ +admet une factorisation comme on vient de dire. Posons $|u| =: m$ et +$|v| =: n$, si bien que $|w| = p-m-n$. On a alors $n\geq 1$ +d'après (i), et $|uv^iw| = m + in + (p-m-n) = p+(i-1)n$ est premier +pour tout $i\geq 0$ d'après (iii). En particulier pour $i=p+1$ on +voit que $p + pn = p(n+1)$ est premier, ce qui contredit le fait qu'il +s'agit d'un multiple non-trivial ($n+1\geq 2$) de $p$. +\end{corrige} + +% + +\exercice + +On considère l'automate suivant : +\begin{center} +%%% begin ex1p2a %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (98bp,72bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,47bp) [draw,circle,state,initial] {$0$}; + \node (q3) at (258bp,72bp) [draw,circle,state] {$3$}; + \node (q2) at (178bp,72bp) [draw,circle,state] {$2$}; + \node (q5) at (178bp,18bp) [draw,circle,state] {$5$}; + \node (q4) at (98bp,18bp) [draw,circle,state] {$4$}; + \node (q7) at (338bp,47bp) [draw,circle,state,final] {$7$}; + \node (q6) at (258bp,18bp) [draw,circle,state] {$6$}; + \draw [->] (q2) ..controls (206.11bp,72bp) and (218.58bp,72bp) .. node[auto] {$a$} (q3); + \draw [->] (q3) ..controls (285.85bp,63.395bp) and (299.33bp,59.074bp) .. node[auto] {$\varepsilon$} (q7); + \draw [->] (q7) to[loop below] node[auto] {$a,b$} (q7); + \draw [->] (q6) ..controls (285.62bp,27.897bp) and (299.46bp,33.043bp) .. node[auto] {$\varepsilon$} (q7); + \draw [->] (q4) ..controls (126.11bp,18bp) and (138.58bp,18bp) .. node[auto] {$b$} (q5); + \draw [->] (q0) to[loop below] node[auto] {$a,b$} (q0); + \draw [->] (q0) ..controls (45.62bp,37.103bp) and (59.462bp,31.957bp) .. node[auto] {$\varepsilon$} (q4); + \draw [->] (q5) ..controls (206.11bp,18bp) and (218.58bp,18bp) .. node[auto] {$b$} (q6); + \draw [->] (q0) ..controls (45.849bp,55.605bp) and (59.331bp,59.926bp) .. node[auto] {$\varepsilon$} (q1); + \draw [->] (q1) ..controls (126.11bp,72bp) and (138.58bp,72bp) .. node[auto] {$a$} (q2); +% +\end{tikzpicture} + +%%% end ex1p2a %%% +\end{center} + +(0) Décrire brièvement le langage accepté par l'automate en question. + +(1) Cet automate est-il déterministe ? Si non, le déterminiser. + +(2) Minimiser l'automate déterminisé (on doit trouver un DFA ayant +quatre états). Décrire brièvement la signification de ces quatre +états, de façon à vérifier qu'il accepte le même langage que décrit +en (0). + +(3) Éliminer les états de l'automate d'origine de façon à obtenir une +expression rationnelle dénotant le langage reconnu par le langage +décrit en (0). + +\begin{corrige} +(0) L'automate proposé accepte les mots ayant soit deux $a$ + consécutifs (en passant par le chemin $0\to 1\to 2\to 3\to 7$) soit + deux $b$ consécutifs (en passant par le chemin $0\to 4\to 5\to 6\to + 7$). + +(1) L'automate ayant des ε-transitions, il ne peut pas être + déterministe : on a affaire à un εNFA. Avant de le déterminiser, on + élimine ses ε-transitions : la ε-fermeture de $0$ est $\{0,1,4\}$, + celle de $3$ est $\{3,7\}$ et celle de $6$ est $\{6,7\}$ ; on est + amené au NFA suivant : +\begin{center} +%%% begin ex1p2b %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q0) at (18bp,47bp) [draw,circle,state,initial] {$0$}; + \node (q3) at (178bp,72bp) [draw,circle,state,final,accepting above] {$3$}; + \node (q2) at (98bp,72bp) [draw,circle,state] {$2$}; + \node (q5) at (98bp,18bp) [draw,circle,state] {$5$}; + \node (q7) at (268bp,47bp) [draw,circle,state,final] {$7$}; + \node (q6) at (178bp,18bp) [draw,circle,state,final,accepting below] {$6$}; + \draw [->] (q2) ..controls (126.11bp,72bp) and (138.58bp,72bp) .. node[auto] {$a$} (q3); + \draw [->] (q3) ..controls (208.21bp,63.701bp) and (225.92bp,58.67bp) .. node[auto] {$a,b$} (q7); + \draw [->] (q7) to[loop below] node[auto] {$a,b$} (q7); + \draw [->] (q6) ..controls (208.34bp,27.667bp) and (226.26bp,33.576bp) .. node[auto] {$a,b$} (q7); + \draw [->] (q5) ..controls (126.11bp,18bp) and (138.58bp,18bp) .. node[auto] {$b$} (q6); + \draw [->] (q0) ..controls (45.62bp,37.103bp) and (59.462bp,31.957bp) .. node[auto] {$b$} (q5); + \draw [->] (q0) ..controls (45.849bp,55.605bp) and (59.331bp,59.926bp) .. node[auto] {$a$} (q2); + \draw [->] (q0) to[loop below] node[auto] {$a,b$} (q0); +% +\end{tikzpicture} + +%%% end ex1p2b %%% +\end{center} +(Les états $1$ et $4$ étant inaccessibles, ils ont été retirés. Il ne +faut pas oublier que $3$ et $6$ sont finaux puisqu'ils ont l'état +final $7$ dans leur ε-fermeture.) + +On peut maintenant procéder à la déterminisation. Pour abréger les +noms des états, on note, par exemple, $023$ pour $\{0,2,3\}$. En +construisant de proche en proche, on obtient le DFA suivant : +\begin{center} +\scalebox{0.8}{%PLEASE! There HAS to be a better way to do this! +%%% begin ex1p2c %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\begin{scope} + \pgfsetstrokecolor{black} + \definecolor{strokecol}{rgb}{1.0,1.0,1.0}; + \pgfsetstrokecolor{strokecol} + \definecolor{fillcol}{rgb}{1.0,1.0,1.0}; + \pgfsetfillcolor{fillcol} +\end{scope} +\begin{scope} + \pgfsetstrokecolor{black} + \definecolor{strokecol}{rgb}{1.0,1.0,1.0}; + \pgfsetstrokecolor{strokecol} + \definecolor{fillcol}{rgb}{1.0,1.0,1.0}; + \pgfsetfillcolor{fillcol} +\end{scope} +\begin{scope} + \pgfsetstrokecolor{black} + \definecolor{strokecol}{rgb}{1.0,1.0,1.0}; + \pgfsetstrokecolor{strokecol} + \definecolor{fillcol}{rgb}{1.0,1.0,1.0}; + \pgfsetfillcolor{fillcol} +\end{scope} +\begin{scope} + \pgfsetstrokecolor{black} + \definecolor{strokecol}{rgb}{1.0,1.0,1.0}; + \pgfsetstrokecolor{strokecol} + \definecolor{fillcol}{rgb}{1.0,1.0,1.0}; + \pgfsetfillcolor{fillcol} +\end{scope} + \node (q0) at (18bp,121.73bp) [draw,circle,state,initial] {$0$}; + \node (q027) at (382bp,39.732bp) [draw,circle,state,final] {$027$}; + \node (q056) at (188bp,58.732bp) [draw,circle,state,final,accepting below] {$056$}; + \node (q023) at (188bp,166.73bp) [draw,circle,state,final,accepting above] {$023$}; + \node (q057) at (382bp,185.73bp) [draw,circle,state,final] {$057$}; + \node (q0567) at (285bp,58.732bp) [draw,circle,state,final,accepting above] {$0567$}; + \node (q02) at (100bp,160.73bp) [draw,circle,state] {$02$}; + \node (q0237) at (285bp,166.73bp) [draw,circle,state,final,accepting below] {$0237$}; + \node (q05) at (100bp,68.732bp) [draw,circle,state] {$05$}; + \draw [->] (q057) ..controls (367.95bp,143.33bp) and (356.68bp,115.58bp) .. (340bp,95.732bp) .. controls (334.17bp,88.79bp) and (326.73bp,82.582bp) .. node[auto] {$b$} (q0567); + \draw [->] (q0) ..controls (45.352bp,134.58bp) and (60.273bp,141.85bp) .. node[auto] {$a$} (q02); + \draw [->] (q0237) to[loop above] node[auto] {$a$} (q0237); + \draw [->] (q023) ..controls (213.27bp,203.89bp) and (232.48bp,226.69bp) .. (256bp,236.73bp) .. controls (279.71bp,246.86bp) and (289.57bp,244.97bp) .. (314bp,236.73bp) .. controls (330.09bp,231.3bp) and (345.38bp,220.3bp) .. node[auto] {$b$} (q057); + \draw [->] (q023) ..controls (222.58bp,166.73bp) and (234.64bp,166.73bp) .. node[auto] {$a$} (q0237); + \draw [->] (q02) ..controls (129.57bp,162.73bp) and (142.05bp,163.6bp) .. node[auto] {$a$} (q023); + \draw [->] (q0567) to[loop below] node[auto] {$b$} (q0567); + \draw [->] (q05) ..controls (129.65bp,65.401bp) and (142.24bp,63.937bp) .. node[auto] {$b$} (q056); + \draw [->] (q056) ..controls (222.58bp,58.732bp) and (234.64bp,58.732bp) .. node[auto] {$b$} (q0567); + \draw [->] (q0237) ..controls (322.23bp,165.23bp) and (331.57bp,165.88bp) .. (340bp,167.73bp) .. controls (343.63bp,168.53bp) and (347.33bp,169.66bp) .. node[auto] {$b$} (q057); + \draw [->] (q056) ..controls (217.15bp,28.639bp) and (235.83bp,12.746bp) .. (256bp,5.7322bp) .. controls (280.35bp,-2.7337bp) and (288.93bp,-0.26493bp) .. (314bp,5.7322bp) .. controls (327.41bp,8.9409bp) and (341.18bp,15.299bp) .. node[auto,below] {$a$} (q027); + \draw [->] (q05) ..controls (100bp,100.68bp) and (100bp,117.05bp) .. node[auto] {$a$} (q02); + \draw [->] (q057) ..controls (397.04bp,148.37bp) and (402.36bp,127.76bp) .. (400bp,109.21bp) .. controls (398.44bp,96.972bp) and (395.4bp,83.809bp) .. node[auto] {$a$} (q027); + \draw [->] (q027) ..controls (362.81bp,75.635bp) and (351.82bp,95.041bp) .. (340bp,110.73bp) .. controls (332.19bp,121.1bp) and (322.64bp,131.57bp) .. node[auto] {$a$} (q0237); + \draw [->] (q0567) ..controls (324.14bp,51.105bp) and (336.81bp,48.57bp) .. node[auto,below] {$a$} (q027); + \draw [->] (q027) ..controls (382bp,87.723bp) and (382bp,124.52bp) .. node[auto] {$b$} (q057); + \draw [->] (q02) ..controls (115.85bp,134.94bp) and (120.35bp,122.5bp) .. (118bp,110.98bp) .. controls (116.93bp,105.75bp) and (115.19bp,100.36bp) .. node[auto] {$b$} (q05); + \draw [->] (q0) ..controls (45.218bp,104.36bp) and (61.545bp,93.546bp) .. node[auto] {$b$} (q05); +% +\end{tikzpicture} + +%%% end ex1p2c %%% +} +\end{center} +(À titre d'exemple, la transition étiquetée $b$ partant de l'état +$0237$ conduit à l'état $057$ car les transitions étiquetées $b$ dans +le NFA précédent et partant des états parmi $\{0,2,3,7\}$ sont $0\to +0$, $0\to 5$, $3\to 7$ et $7\to 7$. Tous les états contenant l'un des +symboles $3,6,7$ sont finaux.) + +(2) On a affaire à un DFA (sous-entendu : \emph{complet}) dont tous +les états sont accessibles, on peut donc appliquer directement +l'algorithme de Moore. Une première partition sépare les états +finaux, soit $023, 0237, 027, 056, 0567, 057$ des non-finaux, soit $0, +02, 05$. L'étape suivante distingue $02$ parce que sa $a$-transition +conduit à une classe différente que celles de $0$ et $05$, et $05$ +parce que sa $b$-transition conduit à une classe différente de $0$ et +$02$. Les étapes suivantes ne changent rien. Finalement, on arrive à +un automate à quatre états : +\begin{center} +%%% begin ex1p2d %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\begin{scope} + \pgfsetstrokecolor{black} + \definecolor{strokecol}{rgb}{1.0,1.0,1.0}; + \pgfsetstrokecolor{strokecol} + \definecolor{fillcol}{rgb}{1.0,1.0,1.0}; + \pgfsetfillcolor{fillcol} + \filldraw (0bp,0bp) -- (0bp,112bp) -- (200bp,112bp) -- (200bp,0bp) -- cycle; +\end{scope} + \node (q02) at (100bp,93bp) [draw,circle,state] {$02$}; + \node (q0) at (18bp,56bp) [draw,circle,state,initial] {$0$}; + \node (qA) at (182bp,60bp) [draw,circle,state,final] {$A$}; + \node (q05) at (100bp,19bp) [draw,circle,state] {$05$}; + \draw [->] (q0) ..controls (45.691bp,68.345bp) and (60.407bp,75.151bp) .. node[auto] {$a$} (q02); + \draw [->] (qA) to[loop below] node[auto] {$a,b$} (qA); + \draw [->] (q02) ..controls (129.2bp,81.367bp) and (143.35bp,75.529bp) .. node[auto] {$a$} (qA); + \draw [->] (q05) ..controls (128.81bp,33.252bp) and (143.85bp,40.959bp) .. node[auto,below] {$b$} (qA); + \draw [->] (q05) ..controls (100bp,46.09bp) and (100bp,55.041bp) .. node[auto] {$a$} (q02); + \draw [->] (q02) ..controls (116.71bp,70.13bp) and (120.2bp,60.948bp) .. (118bp,52.251bp) .. controls (117.33bp,49.598bp) and (116.4bp,46.928bp) .. node[auto] {$b$} (q05); + \draw [->] (q0) ..controls (45.691bp,43.655bp) and (60.407bp,36.849bp) .. node[auto] {$b$} (q05); +% +\end{tikzpicture} + +%%% end ex1p2d %%% +\end{center} +où $A$ représente la classe de tous les états finaux de l'automate +précédent. + +La signification des quatre états est la suivante : l'état $0$ +signifie que l'automate n'a encore rien lu, l'état $02$ signifie que +l'automate vient de lire un $a$, le $05$ signifie qu'il vient de lire +un $b$, le $A$ signifie qu'il a lu deux $a$ consécutifs ou bien deux +$b$ consécutifs. Sur cette description, il est clair que l'automate +accepte les mots contenant deux $a$ consécutifs ou bien deux $b$ +consécutifs. + +(3) L'élimination des états $1$ à $6$ peut se faire dans un ordre +quelconque et conduit à l'automate (à transitions étiquetées par des +expressions rationnelles) suivant : +\begin{center} +%%% begin ex1p2a2 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q0) at (18bp,20.549bp) [draw,circle,state,initial] {$0$}; + \node (q7) at (104bp,20.549bp) [draw,circle,state,final] {$7$}; + \draw [->] (q0) ..controls (47.743bp,20.549bp) and (62.773bp,20.549bp) .. node[auto] {$aa$} (q7); + \draw [->] (q0) ..controls (42.511bp,4.2138bp) and (55.796bp,-1.5495bp) .. (68bp,1.5495bp) .. controls (71.958bp,2.5545bp) and (75.953bp,4.1071bp) .. node[auto,below] {$bb$} (q7); + \draw [->] (q0) to[loop below] node[auto] {$a,b$} (q0); + \draw [->] (q7) to[loop below] node[auto] {$a,b$} (q7); +% +\end{tikzpicture} + +%%% end ex1p2a2 %%% +\end{center} + +Il y a plusieurs flèches entre les mêmes états : quitte à les +remplacer par des disjonctions, on obtient : +\begin{center} +%%% begin ex1p2a3 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$}; + \node (q7) at (119bp,18bp) [draw,circle,state,final] {$7$}; + \draw [->] (q0) ..controls (51.292bp,18bp) and (73.384bp,18bp) .. node[auto] {$aa|bb$} (q7); + \draw [->] (q0) to[loop below] node[auto] {$a|b$} (q0); + \draw [->] (q7) to[loop below] node[auto] {$a|b$} (q7); +% +\end{tikzpicture} + +%%% end ex1p2a3 %%% +\end{center} + +Enfin, on doit éliminer les états $0$ et $7$ eux-mêmes : pour cela, on +ajoute un nouvel état initial qui ne soit la cible d'aucune flèche et +un nouvel état final d'où ne part aucune flèche, +\begin{center} +%%% begin ex1p2a4 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (qi) at (18bp,18bp) [draw,circle,state,initial] {$\phantom{0}$}; + \node (q0) at (97bp,18bp) [draw,circle,state] {$0$}; + \node (q7) at (198bp,18bp) [draw,circle,state] {$7$}; + \node (qf) at (277bp,18bp) [draw,circle,state,final] {$\phantom{7}$}; + \draw [->] (qi) ..controls (45.659bp,18bp) and (57.817bp,18bp) .. node[auto] {$\varepsilon$} (q0); + \draw [->] (q7) ..controls (225.66bp,18bp) and (237.82bp,18bp) .. node[auto] {$\varepsilon$} (qf); + \draw [->] (q0) ..controls (130.29bp,18bp) and (152.38bp,18bp) .. node[auto] {$aa|bb$} (q7); + \draw [->] (q0) to[loop below] node[auto] {$a|b$} (q0); + \draw [->] (q7) to[loop below] node[auto] {$a|b$} (q7); +% +\end{tikzpicture} + +%%% end ex1p2a4 %%% +\end{center} + +Et l'élimination des états $0$ et $7$ dans un ordre quelconque conduit +finalement à l'expression rationnelle $(a|b){*}(aa|bb)(a|b){*}$. +\end{corrige} + +% + +\exercice + +Soit $\Sigma = \{a,b\}$. + +(1) Tracer l'automate de Thompson de l'expression rationnelle +$a{*}(baa{*}){*}$. Cet automate est-il déterministe ? + +(2) En éliminer les transitions spontanées. + +(3) Déterminiser l'automate obtenu (on demande un automate complet). + +(4) Minimiser l'automate obtenu (on demande un automate complet). + +(5) Vérifier le résultat en décrivant en français le langage dénoté +par l'expression rationnelle initiale et reconnu par l'automate +finalement obtenu. + +\begin{corrige} +(1) L'automate de Thompson de $a{*}(baa{*}){*}$ doit comporter $14$ + états puisque cette expression rationnelle contient $7$ symboles + parenthèses non comptées. Il est le suivant (où on a omis les + $\varepsilon$ sur les transitions spontanées) : +\begin{center} +\scalebox{0.34}{% +%%% begin ex3p1 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (97bp,45bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$}; + \node (q3) at (255bp,18bp) [draw,circle,state] {$3$}; + \node (q2) at (176bp,45bp) [draw,circle,state] {$2$}; + \node (q5) at (413bp,48bp) [draw,circle,state] {$5$}; + \node (q4) at (334bp,18bp) [draw,circle,state] {$4$}; + \node (q7) at (571bp,86bp) [draw,circle,state] {$7$}; + \node (q6) at (492bp,86bp) [draw,circle,state] {$6$}; + \node (q9) at (729bp,86bp) [draw,circle,state] {$9$}; + \node (q8) at (650bp,86bp) [draw,circle,state] {$8$}; + \node (q11) at (891.49bp,125bp) [draw,circle,state] {$11$}; + \node (q10) at (809.5bp,125bp) [draw,circle,state] {$10$}; + \node (q13) at (1055.5bp,25bp) [draw,circle,state,final] {$13$}; + \node (q12) at (973.49bp,63bp) [draw,circle,state] {$12$}; + \draw [->] (q0) ..controls (59.7bp,17.371bp) and (103.03bp,16.838bp) .. (140bp,17bp) .. controls (169.56bp,17.13bp) and (203.43bp,17.448bp) .. node[auto] {{}} (q3); + \draw [->] (q12) ..controls (939.5bp,48.432bp) and (914.89bp,40bp) .. (892.49bp,40bp) .. controls (491bp,40bp) and (491bp,40bp) .. (491bp,40bp) .. controls (474.34bp,40bp) and (455.77bp,41.875bp) .. node[auto] {{}} (q5); + \draw [->] (q2) ..controls (203.44bp,35.73bp) and (216.64bp,31.102bp) .. node[auto] {{}} (q3); + \draw [->] (q10) ..controls (835.62bp,135.26bp) and (845.21bp,137.3bp) .. (854bp,136bp) .. controls (856.94bp,135.57bp) and (859.98bp,134.94bp) .. node[auto] {$a$} (q11); + \draw [->] (q7) ..controls (598.66bp,86bp) and (610.82bp,86bp) .. node[auto] {$a$} (q8); + \draw [->] (q9) ..controls (788.12bp,80.488bp) and (892.85bp,70.553bp) .. node[auto] {{}} (q12); + \draw [->] (q8) ..controls (677.66bp,86bp) and (689.82bp,86bp) .. node[auto] {{}} (q9); + \draw [->] (q11) ..controls (915.87bp,107.43bp) and (926.56bp,99.325bp) .. (935.99bp,92bp) .. controls (940.47bp,88.526bp) and (945.22bp,84.783bp) .. node[auto] {{}} (q12); + \draw [->] (q2) ..controls (152.62bp,39.018bp) and (146.07bp,37.685bp) .. (140bp,37bp) .. controls (134.92bp,36.427bp) and (129.53bp,36.741bp) .. node[auto] {{}} (q1); + \draw [->] (q6) ..controls (519.66bp,86bp) and (531.82bp,86bp) .. node[auto] {{}} (q7); + \draw [->] (q12) ..controls (1002.2bp,49.853bp) and (1016.2bp,43.176bp) .. node[auto] {{}} (q13); + \draw [->] (q9) ..controls (756.02bp,98.925bp) and (770.16bp,105.95bp) .. node[auto] {{}} (q10); + \draw [->] (q3) ..controls (282.66bp,18bp) and (294.82bp,18bp) .. node[auto] {{}} (q4); + \draw [->] (q11) ..controls (866.59bp,118.91bp) and (860.06bp,117.66bp) .. (854bp,117bp) .. controls (848.92bp,116.45bp) and (843.55bp,116.73bp) .. node[auto] {{}} (q10); + \draw [->] (q5) ..controls (440.12bp,60.892bp) and (454.27bp,67.873bp) .. node[auto] {$b$} (q6); + \draw [->] (q4) ..controls (366.77bp,7.9414bp) and (390.7bp,2bp) .. (412bp,2bp) .. controls (412bp,2bp) and (412bp,2bp) .. (974.49bp,2bp) .. controls (992.87bp,2bp) and (1012.7bp,7.6737bp) .. node[auto] {{}} (q13); + \draw [->] (q0) ..controls (45.436bp,27.27bp) and (58.635bp,31.898bp) .. node[auto] {{}} (q1); + \draw [->] (q1) ..controls (121.23bp,55.953bp) and (131.02bp,58.496bp) .. (140bp,57bp) .. controls (143.13bp,56.478bp) and (146.36bp,55.711bp) .. node[auto] {$a$} (q2); + \draw [->] (q4) ..controls (361.28bp,28.238bp) and (374.94bp,33.562bp) .. node[auto] {{}} (q5); +% +\end{tikzpicture} + +%%% end ex3p1 %%% +} +\end{center} + +Cet automate n'est pas déterministe : un automate comportant des +ε-transitions est forcément non-déterministe. + +\smallbreak + +(2) Tous les états autres que $0$ (car il est initial) et $2,6,8,11$ +(car des transitions non spontanées y aboutissent) vont disparaître ; +les ε-fermetures $C(q)$ de ces états sont les suivantes : + +\begin{center} +\begin{tabular}{r|l} +$q$&ε-fermeture $C(q)$\\ +\hline +$0$&$\{0,1,3,4,5,13\}$\\ +$2$&$\{1,2,3,4,5,13\}$\\ +$6$&$\{6,7\}$\\ +$8$&$\{5,8,9,10,12,13\}$\\ +$11$&$\{5,10,11,12,13\}$\\ +\end{tabular} +\end{center} + +En remplaçant chaque transition $q^\sharp \to q'$ étiquetée +d'un $x\in\Sigma$ dans l'automate par une transition $q\to q'$ pour +chaque état $q$ tel que $q^\sharp \in C(q)$, on obtient le NFA +suivant : + +\begin{center} +%%% begin ex3p1b %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q0) at (18bp,31.498bp) [draw,circle,state,initial,final,accepting below] {$0$}; + \node (q2) at (97bp,61.498bp) [draw,circle,state,final] {$2$}; + \node (q11) at (335.5bp,19.498bp) [draw,circle,state,final,accepting below] {$11$}; + \node (q8) at (255bp,49.498bp) [draw,circle,state,final,accepting above] {$8$}; + \node (q6) at (176bp,31.498bp) [draw,circle,state] {$6$}; + \draw [->] (q0) ..controls (45.279bp,41.737bp) and (58.943bp,47.06bp) .. node[auto] {$a$} (q2); + \draw [->] (q2) to[loop above] node[auto] {$a$} (q2); + \draw [->] (q8) ..controls (282.44bp,39.394bp) and (295.8bp,34.29bp) .. node[auto] {$a$} (q11); + \draw [->] (q11) to[loop above] node[auto] {$a$} (q11); + \draw [->] (q11) ..controls (297.15bp,8.7001bp) and (264.63bp,2.1768bp) .. (237bp,7.4983bp) .. controls (224.85bp,9.8374bp) and (212.04bp,14.613bp) .. node[auto,near start] {$b$} (q6); + \draw [->] (q0) ..controls (47.643bp,24.415bp) and (64.2bp,20.964bp) .. (79bp,19.498bp) .. controls (94.922bp,17.922bp) and (99.078bp,17.922bp) .. (115bp,19.498bp) .. controls (125.98bp,20.586bp) and (137.94bp,22.768bp) .. node[auto,below] {$b$} (q6); + \draw [->] (q2) ..controls (124.28bp,51.26bp) and (137.94bp,45.936bp) .. node[auto] {$b$} (q6); + \draw [->] (q8) ..controls (234.03bp,34.749bp) and (226.51bp,30.579bp) .. (219bp,28.498bp) .. controls (214.15bp,27.154bp) and (208.87bp,26.751bp) .. node[auto,near start] {$b$} (q6); + \draw [->] (q6) ..controls (198.21bp,42.911bp) and (205.25bp,45.859bp) .. (212bp,47.498bp) .. controls (216.59bp,48.613bp) and (221.55bp,49.292bp) .. node[auto] {$a$} (q8); +% +\end{tikzpicture} + +%%% end ex3p1b %%% +\end{center} + +Les états $0,2,8,11$ sont finaux car ce sont eux qui ont $13$ dans +leur ε-fermeture. + +\smallbreak + +(3) L'automate ainsi obtenu est déjà déterministe incomplet ; pour le +déterminiser-compléter, il n'y a qu'à ajouter un puits $\bot$ avec la +seule transition qui manque, c'est-à-dire une transition étiquetée par +$b$ depuis l'état $6$ (et des transitions de $\bot$ vers lui-même +étiquetées $a$ et $b$). Nous ne représentons pas l'automate à $6$ +états ainsi fabriqué. + +\smallbreak + +(4) On part de l'algorithme déterministe complet obtenu à la +question (3), et on lui applique l'algorithme de minimisation. On +sépare d'abord ses états en deux classes, les finaux $\{0,2,8,11\}$ et +les non-finaux $\{6,\bot\}$. La transition étiquetée $a$ sépare les +états $6$ et $\bot$ car le premier aboutit dans la classe +$\{0,2,8,11\}$ tandis que le second aboutit dans la classe +$\{6,\bot\}$. On vérifie ensuite qu'aucune transition ne sépare des +états. L'automate minimal est donc le suivant : +\begin{center} +%%% begin ex3p1c %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q6) at (97bp,20.28bp) [draw,circle,state] {$6$}; + \node (qbot) at (176bp,20.28bp) [draw,circle,state] {$\bot$}; + \node (qF) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$F$}; + \draw [->] (q6) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp) .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp) .. node[auto] {$a$} (qF); + \draw [->] (q6) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp) .. node[auto] {$b$} (qbot); + \draw [->] (qbot) to[loop above] node[auto] {$a,b$} (qbot); + \draw [->] (qF) to[loop above] node[auto] {$a$} (qF); + \draw [->] (qF) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp) .. node[auto] {$b$} (q6); +% +\end{tikzpicture} + +%%% end ex3p1c %%% +\end{center} +où l'état $F$ représente la classe $0\equiv 2\equiv 8\equiv 11$. + +\smallbreak + +(5) Il s'agit du langage constitué des mots n'ayant jamais deux $b$ +consécutifs ni de $b$ final, +c'est-à-dire des mots dans lesquels chaque $b$ est suivi +d'au moins un $a$ : l'expression rationnelle initiale le présente +comme le langage constitués des mots formés d'un nombre quelconque de +$a$ puis d'un nombre quelconque de répétitions d'un $b$ suivi d'au +moins un $a$. L'automate final interdit les suites de deux $b$ +consécutifs comme ceci : l'état $F$ correspond à la situation où on ne +vient pas de rencontrer un $b$ (=la lettre précédente était un $a$ ou +bien on vient de commencer le mot) et on n'en a jamais rencontré deux, +l'état $6$ à la situation où on vient de rencontrer un $b$ et on n'en +a jamais rencontré deux, et l'état $\bot$ à la situation où on a +rencontré au moins une fois deux $b$ consécutifs. Avec cette +description, il est clair que l'automate fait ce qui était demandé. +\end{corrige} + +% + +\exercice + +Donner plusieurs (au moins trois) expressions rationnelles +équivalentes dénotant le langage reconnu par l'automate suivant sur +l'alphabet $\Sigma = \{a,b\}$ : + +\begin{center} +%%% begin ex3p2 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,initial above,accepting below] {$0$}; + \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$}; + \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp) .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp) .. node[auto] {$b$} (q0); + \draw [->] (q2) to[loop right] node[auto] {$b$} (q2); + \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp) .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp) .. node[auto] {$a$} (q1); + \draw [->] (q0) to[loop left] node[auto] {$a$} (q0); + \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp) .. node[auto] {$b$} (q1); + \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp) .. node[auto] {$a$} (q2); +% +\end{tikzpicture} + + +%%% end ex3p2 %%% +\end{center} +(On pourra considérer les ordres suivants d'élimination des états : +(A) $2,1,0$, ensuite (B) $1,2,0$ et enfin (C) $0,2,1$.) + +\begin{corrige} +(A) Si on commence par éliminer l'état $2$ (en considérant l'automate +comme un automate à transitions étiquetées par des expressions +rationnelles), l'état $1$ reçoit une transition vers lui-même +étiquetée $ab{*}a$. Si on élimine l'état $1$, l'état $0$ reçoit à la +place une transition vers lui-même étiquetée par $b(ab{*}a){*}b$, +qu'on peut fusionner avec la transition vers lui-même déjà existante +étiquetée par $a$ pour une seule étiquetée par $a|b(ab{*}a){*}b$. +Quitte éventuellement à ajouter un nouvel état initial (conduisant à +$0$ par une transition spontanée) et un nouvel état final (vers lequel +$0$ conduit par une transition spontanée) et à éliminer n'état $0$, on +obtient finalement l'expression rationnelle +\[ +(a|b(ab{*}a){*}b){*} +\] + +\smallbreak + +(B) Si on commence par éliminer l'état $1$, il apparaît une transition +$0\to 2$ étiquetée $ba$ et une $2\to 0$ étiquetée $ab$ (si on veut +appliquer l'algorithme de façon puremnet mécanique, l'état $1$ n'a pas +de transition vers lui-même, c'est-à-dire qu'on pourrait l'étiqueter +par $\bot$, symbole d'expression rationnelle qui dénote le lagange +vide, et l'expression rationnelle $\bot{*}$ est équivalente +à $\varepsilon$) ; mais il ne faut pas oublier que l'état $2$ reçoit +lui aussi une transition vers lui-même (en passant par $1$) étiquetée +$aa$, qu'on peut fusionner avec la transition vers lui-même déjà +existante étiquetée par $b$ pour obtenir une transition étiquetée +$b|aa$ ; de même, l'état $0$ reçoit une transition étiquetée $bb$, +qu'on peut fusionner avec celle existante pour obtenir $a|bb$. +L'élimination de l'état $2$ fait alors apparaître une transition de +$0$ vers lui-même étiquetée $ba(b|aa){*}ab$, qu'on peut fusionner avec +la transition vers lui-même déjà étiquetée par $a|bb$ pour une seule +étiquetée par $a|bb|ba(b|aa){*}ab$. On obtient finalement +\[ +(a|bb|ba(b|aa){*}ab){*} +\] +(en particulier, cette expression est équivalente à celle obtenue +précédemment). + +\smallbreak + +(C) Si on préfère commencer par éliminer l'état $0$, il faut au préalable +ajouter un nouvel état initial $I$ (conduisant à $0$ par une +transition spontanée) et un nouvel état final $F$ (vers lequel $0$ +conduit par une transition spontanée). L'élimination de l'état $0$ +fait apparaître une transition de $I$ vers $1$ étiquetée $a{*}b$, une +transition $1$ vers $F$ étiquetée $ba{*}$, et une transition de l'état +$1$ vers lui-même étiquetée $ba{*}b$, et enfin une transition de $I$ +vers $F$ étiquetée $a{*}$. L'élimination de l'état $2$ fait +apparaître une transition de $1$ vers lui-même étiquetée $ab{*}a$, +qu'on peut fusionner avec celle déjà existante étiquetée $ba{*}b$ pour +obtenir une transition $(ab{*}a|ba{*}b)$. Finalement, l'élimination +de l'état $1$ done l'expression rationnelle +\[ +a{*}|a{*}b(ab{*}a|ba{*}b){*}ba{*} +\] +(toujours équivalente aux précédentes). +\end{corrige} + +% + +\exercice + +On considère l'automate fini $M$ sur l'alphabet $\Sigma = \{a,b\}$ +représenté par la figure suivante : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$}; +\node (Y) at (80bp,0bp) [draw,circle,state,final] {$Y$}; +\node (A1) at (-40bp,50bp) [draw,circle,state] {$A\phantom{'}$}; +\node (A2) at (40bp,50bp) [draw,circle,state] {$A'$}; +\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B\phantom{'}$}; +\node (B2) at (40bp,-50bp) [draw,circle,state] {$B'$}; +\draw[->] (X) -- node[auto]{$\varepsilon$} (A1); +\draw[->] (X) -- node[auto,below left]{$\varepsilon$} (B1); +\draw[->] (A1) -- node[auto]{$a$} (A2); +\draw[->] (B1) -- node[auto]{$b$} (B2); +\draw[->] (A1) to[loop above] node[auto]{$b$} (A1); +\draw[->] (A2) to[loop above] node[auto]{$b$} (A2); +\draw[->] (B1) to[loop below] node[auto]{$a$} (B1); +\draw[->] (B2) to[loop below] node[auto]{$a$} (B2); +\draw[->] (A2) -- node[auto]{$\varepsilon$} (Y); +\draw[->] (B2) -- node[auto,below right]{$\varepsilon$} (Y); +\end{tikzpicture} +\end{center} + +(0) De quelle sorte d'automate s'agit-il ? (Autrement dit : est-il +déterministe ou non ? avec transitions spontanées ou non ?) + +(1a) Décrire brièvement, en français, le langage $L$ reconnu +(=accepté) par l'automate $M$, puis donner une expression +rationnelle qui le dénote. (On pourra préférer traiter la question +(1b) d'abord.) + +(1b) Pour chacun des mots suivants, dire s'ils sont dans $L$ ou non : +$\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$. +(Note : il est recommandé de réutiliser ces mots pour vérifier +rapidement les réponses aux questions suivantes et ainsi détecter +d'éventuelles erreurs lors des transformations des automates.) + +(2) Éliminer les transitions spontanées de l'automate $M$. (On +supprimera les états devenus inutiles.) On appellera $M_2$ l'automate +obtenu. + +(3) Déterminiser l'automate $M_2$ obtenu en (2), si nécessaire. (On +demande un automate déterministe complet.) On appellera $M_3$ +l'automate déterminisé. + +Pour simplifier le travail du correcteur, on demande de représenter +$M_3$ de sorte que les transitions étiquetées par $a$ soient, dans la +mesure du possible, horizontales de la gauche vers la droite, et +celles étiquetées par $b$, verticales du haut vers le bas. + +(4) Minimiser l'automate $M_3$ obtenu en (3), si nécessaire +(justifier). + +(5) Donner un automate (de n'importe quelle sorte) qui reconnaît le +langage $\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$. + +(6) Décrire brièvement, en français, ce langage +complémentaire $\overline{L}$. + +(7) (Question bonus, plus longue, à ne traiter qu'en dernier.) +Calculer une expression rationnelle qui dénote ce langage +complémentaire $\overline{L}$. (Ne pas hésiter à introduire des +notations intermédiaires.) + +\begin{corrige} +(0) L'automate $M$ est un automate fini non-déterministe à transitions + spontanées, ou ε-NFA (le concept d'« automate déterministe à + transitions spontanées » n'aurait tout simplement pas de sens). + +\smallbreak + +(1a) Le chemin par les états $X,A,A',Y$ accepte les mots exactement +un $a$, c'est-à-dire le langage dénoté par $b{*}ab{*}$. Le chemin par +les états $X,B,B',Y$ accepte les mots comportant exactement un $b$, +c'est-à-dire le langage dénoté par $a{*}ba{*}$. L'automate $M$ dans +son ensemble accepte les mots comportant exactement un $a$ ou +(inclusif) exactement un $b$ (i.e. $L = \{w\in\Sigma^* : |w|_a = 1 +\penalty0\ \textrm{ou}\penalty0\ |w|_b = 1\}$ si $|w|_x$ désigne le +nombre total d'occurrences de la lettre $x$ dans le mot $w$). C'est +le langage dénoté par l'expression rationnelle $b{*}ab{*} | a{*}ba{*}$ +(nous notons ici et ailleurs $|$ pour la disjonction, qu'on peut aussi +noter $+$). + +(1b) Parmi les mots proposés, $a$, $b$, $ab$ et $aab$ appartiennent à +$L$, tandis que $\varepsilon$, $aa$, $aabb$, $abab$ et $ababa$ n'y +appartiennent pas. + +\smallbreak + +(2) La ε-fermeture (arrière) de l'état $X$ est $\{X,A,B\}$ ; la +ε-fermeture de l'état $A'$ est $\{A',Y\}$ et celle de l'état $B'$ est +$\{B',Y\}$ ; les autres états sont leur propre ε-fermeture (i.e., +celle-ci est un singleton). L'élimination des transitions spontanées +conduit donc à l'automate $M_2$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$}; +\node (A1) at (-40bp,50bp) [draw,circle,state] {$A\phantom{'}$}; +\node (A2) at (40bp,50bp) [draw,circle,state,final] {$A'$}; +\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B\phantom{'}$}; +\node (B2) at (40bp,-50bp) [draw,circle,state,final] {$B'$}; +\draw[->] (X) -- node[auto]{$b$} (A1); +\draw[->] (X) -- node[auto,below left]{$a$} (B1); +\draw[->] (X) -- node[auto,below right]{$a$} (A2); +\draw[->] (X) -- node[auto,above right]{$b$} (B2); +\draw[->] (A1) -- node[auto]{$a$} (A2); +\draw[->] (B1) -- node[auto]{$b$} (B2); +\draw[->] (A1) to[loop above] node[auto]{$b$} (A1); +\draw[->] (A2) to[loop above] node[auto]{$b$} (A2); +\draw[->] (B1) to[loop below] node[auto]{$a$} (B1); +\draw[->] (B2) to[loop below] node[auto]{$a$} (B2); +\end{tikzpicture} +\end{center} +(On a supprimé l'état $Y$ qui est devenu inutile car aucune transition +non-spontanée n'y conduit.) + +\smallbreak + +(3) L'algorithme de déterminisation conduit à l'automate $M_3$ suivant +où, pour plus de lisibilité, les états finaux ont été marqués en les +entourant deux fois plutôt que par une flèche sortante : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$\{X\}$}; +\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$\{A',B\}$}; +\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$\{B\}$}; +\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A,B'\}$}; +\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A',B'\}$}; +\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{B'\}$}; +\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$\{A\}$}; +\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$\{A'\}$}; +\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$\varnothing$}; +\draw[->] (s00) -- node[auto]{$a$} (s01); +\draw[->] (s01) -- node[auto]{$a$} (s02); +\draw[->] (s10) -- node[auto]{$a$} (s11); +\draw[->] (s11) -- node[auto]{$a$} (s12); +\draw[->] (s20) -- node[auto]{$a$} (s21); +\draw[->] (s21) -- node[auto]{$a$} (s22); +\draw[->] (s02) to[loop right] node[auto]{$a$} (s02); +\draw[->] (s12) to[loop right] node[auto]{$a$} (s12); +\draw[->] (s22) to[loop right] node[auto]{$a$} (s22); +\draw[->] (s00) -- node[auto]{$b$} (s10); +\draw[->] (s10) -- node[auto]{$b$} (s20); +\draw[->] (s01) -- node[auto]{$b$} (s11); +\draw[->] (s11) -- node[auto]{$b$} (s21); +\draw[->] (s02) -- node[auto]{$b$} (s12); +\draw[->] (s12) -- node[auto]{$b$} (s22); +\draw[->] (s20) to[loop below] node[auto]{$b$} (s20); +\draw[->] (s21) to[loop below] node[auto]{$b$} (s21); +\draw[->] (s22) to[loop below] node[auto]{$b$} (s22); +\end{tikzpicture} +\end{center} + +Pour la commodité de la suite de la correction, on renomme les états +de cet automate $M_3$ de la façon suivante : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$}; +\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$01$}; +\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$02$}; +\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$10$}; +\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$11$}; +\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$12$}; +\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$20$}; +\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$21$}; +\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$22$}; +\draw[->] (s00) -- node[auto]{$a$} (s01); +\draw[->] (s01) -- node[auto]{$a$} (s02); +\draw[->] (s10) -- node[auto]{$a$} (s11); +\draw[->] (s11) -- node[auto]{$a$} (s12); +\draw[->] (s20) -- node[auto]{$a$} (s21); +\draw[->] (s21) -- node[auto]{$a$} (s22); +\draw[->] (s02) to[loop right] node[auto]{$a$} (s02); +\draw[->] (s12) to[loop right] node[auto]{$a$} (s12); +\draw[->] (s22) to[loop right] node[auto]{$a$} (s22); +\draw[->] (s00) -- node[auto]{$b$} (s10); +\draw[->] (s10) -- node[auto]{$b$} (s20); +\draw[->] (s01) -- node[auto]{$b$} (s11); +\draw[->] (s11) -- node[auto]{$b$} (s21); +\draw[->] (s02) -- node[auto]{$b$} (s12); +\draw[->] (s12) -- node[auto]{$b$} (s22); +\draw[->] (s20) to[loop below] node[auto]{$b$} (s20); +\draw[->] (s21) to[loop below] node[auto]{$b$} (s21); +\draw[->] (s22) to[loop below] node[auto]{$b$} (s22); +\end{tikzpicture} +\end{center} +Ici, l'état $0\bullet$ signifie que l'automate n'a pas rencontré +de $a$, l'état $1\bullet$ qu'il en a rencontré exactement un, et +l'état $2\bullet$ qu'il en a rencontré au moins deux ; les états +$\bullet0$, $\bullet1$ et $\bullet2$ ont la même signification pour la +lettre $b$. + +\smallbreak + +(4) L'automate $M_3$ est déjà minimal. En effet, l'algorithme de +minimisation commence par séparer les classes $\{01,10,11,12,21\}$ +(états finaux) et $\{00,02,20,22\}$ (états non-finaux) ; ensuite, la +transition étiquetée par $a$ sépare la classe $\{01,10,11,12,21\}$ en +$\{01,21\}$ (qui vont vers un état non-final) et $\{10,11,12\}$ (qui +vont vers un état final), et la classe $\{00,02,20,22\}$ en +$\{00,20\}$ (qui vont vers un état final) et $\{02,22\}$ (qui vont +vers un non-final). La transition étiquetée par $b$ sépare ensuite en +deux chacune des trois classes $\{00,20\}$, $\{01,21\}$ et $\{02,22\}$ +(car le premier élément va dans la classe $\{10,11,12\}$ tandis que le +second reste dans la même classe) et sépare en trois la classe +$\{10,11,12\}$. On a donc séparé chacun des états. + +\smallbreak + +(5) Pour reconnaître le complémentaire du langage reconnu par un +automate fini déterministe complet, il suffit d'échanger états finaux +et non-finaux : on peut donc prendre l'automate dessiné en (3) avec, +cette fois, la convention que les états simplement entourés sont +finaux (et les doublement entourés sont non-finaux). +Appelons-le $M_5$. + +\emph{Attention :} échanger états finaux et non-finaux ne marche pas +pour reconnaître le complémentaire du langage reconnu par un automate +non-déterministe ou incomplet (car la négation de « il existe un +chemin qui va vers un état final » est « aucun chemin ne va vers un +état final » et pas « il existe un chemin qui va vers un état +non-final »). + +\smallbreak + +(6) Puisque $L$ est le langage formé des mots comportant exactement un +$a$ ou (inclusif) exactement un $b$, son complémentaire $\overline{L}$ +est formé des mots ayant un nombre différent de $1$ de $a$ \emph{et} +un nombre différent de $1$ de $b$ ; si on préfère, il s'agit du +langage comportant ($0$ ou au moins $2$ fois la lettre $a$) \emph{et} +($0$ ou au moins $2$ fois la lettre $b$). + +\smallbreak + +(7) L'élimination des états n'est pas trop complexe car l'automate +$M_5$ a très peu de boucles. Éliminons simultanément tous les états +non-finaux ($01$, $10$, $11$, $12$ et $21$), et profitons-en pour +créer un nouvel (et unique) état final $F$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$}; +\node (s02) at (100bp,0bp) [draw,rounded corners,state] {$02$}; +\node (s20) at (0bp,-60bp) [draw,rounded corners,state] {$20$}; +\node (s22) at (100bp,-60bp) [draw,rounded corners,state] {$22$}; +\node (F) at (160bp,-60bp) [draw,circle,state,final] {$F$}; +\draw[->] (s00) -- node[auto]{$aa$} (s02); +\draw[->] (s20) -- node[auto]{$ab{*}a$} (s22); +\draw[->] (s02) to[loop above] node[auto]{$a$} (s02); +\draw[->] (s00) -- node[auto]{$bb$} (s20); +\draw[->] (s02) -- node[auto]{$ba{*}b$} (s22); +\draw[->] (s20) to[loop left] node[auto]{$b$} (s20); +\draw[->] (s22) to[loop below] node[auto]{$a|b$} (s22); +\draw[->] (s22) -- node[auto]{$\varepsilon$} (F); +\draw[->] (s00) -- node[auto]{$r$} (s22); +\draw[->,out=0,in=90] (s02) to node[auto]{$\varepsilon$} (F); +\draw[->,out=270,in=270] (s20) to node[auto,below]{$\varepsilon$} (F); +\draw[->] (s00) to[out=45,in=180] (100bp,40bp) to[out=0,in=45] node[auto,above]{$\varepsilon$} (F); +\end{tikzpicture} +\end{center} +où $r := abaa{*}b \,|\, abbb{*}a \,|\, baaa{*}b \,|\, babb{*}a$ +(correspondant aux quatre façons de passer de $00$ à $22$ dans le +graphe ci-dessus). Éliminons l'état $02$ et l'état $20$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$}; +\node (s22) at (100bp,-60bp) [draw,rounded corners,state] {$22$}; +\node (F) at (160bp,-60bp) [draw,circle,state,final] {$F$}; +\draw[->] (s22) -- node[auto]{$\varepsilon$} (F); +\draw[->] (s22) to[loop above] node[auto]{$a|b$} (s22); +\draw[->] (s00) -- node[auto]{$r'$} (s22); +\draw[->,out=0,in=90] (s00) to node[auto]{$\varepsilon|aaa{*}|bbb{*}$} (F); +\end{tikzpicture} +\end{center} +où $r' := r \penalty0\,|\, aaa{*}ba{*}b \penalty0\,|\, bbb{*}ab{*}a = +abaa{*}b \penalty0\,|\, abbb{*}a \penalty0\,|\, baaa{*}b +\penalty0\,|\, babb{*}a \penalty0\,|\, aaa{*}ba{*}b \penalty0\,|\, +bbb{*}ab{*}a$. On obtient finalement l'expression rationnelle +suivante pour $\overline{L}$ : +\[ +\varepsilon\,|\,aaa{*}\,|\,bbb{*}\,|\,(abaa{*}b \,|\, +abbb{*}a \,|\, baaa{*}b \,|\, babb{*}a +\,|\, aaa{*}ba{*}b \,|\, bbb{*}ab{*}a)(a|b){*} +\] +Pour comprendre cette expression rationnelle, la disjonction de plus +haut niveau correspond aux quatre possibilités : (i) $0$ fois la +lettre $a$ et $0$ fois la lettre $b$, (ii) au moins $2$ fois la lettre +$a$ et $0$ fois la lettre $b$, (iii) $0$ fois la lettre $a$ et au +moins $2$ fois la lettre $b$, et (iv) au moins $2$ fois la lettre $a$ +et au moins $2$ fois la lettre $b$. Pour mieux comprendre +l'expression du cas (iv), on peut remarquer que $abaa{*}b +\penalty0\,|\, baaa{*}b \penalty0\,|\, aaa{*}ba{*}b$ dénote le langage +formé des mots comportant au moins deux $a$ et exactement deux $b$ et +qui finissent par un $b$, et symétriquement $abbb{*}a \penalty0\,|\, +babb{*}a \penalty0\,|\,bbb{*}ab{*}a$ dénote le langage formé des mots +comportant au moins deux $b$ et exactement deux $a$ et qui finissent +par un $a$ : l'expression du cas (iv) correspond donc à écrire un mot +ayant au moins deux $a$ et au moins deux $b$ comme le premier préfixe +qui vérifie cette propriété suivi d'un suffixe quelconque. (On +pouvait utiliser directement ce raisonnement pour produire +l'expression.) +\end{corrige} + +% +% +% + +\subsection{Langages algébriques et grammaires hors contexte} + +\exercice + +Considérons le fragment simplifié suivant de la grammaire d'un langage +de programmation hypothétique : +\[ +\begin{aligned} +\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{Conditional}\\ +|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\ +\mathit{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\ \mathtt{else}\ \mathit{Instruction}\\ +|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\ +\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\ +\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\ +\end{aligned} +\] +(Ici, les « lettres » ou tokens ont été écrits comme des mots, par +exemple $\mathtt{foo}$ est une « lettre » : les terminaux sont écrits +en police à espacement fixe tandis que les nonterminaux sont en +italique et commencent par une majuscule. On prendra +$\mathit{Instruction}$ pour axiome.) + +(1) Donner l'arbre d'analyse de : +$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{else}\penalty0\ \mathtt{qux}$ ; +expliquer brièvement pourquoi il n'y en a qu'un. + +(2) Donner deux arbres d'analyse distincts de : +$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}$. +Que peut-on dire de la grammaire présentée ? + +(3) En supposant que, dans ce langage, +$\mathtt{begin}\penalty0\ I\penalty0\ \penalty0\mathtt{end}$ (où $I$ +est une instruction) a le même effet que $I$ seul, comment un +programmeur peut-il réécrire l'instruction considérée en (2) pour +obtenir un comportant équivalent à l'une ou l'autre des deux +interprétations ? + +(4) Modifier légèrement la grammaire proposée de manière à obtenir une +grammaire faiblement équivalente dans laquelle seul l'un des arbres +d'analyse obtenus en (2) est possible (i.e., une grammaire qui force +cette interprétation-là par défaut) ; on pourra être amené à +introduire des nouveaux nonterminaux pour des variantes de +$\mathit{Instruction}$ et $\mathit{Conditional}$ qui interdisent +récursivement les conditionnelles sans $\mathtt{else}$. + +\begin{corrige} +(1) L'arbre d'analyse de + $\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{else}\penalty0\ \mathtt{qux}$ + est le suivant (en notant $I$, $C$ et $E$ pour + $\mathit{Instruction}$, $\mathit{Condition}$ et + $\mathit{Expression}$ respectivement) : +\begin{center} +\tikzstyle{automaton}=[scale=0.4] +%%% begin ex2p1 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (foo) at (279bp,18bp) [draw,draw=none] {$\mathtt{foo}$}; + \node (then1) at (207bp,90bp) [draw,draw=none] {$\mathtt{then}$}; + \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$}; + \node (if1) at (63bp,90bp) [draw,draw=none] {$\mathtt{if}$}; + \node (bar) at (423bp,18bp) [draw,draw=none] {$\mathtt{bar}$}; + \node (I1) at (243bp,234bp) [draw,draw=none] {$I$}; + \node (I0) at (207bp,378bp) [draw,draw=none] {$I$}; + \node (I3) at (423bp,90bp) [draw,draw=none] {$I$}; + \node (I2) at (279bp,90bp) [draw,draw=none] {$I$}; + \node (I4) at (387bp,234bp) [draw,draw=none] {$I$}; + \node (trippy) at (135bp,18bp) [draw,draw=none] {$\mathtt{trippy}$}; + \node (else0) at (315bp,234bp) [draw,draw=none] {$\mathtt{else}$}; + \node (else1) at (351bp,90bp) [draw,draw=none] {$\mathtt{else}$}; + \node (qux) at (387bp,162bp) [draw,draw=none] {$\mathtt{qux}$}; + \node (C1) at (243bp,162bp) [draw,draw=none] {$C$}; + \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$}; + \node (C0) at (207bp,306bp) [draw,draw=none] {$C$}; + \node (E1) at (135bp,90bp) [draw,draw=none] {$E$}; + \node (E0) at (99bp,234bp) [draw,draw=none] {$E$}; + \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$}; + \draw [] (I2) ..controls (279bp,60.846bp) and (279bp,46.917bp) .. (foo); + \draw [] (C0) ..controls (192.52bp,276.85bp) and (185.36bp,262.92bp) .. (then0); + \draw [] (I0) ..controls (207bp,348.85bp) and (207bp,334.92bp) .. (C0); + \draw [] (C0) ..controls (250.16bp,277.03bp) and (271.72bp,263.05bp) .. (else0); + \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp) .. (else1); + \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp) .. (I2); + \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp) .. (happy); + \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp) .. (E1); + \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp) .. (then1); + \draw [] (C0) ..controls (263.23bp,285.79bp) and (310.83bp,268.84bp) .. (351bp,252bp) .. controls (353.93bp,250.77bp) and (356.97bp,249.43bp) .. (I4); + \draw [] (C1) ..controls (186.77bp,141.79bp) and (139.17bp,124.84bp) .. (99bp,108bp) .. controls (96.068bp,106.77bp) and (93.027bp,105.43bp) .. (if1); + \draw [] (C0) ..controls (150.77bp,285.79bp) and (103.17bp,268.84bp) .. (63bp,252bp) .. controls (60.068bp,250.77bp) and (57.027bp,249.43bp) .. (if0); + \draw [] (E1) ..controls (135bp,60.846bp) and (135bp,46.917bp) .. (trippy); + \draw [] (C1) ..controls (299.23bp,141.79bp) and (346.83bp,124.84bp) .. (387bp,108bp) .. controls (389.93bp,106.77bp) and (392.97bp,105.43bp) .. (I3); + \draw [] (C0) ..controls (221.48bp,276.85bp) and (228.64bp,262.92bp) .. (I1); + \draw [] (I4) ..controls (387bp,204.85bp) and (387bp,190.92bp) .. (qux); + \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp) .. (C1); + \draw [] (I3) ..controls (423bp,60.846bp) and (423bp,46.917bp) .. (bar); + \draw [] (C0) ..controls (163.84bp,277.03bp) and (142.28bp,263.05bp) .. (E0); +% +\end{tikzpicture} + +%%% end ex2p1 %%% +\end{center} + +Il est le seul possible car une fois acquis que les deux $\mathtt{if}$ +comportent chacun un $\mathtt{else}$, il se construit ensuite en +descendant de façon unique (l'instruction est forcément une condition, +qui s'analyse en $\mathtt{if}\ E\ \mathtt{then}\ I\ \mathtt{else}\ I$ +de façon unique, et chacun des morceaux s'analyse de nouveau de façon +unique). + +\vskip .5explus.1fil + +(2) Un arbre d'analyse possible consiste à associer le +$\mathtt{else}\penalty0\ \mathtt{bar}$ avec +$\mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}$ : +\begin{center} +\tikzstyle{automaton}=[scale=0.4] +%%% begin ex2p1a %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (bar) at (423bp,18bp) [draw,draw=none] {$\mathtt{bar}$}; + \node (then1) at (207bp,90bp) [draw,draw=none] {$\mathtt{then}$}; + \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$}; + \node (if1) at (63bp,90bp) [draw,draw=none] {$\mathtt{if}$}; + \node (I1) at (243bp,234bp) [draw,draw=none] {$I$}; + \node (I0) at (135bp,378bp) [draw,draw=none] {$I$}; + \node (I3) at (423bp,90bp) [draw,draw=none] {$I$}; + \node (I2) at (279bp,90bp) [draw,draw=none] {$I$}; + \node (trippy) at (135bp,18bp) [draw,draw=none] {$\mathtt{trippy}$}; + \node (else1) at (351bp,90bp) [draw,draw=none] {$\mathtt{else}$}; + \node (foo) at (279bp,18bp) [draw,draw=none] {$\mathtt{foo}$}; + \node (C1) at (243bp,162bp) [draw,draw=none] {$C$}; + \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$}; + \node (C0) at (135bp,306bp) [draw,draw=none] {$C$}; + \node (E1) at (135bp,90bp) [draw,draw=none] {$E$}; + \node (E0) at (99bp,234bp) [draw,draw=none] {$E$}; + \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$}; + \draw [] (I2) ..controls (279bp,60.846bp) and (279bp,46.917bp) .. (foo); + \draw [] (C0) ..controls (149.48bp,276.85bp) and (156.64bp,262.92bp) .. (then0); + \draw [] (I0) ..controls (135bp,348.85bp) and (135bp,334.92bp) .. (C0); + \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp) .. (then1); + \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp) .. (else1); + \draw [] (I3) ..controls (423bp,60.846bp) and (423bp,46.917bp) .. (bar); + \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp) .. (happy); + \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp) .. (E1); + \draw [] (C1) ..controls (186.77bp,141.79bp) and (139.17bp,124.84bp) .. (99bp,108bp) .. controls (96.068bp,106.77bp) and (93.027bp,105.43bp) .. (if1); + \draw [] (C0) ..controls (91.844bp,277.03bp) and (70.277bp,263.05bp) .. (if0); + \draw [] (E1) ..controls (135bp,60.846bp) and (135bp,46.917bp) .. (trippy); + \draw [] (C1) ..controls (299.23bp,141.79bp) and (346.83bp,124.84bp) .. (387bp,108bp) .. controls (389.93bp,106.77bp) and (392.97bp,105.43bp) .. (I3); + \draw [] (C0) ..controls (178.16bp,277.03bp) and (199.72bp,263.05bp) .. (I1); + \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp) .. (I2); + \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp) .. (C1); + \draw [] (C0) ..controls (120.52bp,276.85bp) and (113.36bp,262.92bp) .. (E0); +% +\end{tikzpicture} + +%%% end ex2p1a %%% +\end{center} +un autre consiste à associer le $\mathtt{else}\penalty0\ \mathtt{bar}$ +avec +$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ ...$ : +\begin{center} +\tikzstyle{automaton}=[scale=0.4] +%%% begin ex2p1b %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (bar) at (387bp,162bp) [draw,draw=none] {$\mathtt{bar}$}; + \node (then1) at (279bp,90bp) [draw,draw=none] {$\mathtt{then}$}; + \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$}; + \node (if1) at (135bp,90bp) [draw,draw=none] {$\mathtt{if}$}; + \node (I1) at (243bp,234bp) [draw,draw=none] {$I$}; + \node (I0) at (207bp,378bp) [draw,draw=none] {$I$}; + \node (I2) at (351bp,90bp) [draw,draw=none] {$I$}; + \node (I4) at (387bp,234bp) [draw,draw=none] {$I$}; + \node (trippy) at (207bp,18bp) [draw,draw=none] {$\mathtt{trippy}$}; + \node (else0) at (315bp,234bp) [draw,draw=none] {$\mathtt{else}$}; + \node (foo) at (351bp,18bp) [draw,draw=none] {$\mathtt{foo}$}; + \node (C1) at (243bp,162bp) [draw,draw=none] {$C$}; + \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$}; + \node (C0) at (207bp,306bp) [draw,draw=none] {$C$}; + \node (E1) at (207bp,90bp) [draw,draw=none] {$E$}; + \node (E0) at (99bp,234bp) [draw,draw=none] {$E$}; + \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$}; + \draw [] (I2) ..controls (351bp,60.846bp) and (351bp,46.917bp) .. (foo); + \draw [] (C0) ..controls (192.52bp,276.85bp) and (185.36bp,262.92bp) .. (then0); + \draw [] (I0) ..controls (207bp,348.85bp) and (207bp,334.92bp) .. (C0); + \draw [] (C0) ..controls (250.16bp,277.03bp) and (271.72bp,263.05bp) .. (else0); + \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp) .. (I2); + \draw [] (I4) ..controls (387bp,204.85bp) and (387bp,190.92bp) .. (bar); + \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp) .. (happy); + \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp) .. (E1); + \draw [] (C0) ..controls (263.23bp,285.79bp) and (310.83bp,268.84bp) .. (351bp,252bp) .. controls (353.93bp,250.77bp) and (356.97bp,249.43bp) .. (I4); + \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp) .. (if1); + \draw [] (C0) ..controls (150.77bp,285.79bp) and (103.17bp,268.84bp) .. (63bp,252bp) .. controls (60.068bp,250.77bp) and (57.027bp,249.43bp) .. (if0); + \draw [] (E1) ..controls (207bp,60.846bp) and (207bp,46.917bp) .. (trippy); + \draw [] (C0) ..controls (221.48bp,276.85bp) and (228.64bp,262.92bp) .. (I1); + \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp) .. (then1); + \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp) .. (C1); + \draw [] (C0) ..controls (163.84bp,277.03bp) and (142.28bp,263.05bp) .. (E0); +% +\end{tikzpicture} + +%%% end ex2p1b %%% +\end{center} +La grammaire présentée est donc ambiguë. + +\vskip .5explus.1fil + +(3) Pour forcer la première interprétation (le +$\mathtt{else}\penalty0\ \mathtt{bar}$ se rapporte au +$\mathtt{if}\penalty0\ \mathtt{trippy}$), on peut écrire : +$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{begin}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{end}$. + +Pour forcer la seconde interprétation (le +$\mathtt{else}\penalty0\ \mathtt{bar}$ se rapporte au +$\mathtt{if}\penalty0\ \mathtt{happy}$), on peut écrire : +$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{begin}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{end}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}$. + +\vskip .5explus.1fil + +(4) Pour forcer la première interprétation (le $\mathtt{else}$ se +rapporte au $\mathtt{if}$ le plus proche possible), on peut modifier +la grammaire comme suit : +\[ +\begin{aligned} +\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{Conditional}\\ +|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\ +\mathit{InstrNoSC} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{CondNoSC}\\ +|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\ +\mathit{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{Instruction}\\ +|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\ +\mathit{CondNoSC} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{InstrNoSC}\\ +\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\ +\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\ +\end{aligned} +\] +L'idée est d'obliger une instruction conditionnelle qui apparaîtrait +après le $\mathtt{then}$ d'une conditionnelle complète à être +elle-même complète (elle ne peut pas être courte, car alors le +$\mathtt{else}$ devrait se rattacher à elle), et ce, récursivement. +On peut montrer que la grammaire ci-dessus est inambiguë et faiblement +équivalente à celle de départ. + +On peut aussi fabriquer une grammaire inambiguë, faiblement +équivalente à celle de départ, qui force l'autre interprétation (le +$\mathtt{else}$ se rapporte au $\mathtt{if}$ le plus lointain +possible), mais c'est nettement plus complexe (l'idée générale pour +apparier un $\mathtt{else}$ avec un $\mathtt{if}...\mathtt{else}$ dans +cette logique est de demander que \emph{soit} le $\mathtt{else}$ n'est +suivi d'aucun autre $\mathtt{else}$, \emph{soit} toute instruction +conditionnelle entre le $\mathtt{then}$ et le $\mathtt{else}$ est +elle-même complète). Contrairement à la grammaire précédente, cette +grammaire, bien qu'inambiguë, est probablement impossible à analyser +avec un analyseur LR (ou même, déterministe). +\end{corrige} + + +% + +\exercice\label{non-square-words-is-algebraic} + +Soit $\Sigma = \{a,b\}$. On considère le langage $M$ des mots qui +\emph{ne s'écrivent pas} sous la forme $ww$ avec $w\in\Sigma^*$ +(c'est-à-dire sous la forme d'un carré ; autrement dit, le langage $M$ +est le \emph{complémentaire} du langage $Q$ des carrés considéré dans +l'exercice \ref{square-words-not-algebraic}) : par exemple, $M$ +contient les mots $a$, $b$, $ab$, $aab$ et $aabb$ mais pas +$\varepsilon$, $aa$, $abab$ ni $abaaba$. + +(0) Expliquer pourquoi tout mot sur $\Sigma$ de longueur impaire est +dans $M$, et pourquoi un mot $x_1\cdots x_{2n}$ de longueur paire $2n$ +est dans $M$ si et seulement si il existe $i$ tel que $x_i \neq +x_{n+i}$. + +On considère par ailleurs la grammaire hors contexte $G$ +(d'axiome $S$) +\[ +\begin{aligned} +S &\rightarrow A \;|\; B \;|\; AB \;|\; BA\\ +A &\rightarrow a \;|\; aAa \;|\; aAb \;|\; bAa \;|\; bAb\\ +B &\rightarrow b \;|\; aBa \;|\; aBb \;|\; bBa \;|\; bBb\\ +\end{aligned} +\] + +(1) Décrire le langage $L(G,A)$ des mots dérivant de $A$ dans la +grammaire $G$ (autrement dit, le langage engendré par la grammaire +identique à $G$ mais ayant pour axiome $A$). Décrire de même +$L(G,B)$. + +(2) Montrer que tout mot de longueur impaire est dans le +langage $L(G)$ engendré par $G$. + +(3) Montrer que tout mot $t \in M$ de longueur paire est dans $L(G)$. +(Indication : si $t = x_1\cdots x_{2n}$ est de longueur paire $2n$ et +que $x_i \neq x_{n+i}$, on peut considérer la factorisation de $t$ en +$x_1\cdots x_{2i-1}$ et $x_{2i}\cdots x_{2n}$.) + +(4) Montrer que tout mot de $L(G)$ de longueur paire est dans $M$. + +(5) En déduire que $M$ est algébrique. + +\begin{corrige} +(0) En remarquant que si $n = |w|$ alors $|ww| = 2n$, on constate que + tout mot de la forme $ww$ est de longueur paire, et de plus, que + pour un mot de longueur $2n$, être de la forme $ww$ signifie que son + préfixe de longueur $n$ soit égal à son suffixe de longueur $n$ ; + c'est-à-dire, si $t = x_1\cdots x_{2n}$, que $x_1\cdots x_n = + x_{n+1}\cdots x_{2n}$, ce qui signifie exactement $x_i = x_{n+i}$ + pour tout $1\leq i\leq n$. + +(1) La règle $A \rightarrow a \,|\, aAa \,|\, aAb \,|\, bAa \,|\, bAb$ + permet de faire à partir de $A$ une dérivation qui ajoute un nombre + quelconque de fois une lettre ($a$ ou $b$) de chaque part de $A$, et + finalement remplace ce $A$ par $a$. On obtient donc ainsi + exactement les mots de longueur impaire ayant un $a$ comme lettre + centrale : $L(G,A) = \{w_1aw_2 : |w_1|=|w_2|\}$. De même, $L(G,B) = + \{w_1bw_2 : |w_1|=|w_2|\}$. + +(2) Tout mot de longueur impaire est soit dans $L(G,A)$ soit dans + $L(G,B)$ selon que sa lettre centrale est un $a$ ou un $b$. Il est + donc dans $L(G)$ en vertu des règles $S\rightarrow A$ et + $S\rightarrow B$. + +(3) Soit $t = x_1\cdots x_{2n}$ un mot de $M$ de longueur paire $2n$ : + d'après (0), il existe $i$ tel que $x_i \neq x_{n+i}$. Posons alors + $u = x_1\cdots x_{2i-1}$ et $v = x_{2i}\cdots x_{2n}$. Chacun de + $u$ et de $v$ est de longueur impaire. De plus, leurs lettres + centrales sont respectivement $x_i$ et $x_{n+i}$, et elles sont + différentes : l'une est donc un $a$ et l'autre un $b$ ; mettons sans + perte de généralité que $x_i = a$ et $x_{n+i} = b$. Alors $u \in + L(G,A)$ d'après (1) et $v \in L(G,B)$ : le mot $t = uv$ s'obtient + donc par la règle $S \rightarrow AB$ (suivie de dérivations de $u$ à + partir de $A$ et de $v$ a partir de $B$) : ceci montre bien $t \in + L(G)$. + +(4) On a vu en (1) que tout mot dérivant de $A$ ou de $B$ est de + longueur impaire. Un mot $t$ de $L(G)$ de longueur paire $2n$ + dérive donc forcément de $AB$ ou de $BA$. Sans perte de généralité, + supposons qu'il dérive de $AB$, et on veut montrer qu'il appartient + à $M$. Appelons $u$ le facteur de $t$ qui dérive de $A$ et $v$ le + facteur de $t$ qui dérive de $B$ : on sait alors (toujours + d'après (1)) que $u$ s'écrit sous la forme $x_1\cdots x_{2i-1}$ où + la lettre centrale $x_i$ vaut $a$, et que $v$ s'écrit sous la forme + (quitte à continuer la numérotation des indices) $x_{2i}\cdots + x_{2n}$ où la lettre centrale $x_{n+i}$ vaut $b$. Alors $x_{n+i} + \neq x_i$ donc le mot $t$ est dans $M$ d'après (0). + +(5) On a $M = L(G)$ car d'après les questions précédentes, tout mot de + longueur impaire est dans les deux et qu'un mot de longueur paire + est dans l'un si et seulement si il est dans l'autre. On a donc + montré que $M$ est algébrique. +\end{corrige} + + +% + +\exercice\label{square-words-not-algebraic} + +Soit $\Sigma = \{a,b\}$. Montrer que le langage $Q := \{ww : +w\in\Sigma^*\}$ constitué des mots de la forme $ww$ (autrement dit, +des carrés ; par exemple, $\varepsilon$, $aa$, $abab$, $abaaba$ ou +encore $aabbaabb$ sont dans $Q$) n'est pas algébrique. On pourra pour +cela considérer son intersection avec le langage $L_0$ dénoté par +l'expression rationnelle $a{*}b{*}a{*}b{*}$ et appliquer le lemme de +pompage. + +\begin{corrige} +Supposons par l'absurde que $Q$ soit algébrique : alors son +intersection avec le langage rationnel $L_0 = \{a^m b^n a^{m'} b^{n'} : +m,n,m',n' \in \mathbb{N}\}$ est encore algébrique. Or $Q \cap L_0 = +\{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$. On va maintenant utiliser +le lemme de pompage pour arriver à une contradiction. + +Appliquons le lemme de pompage pour les langages algébriques au +langage $Q \cap L_0 = \{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$ +considéré : appelons $k$ l'entier dont le lemme de pompage garantit +l'existence. Considérons le mot $t := a^k b^k a^k b^k$ : dans la +suite de cette démonstration, on appellera « bloc » de $t$ un des +quatre facteurs $a^k$, $b^k$, $a^k$ et $b^k$. D'après la propriété de +$k$ garantie par le lemme de pompage, il doit exister une +factorisation $t = uvwxy$ pour laquelle on a (i) $|vx|\geq 1$, +(ii) $|vwx|\leq k$ et (iii) $uv^iwx^iy \in Q \cap L_0$ pour +tout $i\geq 0$. + +Chacun de $v$ et de $x$ doit être contenu dans un seul bloc, i.e., +doit être de la forme $a^\ell$ ou $b^\ell$, sinon sa répétition ($v^i$ +ou $x^i$ pour $i\geq 2$, qui appartient à $L_0$ d'après (iii)) ferait +apparaître plus d'alternations entre $a$ et $b$ que le langage $L_0$ +ne le permet. Par ailleurs, la propriété (ii) assure que le facteur +$vwx$ ne peut rencontrer qu'un ou deux blocs de $t$ (pas plus). +Autrement dit, $v$ et $x$ sont contenus dans deux blocs de $t$ qui +sont identiques ou bien consécutifs\footnote{La formulation est + choisie pour avoir un sens même si $v$ ou $x$ est le mot vide (ce + qui est possible \textit{a priori}).}. + +D'après la propriété (i), au moins l'un de $v$ et de $x$ n'est pas le +mot vide. Si ce facteur non trivial est dans le premier bloc $a^k$, +l'autre ne peut pas être dans l'autre bloc $a^k$ d'après ce qui vient +d'être dit : donc $uv^iwx^iy$ est de la forme $a^{k'} b^n a^k b^k$ +avec $k'>k$ si $i>1$, qui n'appartient pas à $Q\cap L_0$, une +contradiction. De même, le facteur non trivial est dans le premier +bloc $b^k$, l'autre ne peut pas être dans l'autre bloc $b^k$ : donc +$uv^iwx^iy$ est de la forme $a^m b^{k'} a^{m'} b^k$ avec $k'>k$ si +$i>1$, qui n'appartient pas à $Q\cap L_0$, de nouveau une +contradiction. Les deux autres cas sont analogues. +\end{corrige} + +\textbf{Remarque :} Les exercices \ref{non-square-words-is-algebraic} +et \ref{square-words-not-algebraic} mis ensemble donnent un exemple +explicite d'un langage $M$ algébrique dont le complémentaire $Q$ n'est +pas algébrique. + +% + +\exercice + +On considère la grammaire hors contexte $G$ suivante (d'axiome $S$) +sur l'alphabet $\Sigma = \{a,b\}$ : +\[ +S \rightarrow aSS \;|\; b +\] +Soit $L = L(G)$ le langage algébrique qu'elle engendre. + +(0) Donner quelques exemples de mots dans $L$. + +(1) Expliquer pourquoi un $w\in \Sigma^*$ appartient à $L$ si et +seulement si : soit $w = b$, soit il existe $u,v\in L$ tels que $w = +auv$. + +(2) En déduire par récurrence sur la longueur $|w|$ de $w$ que si $w +\in L$ alors on a $wz \not\in L$ pour tout $z \in \Sigma^+$ +(c'est-à-dire $z \in \Sigma^*$ et $z \neq \varepsilon$). Autrement +dit : en ajoutant des lettres à la fin d'un mot de $L$ on obtient un +mot qui n'appartient jamais à $L$. (Indication : si on a $auvz = +au'v'$ on pourra considérer les cas (i) $|u'|>|u|$, (ii) $|u'|<|u|$ et +(iii) $|u'|=|u|$.) + +(3) En déduire que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$ +et $v=v'$. (Indication analogue.) + +(4) En déduire que $G$ est inambiguë, c'est-à-dire que chaque mot +$w\in L$ a un unique arbre d'analyse pour $G$ (on pourra reprendre +l'analyse de la question (1) et procéder de nouveau par récurrence +sur $|w|$). + +(5) En s'inspirant des questions précédentes, décrire un algorithme +simple (en une seule fonction récursive) qui, donné un mot +$w\in\Sigma^*$ renvoie la longueur du préfixe de $w$ appartenant à $L$ +s'il existe (il est alors unique d'après la question (2)) ou bien +« échec » s'il n'existe pas ; expliquer comment s'en servir pour +décider si $w\in L$ (i.e., écrire une fonction qui répond vrai ou faux +selon que $w\in L$ ou $w\not\in L$). + +\begin{corrige} +(0) Quelques exemples de mots dans $L$ sont $b$, $abb$, $aabbb$, + $ababb$ ou encore $aabbabb$. + +(1) Si $w \in L$, considérons un arbre d'analyse $\mathscr{W}$ de $w$ + pour $G$ : sa racine, étiquetée $S$, doit avoir des fils étiquetés + selon l'une des deux règles de la grammaire, soit $S\rightarrow b$ + ou bien $S\rightarrow aSS$, autrement dit, soit elle a un unique + fils étiqueté $b$, soit elle a trois fils étiquetés respectivement + $a,S,S$. Dans le premier cas, le mot $w$ est simplement $b$ ; dans + le second, les sous-arbres $\mathscr{U}, \mathscr{V}$ ayant pour + racine les deux fils étiquetés $S$ sont encore des arbres d'analyse + pour $G$, et si on appelle $u$ et $v$ les mots dont ils sont des + arbres d'analyse (c'est-à-dire, ceux obtenus en lisant les feuilles + de $\mathscr{U}$ et $\mathscr{V}$ respectivement par ordre de + profondeur), alors on a $w = auv$ et $u,v\in L$ (puisqu'ils ont des + arbres d'analyse pour $G$). + +La réciproque est analogue : le mot $b$ appartient trivialement à $L$, +et si $u,v\in L$, ils ont des arbres d'analyse $\mathscr{U}, +\mathscr{V}$ pour $G$, et on peut fabriquer un arbre d'analyse pour $w +:= auv$ qui a une racine étiquetée $S$ ayant trois fils étiquetés +$a,S,S$, ces deux derniers ayant pour descendants des sous-arbres +donnés par $\mathscr{U}$ et $\mathscr{V}$. + +\smallbreak + +(2) Montrons par récurrence sur $|w|$ que si $w \in L$ alors on a $wz +\not\in L$ pour tout $z \in \Sigma^+$. La récurrence permet de +supposer la conclusion déjà connue pour tout mot de longueur $<|w|$. +D'après la question (1), le mot $w$ est soit $b$ soit de la forme +$auv$ avec $u,v\in L$ et trivialement $|u|<|w|$ et $|v|<|w|$. Si +$w=b$, il est évident qu'aucun mot de la forme $bz$ ne peut appartenir +à $L$ (la question (1) montre que les seuls mots de $L$ sont le mot +$b$ et des mots commençant par $a$). Il reste le cas $w = auv$ : on +veut montrer que $wz$, c'est-à-dire $auvz$, n'appartient pas à $L$. +Mais s'il y a appartenait, toujours d'après la question (1), il serait +de la forme $au'v'$ (le cas $b$ étant trivialement exclu), où $u',v' +\in L$ ; notamment, $uvz = u'v'$. Distinguons trois cas : (i) soit +$|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$, c'est-à-dire +que $u'$ peut s'écrire sous la forme $u' = ut$ pour un $t\in +\Sigma^+$, et par l'hypothèse de récurrence, on a $u'\not\in L$, une +contradiction ; (ii) soit $|u'|<|u|$, mais alors $u'$ est un préfixe +strict de $u$, c'est-à-dire que $u$ peut s'écrire sous la forme $u = +u't$ pour un $t\in\Sigma^+$, et par l'hypothèse de récurrence (puisque +$|u'|<|u|<|w|$), on a $u\not\in L$, de nouveau une contradiction ; +(iii) soit $|u'|=|u|$, donc $u'=u$ (puisqu'ils sont préfixes de même +longueur du même mot $uvz = u'v'$), et on a alors $v' = vz$, mais +comme $v\in L$, l'hypothèse de récurrence entraîne $v'\not\in L$, +encore une contradiction. + +\smallbreak + +(3) Montrons que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$ +et $v=v'$. On a notamment $uv = u'v'$. Distinguons trois cas : +(i) soit $|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$, +c'est-à-dire que $u'$ peut s'écrire sous la forme $u' = ut$ pour un +$t\in \Sigma^+$, et par la question (2), on a $u'\not\in L$, une +contradiction ; (ii) soit $|u'|<|u|$, mais alors $u'$ est un préfixe +strict de $u$, c'est-à-dire que $u$ peut s'écrire sous la forme $u = +u't$ pour un $t\in\Sigma^+$, et par la question (2), on a $u\not\in +L$, de nouveau une contradiction ; (iii) soit $|u'|=|u|$, donc $u'=u$ +(puisqu'ils sont préfixes de même longueur du même mot $uv = u'v'$), +et on a alors $v' = v$, la conclusion annoncéee. + +\smallbreak + +(4) Soit $w \in L$ : on veut montrer qu'il a un unique arbre d'analyse +pour $G$. On procède par récurrence sur $|w|$, ce qui permet de +supposer la conclusion connue pour tout mot de longueur $<|w|$. Comme +on l'a expliqué en (1), il y a deux possibilités pour un arbre +d'analyse de $w$ : soit la racine a un unique fils étiqueté $b$ et le +mot analysé est $w=b$, soit la racine a trois fils étiquetés $a,S,S$, +et des deux derniers fils partent des arbres d'analyse +$\mathscr{U},\mathscr{V}$ de mots $u,v\in L$ tels que $w=auv$. Ces +deux cas sont évidemment incompatibles : il reste donc simplement à +expliquer que dans le dernier, $\mathscr{U}$ et $\mathscr{V}$ sont +uniquement déterminés. Or la question (3) assure que $u,v$ (tels que +$w=auv$) sont uniquement déterminés, et l'hypothèse de récurrence +permet de conclure (comme $|u|<|w|$ et $|v|<|w|$) que les arbres +d'analyse $\mathscr{U}$ et $\mathscr{V}$ de $u$ et $v$ sont uniquement +déterminés, comme on le voulait. + +\smallbreak + +(5) Donné un mot $w\in\Sigma^*$, la fonction « rechercher préfixe + dans $L$ » suivante renvoie la longueur du préfixe de $w$ +appartenant à $L$, ou bien « échec » si ce préfixe n'existe pas : +\begin{itemize} +\item si $w=\varepsilon$, renvoyer échec, +\item si la première lettre de $w$ est $b$, renvoyer $1$, +\item sinon (la première lettre de $w$ est $a$), soit $x$ le suffixe + de $w$ correspondant (c'est-à-dire $w = ax$, ou si on préfère, $x$ + enlève la première lettre de $w$), +\item appeler la fonction elle-même (rechercher préfixe dans $L$) + sur $x$ : +\item si elle échoue, renvoyer échec, +\item si elle retourne $k$, soit $u$ le préfixe de $x$ de longueur + $k$, et $y$ le suffixe correspondant (c'est-à-dire $x = uy$, ou si + on préfère, $y$ enlève les $k$ premières lettres de $x$), +\item appeler la fonction elle-même (rechercher préfixe dans $L$) + sur $y$ : +\item si elle échoue, renvoyer échec, +\item si elle retourne $\ell$, retourner $1+k+\ell$ (en effet, on a $w + = auvz$ où $u$ est de longueur $k$ et $v$ est de longueur $\ell$). +\end{itemize} + +Pour savoir si un mot appartient à $w$, il s'agit simplement de +vérifier que la valeur retournée (=la longueur du préfixe appartenant +à $L$) n'est pas un échec et est égale à la longueur $|w|$. + +La terminaison de cet algorithme est claire par récurrence sur la +longueur (chaque appel récursif est fait sur un mot de longueur +strictement plus courte), et sa correction est garantie par les +questions précédentes : les cas $b$ et $auv$ sont disjoints et dans le +dernier cas, $u$ et $v$ sont uniquement déterminés (c'est ce +qu'affirme la non-ambiguïté de la grammaire). + +(Il s'agit ici du cas le plus simple d'un analyseur LL, et +l'algorithme présenté ci-dessus est essentiellement un analyseur LL(1) +camouflé sous forme d'analyseur par descente récursive.) +\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$ » 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 d'appeler +$a$ la lettre « parenthèse ouvrante » de $\Sigma$ et $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 considère la grammaire hors contexte $G$ suivante (d'axiome $S$) +sur l'alphabet $\Sigma = \{a,b\}$ : +\[ +S \rightarrow SaS \;|\; b +\] +Soit $L = L(G)$ le langage algébrique qu'elle engendre. + +(0) Donner quelques exemples de mots dans $L$. + +(1) Cette grammaire $G$ est-elle ambiguë ? + +(2) Décrire simplement le langage $L$. + +(3) Donner une grammaire inambiguë engendrant le même langage $L$ +que $G$. + +\begin{corrige} +(0) Quelques exemples de mots dans $L$ sont $b$, $bab$, $babab$, et + ainsi de suite (cf. (2)). + +(1) La grammaire $G$ est ambiguë : le mot $babab$ a deux arbres + d'analyse différents, à savoir +\begin{center} +\tikzstyle{automaton}=[scale=0.5] +%%% begin ex3pt1 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (S3) at (27bp,90bp) [draw,draw=none] {$S$}; + \node (S2) at (243bp,162bp) [draw,draw=none] {$S$}; + \node (S1) at (99bp,162bp) [draw,draw=none] {$S$}; + \node (S0) at (171bp,234bp) [draw,draw=none] {$S$}; + \node (S4) at (171bp,90bp) [draw,draw=none] {$S$}; + \node (a1) at (99bp,90bp) [draw,draw=none] {$a$}; + \node (a0) at (171bp,162bp) [draw,draw=none] {$a$}; + \node (b0) at (243bp,90bp) [draw,draw=none] {$b$}; + \node (b1) at (27bp,18bp) [draw,draw=none] {$b$}; + \node (b2) at (171bp,18bp) [draw,draw=none] {$b$}; + \draw [] (S1) ..controls (70.042bp,132.85bp) and (55.714bp,118.92bp) .. (S3); + \draw [] (S0) ..controls (142.04bp,204.85bp) and (127.71bp,190.92bp) .. (S1); + \draw [] (S0) ..controls (171bp,204.85bp) and (171bp,190.92bp) .. (a0); + \draw [] (S2) ..controls (243bp,132.85bp) and (243bp,118.92bp) .. (b0); + \draw [] (S1) ..controls (99bp,132.85bp) and (99bp,118.92bp) .. (a1); + \draw [] (S0) ..controls (199.96bp,204.85bp) and (214.29bp,190.92bp) .. (S2); + \draw [] (S3) ..controls (27bp,60.846bp) and (27bp,46.917bp) .. (b1); + \draw [] (S4) ..controls (171bp,60.846bp) and (171bp,46.917bp) .. (b2); + \draw [] (S1) ..controls (127.96bp,132.85bp) and (142.29bp,118.92bp) .. (S4); +% +\end{tikzpicture} + +%%% end ex3pt1 %%% +\end{center} +et son symétrique par rapport à l'axe vertical. + +\smallbreak + +(2) Montrons que $L$ est égal au langage $L_{(ba){*}b}$ dénoté par +l'expression rationnelle $(ba){*}b$ comme la question (0) le laisse +entrevoir. Pour cela, il suffit de voir que l'ensemble des +pseudo-mots (:= mots sur l'ensemble des terminaux et des nonterminaux) +qu'on peut dériver de $S$ dans $G$ est le langage $((S|b)a){*}(S|b)$ +constitué des pseudo-mots de la forme $xaxax\cdots ax$ où chaque $x$ +est soit un $S$ soit un $b$, indépendamment les uns des autres. Or il +est clair que remplacer un $x$ (et notamment, remplacer un $S$) par +$SaS$ (qui est de la forme $xax$) dans un pseudo-mot de cette forme +donne encore un pseudo-mot de cette forme : ceci montre qu'une +dérivation de $G$, quelle que soit l'application faite de la règle +$S\rightarrow SaS$, donne des pseudo-mots de cette forme, donc tout +pseudo-mot obtenu par dérivation de $S$ dans la grammaire $G$ est de +la forme qu'on vient de dire ; et réciproquement, il est facile de +produire n'importe quel nombre $n$ de répéritions du motif $aS$ en +appliquant $n$ fois la règle $S\rightarrow SaS$ à partir de $S$, et on +peut ensuite librement transformer certains $S$ en $b$. + +\smallbreak + +(3) La grammaire $G'$ donnée par $S \rightarrow baS\,|\,b$ engendre le +même langage que $G$ d'après la question précédente ; et il est +évident que cette grammaire est inambiguë : toutes les dérivations +sont de la forme $S \Rightarrow baS \Rightarrow babaS \Rightarrow +(ba)^n S$ suivie éventuellement de $\Rightarrow (ba)^n b$. +\end{corrige} + +% +% +% + +\subsection{Introduction à la calculabilité} + +\exercice + +Soit $\Sigma$ un alphabet (fini, non vide) fixé. Les questions +suivantes sont indépendantes (mais on remarquera leur parallélisme). +Ne pas hésiter à décrire les algorithmes de façon succincte et +informelle. + +(1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe +un algorithme $A_1$ qui, étant donnée une expression rationnelle $r$ +sur $\Sigma$, décide si le langage $L_r$ dénoté par $r$ est différent +du langage $\Sigma^*$ de tous les mots sur $\Sigma$. (Autrement dit, +l'algorithme $A_1$ doit prendre en entrée une expression rationnelle +$r$, terminer en temps fini, et répondre « vrai » s'il existe un mot +$w\in\Sigma^*$ tel que $w\not\in L_r$ et « faux » si $L_r = \Sigma^*$. +On ne demande pas que l'algorithme soit efficace.) + +(2) Expliquer pourquoi il existe un algorithme $A_2$ qui, étant donnée +une grammaire hors contexte $G$ sur $\Sigma$, « semi-décide » si le +langage $L_G$ engendré par $G$ est différent du langage $\Sigma^*$ de +tous les mots. (« Semi-décider » signifie que l'algorithme $A_2$ doit +prendre en entrée une grammaire hors contexte $G$, terminer en temps +fini en répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que +$w\not\in L_G$, et ne pas terminer\footnote{On peut admettre qu'il + termine parfois en répondant « faux », mais ce ne sera pas utile.} +si $L_G = \Sigma^*$.) Indication : on peut tester tous les mots +possibles. + +(3) Expliquer pourquoi il existe un algorithme $A_3$ comme suit : on +lui fournit en entrée un algorithme $T$ qui décide un langage $L_T +\subseteq \Sigma^*$ (c'est-à-dire que $T$ termine toujours en temps +fini quand on lui présente un mot sur $\Sigma$, et répond « vrai » ou +« faux », et $L_T$ est le langage des mots sur lesquels il répond +« vrai »), et l'algorithme $A_3$ doit semi-décider si $L_T$ est +différent de $\Sigma^*$. (C'est-à-dire que $A_3$ doit terminer en +répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que $w\not\in +L_T$, et ne pas terminer si $L_T = \Sigma^*$.) Indication : la même +approche permet de traiter les questions (2) et (3). + +(4) Expliquer pourquoi il \emph{n'existe pas} d'algorithme $A_4$ qui, +dans les mêmes conditions que $A_3$, décide (au lieu de seulement +semi-décider) si $L_T$ est différent de $\Sigma^*$. (C'est-à-dire que +$A_4$ est censé terminer toujours, et répondre « vrai » s'il existe un +mot $w\in\Sigma^*$ tel que $w\not\in L_T$, et « faux » si $L_T = +\Sigma^*$.) Indication : expliquer comment on pourrait utiliser un +tel $A_4$ pour résoudre le problème de l'arrêt, en cherchant à +fabriquer un $T$ qui rejette un mot précisément si un programme donné +s'arrête. + +\begin{corrige} +(1) Donnée une expression rationnelle $r$, on sait qu'on peut + algorithmiquement fabriquer un automate fini non-déterministe à + transitions spontanées qui reconnaît exactement le langage $L_r$ + dénoté par $r$, et ensuite éliminer les transitions spontanées et + déterminiser l'automate pour obtenir un automate fini déterministe + complet reconnaissant $L_r$. Sur un tel automate, savoir si $L_r + \neq \Sigma^*$ est trivial : dès lors qu'il existe un état $q$ + non-final accessible, il existe un mot rejeté par l'automate (i.e., + n'appartenant pas à $L_r$), à savoir le mot lu en suivant les + étiquettes d'un chemin quelconque de l'état initial $q_0$ + jusqu'à $q$, et inversement, si tous les états sont finaux, il est + trivial que l'automate accepte tous les mots. (On pouvait aussi + minimiser l'automate et le comparer à l'automate minimal trivial qui + reconnaît le langage $\Sigma^*$.) + +\smallbreak + +(2) On sait qu'il existe un algorithme qui, donnée une grammaire +hors-contexte $G$ et un mot $w$, décide si $w \in L_G$. Pour +semi-décider s'il existe un $w$ tel que $w \not\in L_G$, il suffit de +tester tous les mots possibles : plus exactement, on construit un +algorithme $A_2$ qui effectue une boucle infinie sur tous les +$w\in\Sigma^*$ (il est évidemment algorithmiquement faisable +d'énumérer tous les mots sur $\Sigma$) et, pour chacun, teste si $w +\in L_G$, et si ce n'est pas le cas, termine immédiatement en +répondant « vrai » (on a trouvé un $w$ n'appartenant pas à $L_G$), +tandis que si c'est le cas, l'algorithme $A_2$ ne terminera jamais. + +\smallbreak + +(3) On procède exactement comme en (2) : par hypothèse on dispose d'un +algorithme $T$ qui, donné un mot $w$, décide si $w \in L_T$. Pour +semi-décider s'il existe un $w$ tel que $w \not\in L_T$, il suffit de +tester tous les mots possibles : plus exactement, on construit un +algorithme $A_3$ qui effectue une boucle infinie sur tous les +$w\in\Sigma^*$ et, pour chacun, teste si $w \in L_T$ (en lançant +l'algorithme $T$ qui, par hypothèse, termine toujours), et si ce n'est +pas le cas, termine immédiatement en répondant « vrai » (on a trouvé +un $w$ n'appartenant pas à $L_T$), tandis que si c'est le cas, +l'algorithme $A_3$ ne terminera jamais. + +\smallbreak + +(4) Supposons par l'absurde qu'on dispose d'un algorithme $A_4$ comme +on vient de dire, et montrons pour arriver à une contradiction qu'on +peut s'en servir pour résoudre le problème de l'arrêt. On se donne +donc un algorithme $S$ et une entrée $x$ de $S$ et on cherche à savoir +(en utilisant $A_4$) si $S$ termine sur l'entrée $x$. Pour cela, on +va construire un $T$ auquel appliquer $A_4$. + +Voici une solution possible : donné un mot $w \in \Sigma^*$, le +programme $T$ ne considère que la longueur $|w|$ de $w$, et lance +(=simule) l'exécution de $S$ sur l'entrée $x$ pour au plus $|w|$ +étapes : si l'exécution termine dans le temps imparti, alors $T$ +rejette le mot $w$, sinon, il l'accepte (dans tous les cas, $T$ +termine et répond « vrai » ou « faux », donc il est une entrée +légitime à $A_4$). Cette construction fait que $L_T$ rejette au moins +un mot précisément lorsque $S$ termine sur $x$ : si au contraire $S$ +ne termine pas sur $x$, alors $L_T = \Sigma^*$. L'utilisation de +$A_4$ sur $T$ permet donc de savoir algorithmiquement si $S$ termine +sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt. + +\textit{Variante de la même idée :} on appelle « trace d'exécution » de $S$ sur +$x$ un mot $w$ qui code le calcul complet de l'exécution de $S$ sur +$x$ (par exemple, si on voit $S$ comme une machine de Turing, l'état +courant et le contenu du ruban à chaque étape), du début à l'arrêt. +Une telle trace d'exécution existe donc précisément si $S$ termine +sur $x$. Or il est visiblement décidable de savoir si un mot $w$ +donné est une trace d'exécution (il suffit de vérifier qu'à chaque +étape la machine a bien fait ce qu'elle devait faire). On peut donc +écrire un algorithme $T$ qui termine toujours et accepte précisément +les mots qui \emph{ne sont pas} une trace d'exécution de $S$ sur $x$. +Le fait que $L_T$ soit différent de $\Sigma^*$ signifie alors +exactement qu'une trace d'exécution existe, donc que $S$ termine +sur $x$. Ainsi l'utilisation de $A_4$ permet de savoir +algorithmiquement si $S$ termine sur $x$, ce qui contredit +l'indécidabilité du problème de l'arrêt. +\end{corrige} + +% + +\exercice + +(1) Soit $\Sigma$ un alphabet (i.e., un ensemble fini). L'ensemble $L += \{u^k : u\in\Sigma^*, k\geq 2\}$ des mots qui sont une puissance +$k$-ième pour un $k\geq 2$ est-il décidable ? Semi-décidable ? + +(2) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième +programme (ou, si on préfère, de la $e$-ième machine de Turing), +exécuté sur l'entrée $42$, termine en au plus $10^{1000+e}$ étapes +est-il décidable ? Semi-décidable ? + +(3) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième +programme (ou, si on préfère, de la $e$-ième machine de Turing), +exécuté sur l'entrée $42$, termine en temps fini est-il décidable ? +Semi-décidable ? (On pourra montrer qu'on peut y ramener le problème +de l'arrêt.) + +\begin{corrige} +(1) Si $w = u^k$ pour un certain $u\neq\varepsilon$, alors + nécessairement $k\leq |w|$ puisque $|w|=k\cdot|u|$. On dispose donc + de l'algorithme suivant pour décider si $w\in L$ : si + $w=\varepsilon$, retourner vrai immédiatement ; sinon, pour $k$ + allant de $2$ à $|w|$ et qui divise $|w|$, considérer les $k$ + facteurs successifs de $w$ de longueur $|w|/k$ (c'est-à-dire, pour + $0\leq i<k$, le facteur de $w$ de longueur $\ell := |w|/k$ + commençant à la position $i \ell$) : s'ils sont tous égaux, renvoyer + vrai ; si la boucle termine sans avoir trouvé de $k$ qui convienne, + renvoyer faux. Le langage proposé est donc décidable (et \textit{a + fortiori} semi-décidable). + +\smallbreak + +(2) Donné un $e \in \mathbb{N}$, la fonction $10^{1000+e}$ est + évidemment calculable. On peut ensuite lancer l'exécution du + $e$-ième programme, sur l'entrée $42$, pour au plus ce nombre + d'étapes (en utilisant la machine universelle, c'est-à-dire, par + exemple, en simulant la $e$-ième machine de Turing sur une machine + de Turing). Si l'exécution termine en le temps imparti, on renvoie + vrai, sinon, on renvoie faux : ceci montre que l'ensemble proposé + est bien décidable (et \textit{a fortiori} semi-décidable). + +\smallbreak + +(3) L'ensemble $A$ proposé est « presque » le problème de l'arrêt. La + différence est que le problème de l'arrêt est l'ensemble des couples + $(e,n)$ tels que le $e$-ième programme termine sur l'entrée $n$ + alors qu'ici on a fixé l'entrée à $42$. Il s'agit donc de montrer + que cette limitation ne rend pas pour autant calculable l'ensemble + considéré. Or donnés deux entiers $(e,n)$, on peut fabriquer un + programme $e'$ qui prend en entrée une valeur, \emph{ignore} cette + valeur, et exécute le $e$-ième programme sur l'entrée $n$ ; de plus + un tel $e'$ se calcule algorithmiquement\footnote{Techniquement, on + invoque ici le théorème s-m-n ; mais dans les faits, il s'agit + essentiellement d'ajouter une ligne « \texttt{let + n=}(représentation décimale de $n$) » au début d'un programme, + ce qui est certainement faisable.} à partir de $e$ et $n$. + L'exécution du programme $e'$ sur l'entrée $42$ (ou n'importe quelle + autre entrée) se comporte donc comme l'exécution du programme $e$ + sur l'entrée $n$, et notamment, termine si et seulement si elle + termine. Autrement dit, $e'$ appartient à l'ensemble $A$ considéré + dans cette question si et seulement si $(e,n)$ appartient au + problème de l'arrêt. Comme on vient de dire qu'on peut calculer + $e'$ algorithmiquement à partir de $(e,n)$, si l'ensemble $A$ était + décidable, le problème de l'arrêt le serait, ce qui n'est pas le + cas. Donc $A$ n'est pas décidable. En revanche, $A$ est + semi-décidable : il suffit de lancer l'exécution du programme $e$ + sur l'entrée $42$ et renvoyer vrai si elle termine (si elle ne + termine pas, on ne termine pas). +\end{corrige} + +% + +\exercice + +Soit $\Sigma$ un alphabet (i.e., un ensemble fini). On s'intéresse à +des langages sur $\Sigma$. + +(A) Montrer que si deux langages $L_1$ et $L_2$ sont décidables, alors +$L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont décidables ; montrer +que si un langage $L$ est décidable alors $L^*$ est décidable (pour ce +dernier, on pourra commencer par chercher, si $w \in \Sigma^*$ est un +mot de longueur $n$, comment énumérer toutes les façons de le +factoriser en mots de longueur non nulle). + +(B) Montrer que si deux langages $L_1$ et $L_2$ sont semi-décidables, +alors $L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont +semi-décidables ; montrer que si un langage $L$ est semi-décidable +alors $L^*$ est semi-décidable. + +\begin{corrige} +(A) Supposons qu'on dispose d'algorithmes $T_1$ et $T_2$ qui décident + $L_1$ et $L_2$ respectivement (i.e., donné $w \in \Sigma^*$, + l'algorithme $T_i$ termine toujours en temps fini, en répondant oui + si $w\in L_i$ et non si $w\not\in L_i$). + +Pour faire un algorithme qui décide $L_1\cup L_2$, donné un mot +$w\in\Sigma^*$, il suffit de lancer successivement $T_1$ et $T_2$ : si +l'un des deux répond oui, on répond oui, sinon on répond non +(autrement dit, on calcule les valeurs de vérité de $w\in L_1$ et +$w\in L_2$ au moyen de $T_1$ et $T_2$, et on calcule ensuite leur +« ou » logique). De même pour décider $L_1\cap L_2$, il suffit de +lancer successivement $T_1$ et $T_2$, si les deux répondent oui on +répond oui, sinon on répond non (i.e., on calcule les valeurs de +vérité de $w\in L_1$ et $w\in L_2$ au moyen de $T_1$ et $T_2$, et on +calcule ensuite leur « et » logique). + +Pour décider $L_1 L_2$, on effectue une boucle sur toutes les +factorisation $w = uv$ de $w$, c'est-à-dire, une boucle sur toutes les +longueurs $0\leq i\leq |w|$ en appelant à chaque fois $u$ le préfixe +de $w$ de longueur $i$ et $v$ le suffixe de $w$ de longueur $|w|-i$, +et pour chaque paire $(u,v)$ ainsi trouvée, on utilise $T_1$ et $T_2$ +pour tester si $u\in L_1$ et $v\in L_2$ : si c'est le cas, on termine +l'algorithme en répondant oui (on a $w = uv \in L_1 L_2$) ; si aucune +paire ne convient, on répond non. + +L'algorithme pour décider $L^*$ est semblable : il s'agit de tester +toutes les manières de factoriser un mot $w \in \Sigma^*$ en facteurs +de longueur non nulle. (On peut d'ores et déjà exclure +$w=\varepsilon$ car le mot vide appartient de toute façon à $L^*$.) +Si $n=|w| > 0$, on peut effectuer une boucle pour un nombre de +facteurs $k$ allant de $1$ à $n$, et, pour chaque $k$, effectuer $k$ +boucles emboîtées pour déterminer les limites des facteurs +$u_1,\ldots,u_k \in \Sigma^+$ tels que $w = u_1\cdots u_k$ (il suffit +par exemple de faire boucler $i_1,\ldots,i_k$ chacun de $1$ à $n$, et +lorsque $i_1+\cdots+i_k = n$, appeler $u_j$ le facteur de $w$ de +longueur $i_j$ commençant à la position $i_1+\cdots+i_{j-1}$). Pour +chaque factorisation comme on vient de le dire, on teste si tous les +$u_i$ appartiennent à $L$, et si c'est le cas on renvoie vrai (le mot +$w$ appartient à $L^*$) ; si aucune factorisation ne convient, on +renvoie faux. + +(Dans l'algorithme qui précède, on a écarté les factorisations faisant +intervenir le mot vide, car si $w$ est factorisable en mots de $L$ en +faisant intervenir le mot vide, quitte à retirer celui-ci, il est +encore factorisable en mots non vides de $L$.) + +\smallbreak + +(B) Les algorithmes sont très semblables à ceux de la partie (A) si ce +n'est qu'il faut tenir compte de la possibilité qu'ils puissent ne pas +terminer. À part pour l'intersection, on doit donc les lancer « en +parallèle » et pas « en série » : lorsqu'on dira qu'on lance deux +algorithmes $T$ et $T'$ « en parallèle », cela signifie qu'on exécute +une étape du calcul de $T$, puis une étape de $T'$, puis de nouveau +une de $T$, et ainsi de suite en alternant entre les deux, jusqu'à ce +que l'un termine et renvoie vrai. + +Si $L_1$ et $L_2$ sont semi-dédicables et si $T_1$ et $T_2$ sont des +algorithmes qui les « semi-décident » (i.e., $T_i$ termine en temps +fini et répond oui si $w\in L_i$, et ne termine pas sinon), pour +semi-décider $L_1\cup L_2$, on lance les deux algorithmes $T_1$ et +$T_2$ en parallèle sur le même mot $w$ : si l'un d'eux termine, on +termine en renvoyant vrai (sinon, bien sûr, on ne termine pas). + +Pour semi-décider $L_1\cap L_2$, en revanche, il n'y a pas de raison +de procéder en parallèle : on lance d'abord $T_1$ sur le mot $w$ à +tester : si $T_1$ termine, on lance ensuite $T_1$ sur le même mot : si +$T_2$ termine et renvoie vrai, on renvoie vrai ; si l'un des deux +algorithmes $T_i$ lancés séquentiellement ne termine pas, bien sûr, le +calcul dans son ensemble ne terminera pas. + +Pour semi-décider $L_1 L_2$ ou $L^*$, on procède comme dans le cas (A) +en lançant en parallèle les algorithmes pour tester toutes les +différentes factorisations possibles $w = uv$ ou bien $w = u_1\cdots +u_k$ (en mots non vides) du mot $w$. +\end{corrige} + +% + +\exercice + +On rappelle qu'une fonction $f\colon \mathbb{N} \to \mathbb{N}$ est +dite \emph{calculable} lorsqu'il existe un algorithme (par exemple, un +programme pour une machine de Turing) prenant en entrée un +$n\in\mathbb{N}$ qui termine toujours en temps fini et renvoie la +valeur $f(n)$. On rappelle qu'une partie $E$ de $\mathbb{N}$ ou de +$\mathbb{N}^2$ est dite \emph{décidable} lorsque sa fonction +indicatrice est calculable, ou, ce qui revient au même, lorsqu'il +existe un algorithme prenant en entrée un élément de $\mathbb{N}$ ou +de $\mathbb{N}^2$ qui termine toujours en temps fini et renvoie +vrai ($1$) ou faux ($0$) selon que l'élément fourni appartient ou non +à $E$. On rappelle enfin qu'une partie $E$ de $\mathbb{N}$ ou de +$\mathbb{N}^2$ est dite \emph{semi-décidable} lorsqu'il existe un +algorithme prenant en entrée un élément de $\mathbb{N}$ ou de +$\mathbb{N}^2$ qui termine toujours en temps fini et renvoie +vrai ($1$) si l'élément fourni appartient à $E$, et sinon ne termine +pas (on peut aussi accepter qu'il termine en renvoyant faux, cela ne +change rien). + +Soit $f\colon \mathbb{N} \to \mathbb{N}$ : montrer qu'il y a +équivalence entre les affirmations suivantes : +\begin{enumerate} +\item la fonction $f$ est calculable, +\item le graphe $\Gamma_f := \{(n,f(n)) : n\in\mathbb{N}^2\} = + \{(n,p)\in\mathbb{N}^2 : p=f(n)\}$ de $f$ est décidable, +\item le graphe $\Gamma_f$ de $f$ est semi-décidable. +\end{enumerate} + +(Montrer que (3) implique (1) est le plus difficile : on pourra +commencer par s'entraîner en montrant que (2) implique (1). Pour +montrer que (3) implique (2), on pourra chercher une façon de tester +en parallèle un nombre croissant de valeurs de $p$ de manière à +s'arrêter si l'une quelconque convient.) + +\begin{corrige} +Montrons que (1) implique (2) : si on dispose d'un algorithme capable +de calculer $f(n)$ en fonction de $n$, alors il est facile d'écrire un +algorithme capable de décider si $p=f(n)$ (il suffit de calculer +$f(n)$ avec l'algorithme supposé exister, de comparer avec la valeur +de $p$ fournie, et de renvoyer vrai/$1$ si elles sont égales, et +faux/$0$ sinon). + +Le fait que (2) implique (3) est évident car tout ensemble décidable +est semi-décidable. + +Montrons que (2) implique (1) même si ce ne sera au final pas utile : +supposons qu'on ait un algorithme $T$ qui décide $\Gamma_f$ (i.e., +donnés $(n,p)$, termine toujours en temps fini, en répondant oui si +$p=f(n)$ et non si $p\neq f(n)$), et on cherche à écrire un algorithme +qui calcule $f(n)$. Pour cela, donné un $n$, il suffit de lancer +l'algorithme $T$ successivement sur les valeurs $(n,0)$ puis $(n,1)$ +puis $(n,2)$ et ainsi de suite (c'est-à-dire faire une boucle infinie +sur $p$ et lancer $T$ sur chaque couple $(n,p)$) jusqu'à trouver un +$p$ pour lequel $T$ réponde vrai : on termine alors en renvoyant la +valeur $p$ qu'on a trouvée, qui vérifie $p=f(n)$ par définition +de $T$. + +\smallbreak + +Reste à montrer que (3) implique (1) : supposons qu'on ait un +algorithme $T$ qui « semi-décide » $\Gamma_f$ (i.e., donnés $(n,p)$, +termine en temps fini et répond oui si $p=f(n)$, et ne termine pas +sinon), et on cherche à écrire un algorithme qui calcule $f(n)$. Pour +cela, on va tester les valeurs $0\leq p\leq M$ chacune pour $M$ étapes +et faire tendre $M$ vers l'infini : plus exactement, on utilise +l'algorithme $U$ suivant : +\begin{itemize} +\item pour $M$ allant de $0$ à l'infini, +\begin{itemize} +\item pour $p$ allant de $0$ à $M$, +\begin{itemize} +\item exécuter l'algorithme $T$ sur l'entrée $(n,p)$ pendant au + plus $M$ étapes, +\item s'il termine en renvoyant vrai ($1$), terminer et renvoyer $p$ + (sinon, continuer les boucles). +\end{itemize} +\end{itemize} +\end{itemize} + +(Intuitivement, $U$ essaie de lancer l'algorithme $T$ sur un nombre de +valeurs de $p$ de plus en plus grand et en attendant de plus en plus +longtemps pour voir si l'une d'elles termine.) + +Si l'algorithme $U$ défini ci-dessus termine, il renvoie forcément +$f(n)$ (puisque l'algorithme $T$ a répondu vrai, c'est que $p=f(n)$, +et on renvoie la valeur en question) ; il reste à expliquer pourquoi +$U$ termine toujours. Mais la valeur $f(n)$ existe (même si on ne la +connaît pas) car la fonction $f$ était supposée définie partout, et +lorsque l'algorithme $T$ est lancé sur $(n,f(n))$ il est donc censé +terminer en un certain nombre (fini !) d'étapes : si $M$ est supérieur +à la fois à $f(n)$ et à ce nombre d'étapes, la valeur $f(n)$ va être +prise par $p$ dans la boucle intérieure, et pour cette valeur, +l'algorithme $T$ va terminer sur l'entrée $(n,p)$ en au plus $M$ +étapes, ce qui assure que $U$ termine effectivement. + +L'algorithme $U$ calcule donc bien la fonction $f$ demandée, ce qui +prouve (1). +\end{corrige} + +% + +\exercice + +Soit $A \subseteq \mathbb{N}$ un ensemble infini. Montrer qu'il y a +équivalence entre : +\begin{itemize} +\item l'ensemble $A$ est décidable, +\item il existe une fonction calculable \emph{strictement croissante} + $f\colon\mathbb{N}\to\mathbb{N}$ telle que $f(\mathbb{N}) = A$. +\end{itemize} + +\begin{corrige} +Supposons $A$ décidable : on va construire $f$ comme indiqué. Plus +exactement, on va appeler $f(n)$ le $n$-ième élément de $A$ par ordre +croissant (c'est-à-dire que $f(0)$ est le plus petit élément de $A$, +et $f(1)$ le suivant par ordre de taille, et ainsi de suite ; noter +que $A$ est infini donc cette fonction est bien définie). Montrons +que $f$ est calculable : donné un entier $n$, on teste successivement +si $0\in A$ puis $1\in A$ puis $2\in A$ et ainsi de suite, à chaque +fois en utilisant un algorithme décidant $A$ (qui est censé exister +par hypothèse) jusqu'à obtenir $n$ fois la réponse « oui » ; plus +exactement : +\begin{itemize} +\item initialiser $m \leftarrow 0$, +\item pour $k$ allant de $0$ à l'infini, +\begin{itemize} +\item interroger l'algorithme qui décide si $k\in A$, +\item s'il répond « oui » : +\begin{itemize} +\item si $m=n$, terminer et renvoyer $k$, +\item sinon, incrémenter $m$ (c'est-à-dire faire $m \leftarrow m+1$). +\end{itemize} +\end{itemize} +\end{itemize} +La boucle termine car $A$ est infini. + +Réciproquement, supposons $f$ strictement croissante calculable et +posons $A = f(\mathbb{N})$ : on veut montrer que $A$ est décidable. +Or pour décider si $k \in A$, il suffit de calculer successivement +$f(0)$, $f(1)$, $f(2)$ et ainsi de suite, et de terminer si $f(n)$ +atteint ou dépasse le $k$ fixé : s'il l'atteint, on renvoie vrai (on a +trouvé $n$ tel que $f(n)=k$), sinon, on renvoie faux (la valeur $k$ a +été sautée par la fonction $f$ et ne sera donc jamais atteinte). +L'algorithme est donc explicitement : +\begin{itemize} +\item pour $n$ allant de $0$ à l'infini, +\begin{itemize} +\item calculer $f(n)$, +\item si $f(n) = k$, renvoyer vrai, +\item si $f(n) > k$, renvoyer faux. +\end{itemize} +\end{itemize} +La boucle termine car toute fonction strictement croissante +$\mathbb{N}\to\mathbb{N}$ est de limite $+\infty$ en l'infini (donc +$f(n)$ finit forcément par atteindre ou dépasser $k$). +\end{corrige} + +% + +\exercice + +Soit $S(e,n)$ le nombre d'étapes de l'exécution du $e$-ième programme +(ou, si on préfère, de la $e$-ième machine de Turing) quand on lui +fournit le nombre $n$ en entrée, à supposer que cette exécution +termine ; sinon, $S(e,n)$ n'est pas défini. + +Soit par ailleurs $M(k)$ le maximum des $S(e,n)$ pour $0\leq e\leq k$ +et $0\leq n\leq k$ qui soient définis (et $0$ si aucun d'eux n'est +défini). Autrement dit, il s'agit du plus petit entier supérieur ou +égal au nombre d'étapes de l'exécution de l'un des programmes $0\leq +e\leq k$ sur l'un des entiers $0\leq n\leq k$ en entrée, lorsqu'ils +terminent. + +Montrer que la fonction $M$ n'est pas calculable (i.e., n'est pas +calculable par un algorithme) : on pourra pour cela montrer que la +connaissance de $M$ permet de résoudre le problème de l'arrêt. +Montrer même qu'\emph{aucune} fonction $M'$ telle que $M'(k) \geq +M(k)$ pour tout $k$ n'est calculable. Montrer que même si $M'$ +vérifie simplement $M'(k)\geq M(k)$ pour $k\geq k_0$, alors $M'$ n'est +pas calculable. + +\emph{Remarque :} La fonction $M$, ou différentes variantes de +celle-ci, s'appelle fonction du « castor affairé ». On peut montrer +encore plus fort : si $F$ est une fonction calculable quelconque, +alors il existe $k_0$ tel que $M(k) \geq F(k)$ pour $k\geq k_0$ +(autrement dit, la fonction $M$ finit par dépasser n'importe quelle +fonction calculable : Radó, 1962, \textit{On Non-Computable + Functions}). + +\begin{corrige} +Supposons que $M$ soit calculable. On peut alors résoudre le problème +de l'arrêt de la manière suivante : donné un algorithme $T$, de +numéro $e$, et une entrée $n$ à fournir à cet algorithme, pour savoir +si $T$ s'arrête, on calcule $M(k)$ où $k = \max(e,n)$, on exécute +ensuite l'algorithme $T$ pendant au plus $M(k)$ étapes : s'il termine +dans le temps imparti, on répond vrai (il a terminé), sinon, on répond +faux (il ne terminera jamais). Cette résolution du problème de +l'arrêt est correcte, car si $T$ termine sur l'entrée $n$, il prendra +par définition $S(e,n)$ étapes, avec $0\leq e\leq k$ et $0\leq n\leq +k$ par définition de $k$, donc $S(e,n) \leq M(k)$ par définition de +$M(k)$ : ceci signifie précisément que si $T$ n'a pas terminé en +$M(k)$ étapes, il ne terminera jamais. + +Exactement le même argument montre que $M'$ n'est pas calculable sous +l'hypothèse que $M'(k) \geq M(k)$ pour tout $k$ : s'il l'était, on +pourrait exécuter l'algorithme $T$ pendant au plus $M'(k)$ étapes, et +comme on a $S(e,n) \leq M(k) \leq M'(k)$, la même démonstration +convient. + +Enfin, si on suppose seulement $M'(k)\geq M(k)$ pour $k\geq k_0$, la +fonction $M'$ n'est toujours pas calculable : en effet, si on suppose +par l'absurde qu'elle l'est, la fonction $M''$ qui à $k$ associe +$M'(k)$ si $k\geq k_0$ et $M(k)$ sinon, serait encore calculable +puisqu'elle ne diffère de $M'$ qu'en un nombre fini de valeurs, or +changer la valeur en un point d'une fonction calculable donne toujours +une fonction calculable (même si on « ne connaît pas » la valeur à +changer, elle existe, donc l'algorithme modifié existe). Mais d'après +le paragraphe précédent, $M''$ n'est pas calculable puisqu'elle est +partout supérieure ou égale à $M$. +\end{corrige} + +% + +\exercice + +Dans cet exercice, on s'intéresse au langage $L$ formé des +programmes $e$ (codés, dans une formalisation quelconque de la +calculabilité\footnote{Par exemple, un langage de programmation + (Turing-complet) quelconque.}, comme des entiers naturels ou comme +des mots sur un alphabet fixé sans importance) qui, quel que soit le +paramètre $n$ qu'on leur fournit en entrée, terminent en temps fini et +retournent la valeur $0$ : soit $L = \{e : (\forall n) +{\varphi_e(n)\downarrow} = 0\}$. Si l'on préfère, $L$ est l'ensemble +de toutes les façons de coder la fonction constante égale à $0$. On +appellera aussi $M$ le complémentaire de $L$. On se demande si $L$ ou +$M$ sont semi-décidables. + +\smallskip + +(1) Thésée et Hippolyte se disputent pour savoir si $L$ est +semi-décidable. Thésée pense qu'il l'est, et il tient le raisonnement +suivant pour l'expliquer : + +{\narrower + +Pour savoir si un programme $e$ est dans l'ensemble $L$, il suffit de +l'examiner pour vérifier que toutes les instructions qui mettent fin +au programme renvoient la valeur $0$ : si c'est le cas, on termine en +répondait « oui » (c'est-à-dire $e\in L$) ; sinon, on rentre dans une +boucle infinie. Ceci fournit un algorithme qui semi-décide $L$. + +\par} + +\smallskip + +\noindent Hippolyte, elle, pense que $L$ n'est pas semi-décidable. Son +argument est le suivant : + +{\narrower + +Si $L$ était semi-décidable, je pourrais m'en servir pour résoudre le +problème de l'arrêt. En effet, donné un programme $e'$ et une +entrée $m$ sur laquelle je cherche à tester l'arrêt de $e'$, je peux +fabriquer le programme $e$ qui prend une entrée $n$, lance l'exécution +de $e'$ sur l'entrée $m$ pendant au plus $n$ étapes et à la fin +renvoie $1$ si ces $n$ étapes ont suffi à terminer l'exécution +de $e'$, et $0$ sinon. Dire que $e \in L$ signifie que $e'$ ne +termine jamais sur $m$, donc pouvoir semi-décider $L$ permet de +résoudre algorithmiquement le problème de l'arrêt, ce qui est +impossible. + +\par} + +\smallskip + +\noindent Qui a raison ? Expliquer précisément quelle est l'erreur +(ou les erreurs) commise(s) par le raisonnement incorrect, et +détailler les éventuels passages incomplets dans le raisonnement +correct. + +\begin{corrige} +C'est Hippolyte qui a raison ($L$ n'est pas semi-décidable). + +L'argument de Thésée est stupide : une instruction mettant fin au +programme avec une valeur autre que $0$ pourrait ne jamais être +atteinte, et réciproquement, même si toutes les instructions mettant +fin au programme renvoyaient $0$, il pourrait aussi ne jamais +terminer. (Au passage, l'argument de Thésée semblerait même montrer +que $L$ est décidable, pas juste semi-décidable.) + +L'argument d'Hippolyte, lui, est correct : il montre que si $L$ était +semi-décidable, le complémentaire du problème de l'arrêt (l'ensemble +des $e'$ qui ne terminent jamais) serait semi-décidable, ce qui n'est +pas le cas. (Le complémentaire du problème de l'arrêt n'est pas +semi-décidable, car s'il l'était, le problème de l'arrêt serait +décidable, vu qu'il est déjà semi-décidable.) Parmi les points qui +méritent éventuellement d'être précisés, on peut mentionner : le fait +que $e$ se déduise algorithmiquement de $e'$ et $m$ ; et le fait qu'il +est algorithmiquement possible de lancer l'exécution d'un programme +sur $n$ étapes (peu importe la définition exacte de « étape » tant que +chacune termine à coup sûr en temps fini) et tester si elle est bien +finie au bout de ce temps. +\end{corrige} + +\medskip + +(2) Achille et Patrocle se disputent pour savoir si $M$ (le +complémentaire de $L$) est semi-décidable. Achille pense qu'il l'est, +et il tient le raisonnement suivant pour l'expliquer : + +{\narrower + +Pour savoir si un programme $e$ est dans l'ensemble $M$, il suffit de +tester successivement les valeurs $\varphi_e(n)$ pour tous les $n$ +possibles : si l'on rencontre un $n$ tel que $\varphi_e(n)$ n'est +pas $0$, alors on termine en répondant « oui » (c'est-à-dire $e\in +M$) ; sinon, on ne va jamais terminer, et cela signifie que $e\not\in +M$. Ceci fournit un algorithme qui semi-décide $M$. + +\par} + +\smallskip + +\noindent Patrocle, lui, pense que $M$ n'est pas semi-décidable. Son +argument est le suivant : + +{\narrower + +Si $M$ était semi-décidable, je pourrais m'en servir pour résoudre le +problème de l'arrêt. En effet, donné un programme $e'$ et une +entrée $m$ sur laquelle je cherche à tester l'arrêt de $e'$, je peux +fabriquer le programme $e$ qui prend une entrée $n$, l'ignore purement +et simplement, exécute $e'$ sur l'entrée $m$ et à la fin renvoie $0$. +Dire que $e\in M$ signifie que $e'$ ne termine pas sur $m$, donc +pouvoir semi-décider $M$ permet de résoudre algorithmiquement le +problème de l'arrêt, ce qui est impossible. + +\par} + +\smallskip + +\noindent Qui a raison ? Expliquer précisément quelle est l'erreur +(ou les erreurs) commise(s) par le raisonnement incorrect, et +détailler les éventuels passages incomplets dans le raisonnement +correct. + +\begin{corrige} +C'est Patrocle qui a raison ($M$ n'est pas semi-décidable). + +Le raisonnement d'Achille se fonde sur l'idée que le complémentaire de +« l'ensemble des programmes qui renvoient toujours la valeur $0$ » est +« l'ensemble des programmes qui renvoient parfois une valeur autre +que $0$ », ce qui oublie la possibilité que le programme ne termine +pas. C'est là la principale erreur (le reste est globalement +correct). + +L'argument de Patrocle, lui, est correct : il montre que si $M$ était +semi-décidable, le complémentaire du problème de l'arrêt (l'ensemble +des $e'$ qui ne terminent jamais) serait semi-décidable, ce qui n'est +pas le cas. (Le complémentaire du problème de l'arrêt n'est pas +semi-décidable, car s'il l'était, le problème de l'arrêt serait +décidable, vu qu'il est déjà semi-décidable.) On fait appel à des +fonctions constantes, et qui ne peuvent renvoyer que $0$ ou ne pas +terminer, mais ce n'est pas spécialement problématique. Parmi les +points qui méritent éventuellement d'être précisés, on peut mentionner +le fait que $e$ se déduise algorithmiquement de $e'$ et $m$. +\end{corrige} + + % % |