diff options
-rw-r--r-- | controle-20210618.tex | 672 | ||||
-rw-r--r-- | controle-20220616.tex | 674 | ||||
-rw-r--r-- | controle-20220825.tex | 683 | ||||
-rw-r--r-- | controle-20230615.tex | 870 | ||||
-rw-r--r-- | errata-notes-inf105.tex | 227 | ||||
-rw-r--r-- | exemples-automates.xoj | bin | 0 -> 310263 bytes | |||
-rwxr-xr-x | misc/quiz-extract-automata.pl | 53 | ||||
-rw-r--r-- | notes-inf105.tex | 90 | ||||
-rw-r--r-- | programme-inf105.tex | 35 | ||||
-rw-r--r-- | quiz-20220428.tex | 238 | ||||
-rw-r--r-- | quiz-20220602.tex | 432 | ||||
-rw-r--r-- | rattrapage-20230621.tex | 575 |
12 files changed, 4352 insertions, 197 deletions
diff --git a/controle-20210618.tex b/controle-20210618.tex new file mode 100644 index 0000000..aa30be9 --- /dev/null +++ b/controle-20210618.tex @@ -0,0 +1,672 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +\usepackage{hyperref} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +\newenvironment{commentaire}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}} +{{\hbox{}\nobreak\hfill\maltese}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% NOTE: compile dot files with +% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} +\ifcorrige +\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{18 juin 2021} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +\medbreak + +L'usage de tous les documents (notes de cours manuscrites ou +imprimées, feuilles d'exercices, livres) est autorisé. + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 1h30 + +Barème \emph{indicatif} : 8+7+5. + +\ifcorrige +Ce corrigé comporte 9 pages (page de garde incluse). +\else +Cet énoncé comporte 3 pages (page de garde incluse). +\fi + +\vfill + +{\tiny\noindent +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On considère +l'expression rationnelle $r := bb{*}a(a|b){*}$, et soit $L := L(r)$ le +langage qu'elle dénote (autrement dit, c'est le langage constitué des +mots qui commencent par un nombre $\geq 1$ de fois la lettre $b$, +immédiatement suivis par la lettre $a$, puis n'importe quoi). + +(0) Pour chacun des mots suivants, dire si oui ou non il appartient +à $L$ (c'est-à-dire s'il vérifie $r$) : $\varepsilon$ (le mot vide), +$a$, $b$, $ab$, $ba$, $bb$, $bab$, $bba$, $baba$. On ne demande pas +de justifier les réponses. + +\begin{corrige} +Les mots $\varepsilon$, $a$, $b$, $ab$ et $bb$ n'appartiennent pas +à $L$ ; les mots $ba$, $bab$, $bba$ et $baba$ appartiennent à $L$. +\end{corrige} + +\emph{Il est fortement conseillé, dans toutes les questions suivantes, + d'utiliser les mots qui viennent d'être listés pour vérifier les + automates successifs qu'on calculera.} (Par exemple, pour un +automate censé reconnaître le langage $L$, on vérifiera qu'il accepte +bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux +qu'on a identifiés comme n'appartement pas à $L$.) Les fautes qui +auraient dû être détectées par cette vérification pourront être plus +lourdement sanctionnées. + +(1) Traiter l'une \emph{ou} l'autre des questions suivantes : +(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ; +(ii) construire l'automate de Thompson de $r$, puis éliminer les +transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on +retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$ +l'automate ainsi obtenu. + +(Dans les deux cas, on obtient le même automate fini $\mathscr{A}_1$. +À défaut de donner l'automate de Glushkov ou de Thompson, donner un +NFA reconnaissant $L$ pourra apporter une partie des points.) + +\begin{corrige} +L'automate $\mathscr{A}_1$ trouvé est le suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$}; +\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$a$} (q4); +\draw[->] (q3) -- node[auto,below]{$b$} (q5); +\draw[->] (q4) to[loop above] node[auto]{$a$} (q4); +\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5); +\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4); +\draw[->] (q5) to[loop below] node[auto]{$b$} (q5); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(2) Déterminiser l'automate $\mathscr{A}_1$. On appellera +$\mathscr{A}_2$ l'automate en question. On rappelle qu'on attend ici +un automate fini \emph{déterministe complet}. + +\begin{corrige} +L'automate $\mathscr{A}_1$ est déjà déterministe, mais incomplet : +pour le transformer en automate déterministe complet, on se contente +pour obtenir l'automate $\mathscr{A}_2$ de lui ajouter un puits vers +lequel on fait pointer la seule transition manquante : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$}; +\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$}; +\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$a$} (q4); +\draw[->] (q3) -- node[auto,below]{$b$} (q5); +\draw[->] (q4) to[loop above] node[auto]{$a$} (q4); +\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5); +\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4); +\draw[->] (q5) to[loop below] node[auto]{$b$} (q5); +\draw[->] (q0) -- node[auto,swap]{$a$} (Sink); +\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(3) Minimiser l'automate $\mathscr{A}_2$. On appellera +$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du +langage $L$). + +\begin{corrige} +L'automate $\mathscr{A}_2$ est déterministe complet sans état +inaccessible. On commence l'algorithme de minimisation en séparant +les états finaux $\{3,4,5\}$ et non-finaux $\{0,1,2,\bot\}$. On +sépare ensuite ces derniers en deux classes, $\{1,2\}$ et $\{0,\bot\}$ +selon que la transition étiquetée $a$ conduit à un état final ou non. +Enfin, la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en +deux. Finalement, on aboutit aux classes suivantes : $\{0\}$, +$\{1,2\}$, $\{3,4,5\}$ et $\{\bot\}$ (qu'on rebaptise $0,1,3,\bot$ +respectivement), et à l'automate minimal $\mathscr{A}_3$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final] {$3$}; +\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3); +\draw[->] (q0) -- node[auto,swap]{$a$} (Sink); +\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(4) Déduire de $\mathscr{A}_3$ un automate fini déterministe complet +$\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$ +complémentaire de $L$. + +\begin{corrige} +Il suffit d'échanger les états finaux et non-finaux +dans $\mathscr{A}_3$, ce qui donne l'automate $\mathscr{A}_4$ +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,final,accepting below] {$1$}; +\node (q3) at (120bp,0bp) [draw,circle,state] {$3$}; +\node (qZ) at (0bp,-50bp) [draw,circle,final] {$Z$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3); +\draw[->] (q0) -- node[auto,swap]{$a$} (qZ); +\draw[->] (qZ) to[loop left] node[auto]{$a,b$} (qZ); +\end{tikzpicture} +\end{center} +(On a renommé l'état $\bot$ en $Z$ vu que ce n'est plus un puits sur +ce nouvel automate, en revanche $3$ en est un. Ces nom sont, bien +sûr, sans aucun impact sur le fonctionnement de l'automate.) +\end{corrige} + +(5) En appliquant l'algorithme d'élimination des états, déduire +de $\mathscr{A}_4$ une expression rationnelle $s$ dénotant le +langage $M$ (c'est-à-dire vérifiée exactement par les mots qui ne +vérifient pas $r$). +\begin{corrige} +Pour procéder à l'algorithme d'élimination des états, on commence par +donner à l'automate un unique état final sans aucune transition qui en +part, appelons-le $\infty$. On peut aussi d'ores et déjà éliminer +l'état $3$ qui est maintenant inutile, et remplacer les deux +transitions $Z\to Z$ étiquetées $a$ et $b$ par une seule +étiquetée $a|b$ (ce qui, dans un RNFA, revient au même) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (qZ) at (0bp,-50bp) [draw,circle] {$Z$}; +\node (final) at (60bp,-50bp) [draw,circle,final] {$\infty$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q0) -- node[auto,swap]{$a$} (qZ); +\draw[->] (qZ) to[loop left] node[auto]{$a|b$} (qZ); +\draw[->] (q0) -- node[auto]{$\varepsilon$} (final); +\draw[->] (q1) -- node[auto]{$\varepsilon$} (final); +\draw[->] (qZ) -- node[auto,below]{$\varepsilon$} (final); +\end{tikzpicture} +\end{center} +L'élimination de l'état $1$ conduit à remplacer la transition +$0\to\infty$ étiquetée $\varepsilon$ par $\varepsilon | bb{*}$, et +l'élimination de l'état $Z$ conduit à y ajouter $a(a|b){*}$. +Finalement, on a affaire à un automate ayant les seuls états $0$ +(initial) et $\infty$ (final) avec la seule transition $0\to\infty$ +étiquetée par l'expression rationnelle $s$ recherchée : +\[ +\varepsilon \,|\, bb{*} \,|\, a(a|b){*} +\] +qui dénote le langage $M$ complémentaire de $L$. (Autrement dit : un +mot qui \emph{n'est pas} un nombre $\geq 1$ de $b$ suivi d'un $a$ +suivi de n'importe quoi, c'est la même chose qu'un mot soit vide, soit +formé uniquement d'un nombre $\geq 1$ de $b$, soit d'un $a$ suivi de +n'importe quoi.) +\end{corrige} + + +% +% +% + +\exercice + +On considère la grammaire hors-contexte $G$ sur l'alphabet $\Sigma = +\{a,b,c\}$ ayant pour seul nonterminal son axiome $S$, et pour règles +\[ +S \rightarrow abc \;|\; aSbc \;|\; abSc +\] +On appellera « $0$ » la règle $S \rightarrow abc$, et « $1$ » la règle +$S \rightarrow aSbc$, et enfin « $2$ » la règle $S \rightarrow abSc$. + +(1) Donner un arbre d'analyse (= de dérivation) du mot $abaabcbcc$ +selon cette grammaire $G$. (On pourra d'abord lire les questions +suivantes si on a du mal à trouver comment dériver ce mot.) + +\begin{corrige} +L'arbre d'analyse est le suivant : +% S<a.b.S<a.S<a.b.c.>b.c.>c.> +\begin{center} +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (68.750bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (S1) at (95.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (a1) at (40.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a1); +\node (S2) at (80.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (a2) at (60.000bp,-90.000bp) [draw=none] {$a$}; \draw (S2) -- (a2); +\node (b1) at (80.000bp,-90.000bp) [draw=none] {$b$}; \draw (S2) -- (b1); +\node (c0) at (100.000bp,-90.000bp) [draw=none] {$c$}; \draw (S2) -- (c0); +\node (b2) at (120.000bp,-60.000bp) [draw=none] {$b$}; \draw (S1) -- (b2); +\node (c1) at (140.000bp,-60.000bp) [draw=none] {$c$}; \draw (S1) -- (c1); +\node (c2) at (160.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c2); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +On va maintenant montrer que $G$ est inambiguë. + +(2) Expliquer pourquoi tout mot non-vide du langage $L := L(G)$ +engendré par $G$ a nécessairement $a$ pour préfixe (i.e., commence par +la lettre $a$). + +\begin{corrige} +Les trois règles $0,1,2$ ont toutes le terminal $a$ comme premier +symbole de leur membre de droite. Le fils le plus à gauche de la +racine (étiquetée $S$) dans n'importe quel arbre d'analyse selon $G$ +est nécessairement étiqueté $a$, et le mot analysé commence donc +nécessairement par $a$. (Si on préfère, toute dérivation selon $G$ +commence par une règle produisant $a$ comme symbole le plus à gauche, +qui ne peut ensuite jamais être effacé ni réécrit puisqu'il s'agit +d'un terminal.) +\end{corrige} + +(3) Montrer que tout mot de $L$ dérivé en démarrant +par\footnote{C'est-à-dire : tout mot $w$ possédant une dérivation + selon $G$ de la forme $S \Rightarrow aSbc \mathrel{\Rightarrow^*} w$ + où $\mathrel{\Rightarrow^*}$ désigne une succession quelconque de + dérivations immédiates. Ou, ce qui revient au même (et on pourra + tenir ce point pour acquis) : tout mot $w$ possédant un arbre + d'analyse dont la racine a quatre fils étiquetés $a,S,b,c$ dans cet + ordre.} la règle $1$ a nécessairement $aa$ comme préfixe. Montrer +de même que tout mot de $L$ dérivé en démarrant par la règle $2$ a +nécessairement $aba$ comme préfixe. + +\begin{corrige} +Si dans un arbre d'analyse $\mathscr{T}$ selon $G$ la racine +(étiquetée $S$) a quatre fils étiquetés $a,S,b,c$ dans cet ordre +(i.e., en démarrant par la règle $1$), les descendants du deuxième +fils (celui étiqueté $S$, y compris lui-même) forment eux-mêmes un +arbre d'analyse $\mathscr{T}'$ selon $G$, dont le mot analysé $w'$ +commence par $a$ (d'après la question précédente), si bien que le mot +$w = aw'bc$ analysé par $\mathscr{T}$ commence par $aa$. (Avec la +notation qui sera introduite ci-dessous, on a $\mathscr{T} = +\mathbf{R}_1(\mathscr{T}')$.) + +Si on préfère : une dérivation de la forme $S \buildrel +1\over\Rightarrow aSbc \mathrel{\Rightarrow^*} w$ a nécessairement $w += aw'bc$ où $w'$ est le mot obtenu en appliquant les mêmes règles +à $S$, qui commence donc par $a$, si bien que $w$ commence par $aa$. + +Un raisonnement analogue conduit à conclure que tout mot dérivé en +démarrant par la règle $2$ a la forme $abw'c$ où $w'\in L$ donc +commence par $a$, si bien que le mot commence par $aba$. +\end{corrige} + +(4) En déduire comment, d'après les premières lettres d'un mot $w$ +de $L$, on peut savoir par quelle règle démarre nécessairement une +dérivation de $w$ selon $G$ (ou, ce qui revient au même, quels sont +les fils de la racine dans tout arbre d'analyse de $w$). + +\begin{corrige} +Si on appelle $L_0,L_1,L_2$ les parties de $L$ constituées des mots +ayant (au moins) une dérivation selon $G$ démarrant par les règles +$0,1,2$ respectivement, on a trivialement $L_0 = \{abc\}$ et on vient +de voir que les mots de $L_1$ ont $aa$ comme préfixe et ceux de $L_2$ +ont $aba$ comme préfixe. Notamment : +\begin{itemize} +\item $L_0,L_1,L_2$ sont disjoints (i.e., la règle par laquelle + démarre une dérivation de $w$ est déterminée par $w$), et +\item on peut savoir si un mot $w \in L$ appartient à $L_0$, $L_1$ + ou $L_2$ en regardant s'il commence par $abc$, $aa$ ou $aba$. +\end{itemize} +Ce qui répond à la question posée. +\end{corrige} + +(5) Connaissant tous les arbres d'analyse d'un mot $w$ selon $G$, +expliquer comment trouver tous les arbres d'analyse du mot $awbc$ +d'une part, et du mot $abwc$ d'autre part. + +\begin{corrige} +Afin de s'épargner des répétitions fastidieuses, on définit pour toute +la suite de ce corrigé des notations pour les arbres d'analyse +selon $G$ démarrant par les règles $0,1,2$ respectivement, à savoir : +\begin{itemize} +\item on notera $\mathbf{R}_0$ l'arbre d'analyse associé à la + règle $0$, c'est-à-dire l'arbre dont la racine, étiquetée $S$, a + exactement trois fils, qui sont des feuilles, et qui sont étiquetés + $a,b,c$ dans cet ordre ; +\item si $\mathscr{T}$ est un arbre d'analyse selon $G$, on notera + $\mathbf{R}_1(\mathscr{T})$ l'arbre d'analyse associé à la règle $1$ + suivie des règles décrites par $\mathscr{T}$, c'est-à-dire l'arbre + dont la racine, étiquetée $S$, a exactement quatre fils, étiquetés + $a,S,b,c$ dans cet ordre, où le premier et les deux derniers sont + des feuilles et où les descendants du second (y compris lui-même) + forment une copie de l'arbre d'analyse $\mathscr{T}$ ; +\item de façon analogue, si $\mathscr{T}$ est un arbre d'analyse + selon $G$, on notera $\mathbf{R}_2(\mathscr{T})$ l'arbre d'analyse + associé à la règle $2$ suivie des règles décrites par $\mathscr{T}$, + c'est-à-dire l'arbre dont la racine, étiquetée $S$, a exactement + quatre fils, étiquetés $a,b,S,c$ dans cet ordre, où les deux + premiers et le dernier sont des feuilles et où les descendants du + troisième (y compris lui-même) forment une copie de l'arbre + d'analyse $\mathscr{T}$. +\end{itemize} + +Soit graphiquement : +\begin{center} +\begin{tabular}{c|c|c} +$\mathbf{R}_0$&$\mathbf{R}_1(\mathscr{T})$&$\mathbf{R}_2(\mathscr{T})$\\ +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (20.000bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (c0) at (40.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c0); +\end{tikzpicture} +& +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (30.000bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S1) at (20.000bp,-30.000bp) [draw,circle] {$\mathscr{T}$}; \draw (S0) -- (S1); +\node (b0) at (40.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (c0) at (60.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c0); +\end{tikzpicture} +& +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (30.000bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (S1) at (40.000bp,-30.000bp) [draw,circle] {$\mathscr{T}$}; \draw (S0) -- (S1); +\node (c0) at (60.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c0); +\end{tikzpicture} +\end{tabular} +\end{center} +(par exemple, l'arbre d'analyse répondant à la question $1$ est +l'arbre $\mathbf{R}_2(\mathbf{R}_1(\mathbf{R}_0))$). + +Manifestement, tout arbre d'analyse selon $G$ est soit l'arbre +$\mathbf{R}_0$, soit de la forme $\mathbf{R}_1(\mathscr{T})$ ou +$\mathbf{R}_2(\mathscr{T})$ avec $\mathscr{T}$ un autre arbre +(strictement plus petit). + +Répondons maintenant à la question posée. + +Si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, alors +$\mathbf{R}_1(\mathscr{T})$ est un arbre d'analyse de $awbc$ (toujours +selon $G$). Mais réciproquement, comme $awbc$ commence par $aa$ +(i.e., a $aa$ pour préfixe), on a vu en (4) que toute dérivation du +mot $awbc$ selon $G$ démarre nécessairement par la règle $1$, +c'est-à-dire que tout arbre d'analyse de $awbc$ est de la +forme $\mathbf{R}_1(\mathscr{T})$, et $\mathscr{T}$ est alors +uniquement défini (comme ce qui descend du deuxième fils de la +racine). Bref : $\mathbf{R}_1$ définit une bijection entre les arbres +d'analyse de $w$ et ceux de $awbc$. + +De même, si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, +alors $\mathbf{R}_2(\mathscr{T})$ est un arbre d'analyse de $abwc$. +Mais réciproquement, comme $abwc$ commence par $aba$ (i.e., a $aba$ +pour préfixe), on a vu en (4) que toute dérivation du mot $abwc$ +selon $G$ démarre nécessairement par la règle $2$, c'est-à-dire que +tout arbre d'analyse de $abwc$ est de la +forme $\mathbf{R}_2(\mathscr{T})$, et $\mathscr{T}$ est alors +uniquement défini (comme ce qui descend du troisième fils de la +racine). Bref : $\mathbf{R}_2$ définit une bijection entre les arbres +d'analyse de $w$ et ceux de $awbc$. +\end{corrige} + +(6) En déduire que tout mot $w \in L$ possède un unique arbre +d'analyse selon $G$, et proposer (sur la base des questions +précédentes) un algorithme qui le calcule. + +\begin{corrige} +En reformulant les conclusions des questions suivantes, tout mot $w$ +de $L$ est dans un et un seul des trois cas suivants : +\begin{itemize} +\item soit $w$ est le mot $abc$ et son unique arbre d'analyse selon $G$ + est $\mathbf{R}_0$, +\item soit $w$ commence par $aa$ et alors $w$ est de la forme $aw'bc$ + et tout arbre d'analyse de $w$ selon $G$ est de la forme + $\mathbf{R}_1(\mathscr{T}')$ pour un unique arbre d'analyse + $\mathscr{T}'$ de $w'$, +\item soit $w$ commence par $aba$ et alors $w$ est de la forme $abw'c$ + et tout arbre d'analyse de $w$ selon $G$ est de la forme + $\mathbf{R}_2(\mathscr{T}')$ pour un unique arbre d'analyse + $\mathscr{T}'$ de $w'$. +\end{itemize} + +Il résulte par récurrence sur la longueur de $w \in L$ que $w$ a un +unique arbre d'analyse selon $G$ : en effet, dans le premier des trois +cas ci-dessus, $w$ a pour unique arbre d'analyse $\mathbf{R}_0$, et +dans les deux derniers cas on a $|w'| < |w|$ (précisément $|w'| = +|w|-3$), donc $w'$ a un unique arbre d'anayse $\mathscr{T}'$ selon $G$ +par l'hypothèse de récurrence, d'où il résulte que $w$ a lui aussi un +unique arbre d'analyse (à savoir $\mathbf{R}_1(\mathscr{T}')$ ou +$\mathbf{R}_2(\mathscr{T}')$). + +La grammaire $G$ est donc inambiguë. + +Cette démonstration est constructive, c'est-à-dire qu'on a +l'algorithme suivant qui analyse un mot $w$ et renvoie l'unique arbre +d'analyse de $w$ selon $G$ (s'il existe, ou signale une erreur +d'analyse dans le cas contraire) : +\begin{itemize} +\item si le mot $w$ à analyser est $abc$, renvoyer l'arbre + $\mathbf{R}_0$ ; +\item sinon, si $w$ commence par $aa$, vérifier qu'il termine par $bc$ + (sinon abandonner avec une erreur d'analyse), appeler $w'$ le mot + obtenu en effaçant le $a$ initial et le $bc$ final, appliquer + récursivement l'algorithme qu'on est en train de définir au + mot $w'$, appeler $\mathscr{T}'$ l'arbre d'analyse ainsi calculer, + et renvoyer $\mathbf{R}_1(\mathscr{T}')$ ; +\item sinon, si $w$ commence par $aba$, vérifier qu'il termine par $c$ + (sinon abandonner avec une erreur d'analyse), appeler $w'$ le mot + obtenu en effaçant le $ab$ initial et le $c$ final, appliquer + récursivement l'algorithme qu'on est en train de définir au + mot $w'$, appeler $\mathscr{T}'$ l'arbre d'analyse ainsi calculer, + et renvoyer $\mathbf{R}_2(\mathscr{T}')$ ; +\item dans tout autre cas (i.e., si $w$ n'est pas $abc$ et commence + par autre chose que $aa$ ou $aba$), abandonner avec une erreur + d'analyse. +\end{itemize} +(L'algorithme termine en temps fini parce que les appels récursifs se +font sur des mots de longueur strictement plus courte. Il s'agit d'un +algorithme par « descente récursive », qui se transforme facilement, +quitte à remplacer la pile des appels récursifs en une pile en tant +que structure de données, en un analyseur LL.) +\end{corrige} + + +% +% +% + +\exercice + +(Les deux questions suivantes sont indépendantes.) + +\smallskip + +(1) Le langage $\{a^n b^n c^n : n\in\mathbb{N}\}$ n'est pas +algébrique\footnote{Ce fait est démontré dans le poly, dans la section + consacrée au lemme de pompage pour les langages algébriques et comme + illustration de ce dernier ; on ne demande bien sûr pas ici de le + redémontrer.}. Est-il rationnel ? Est-il décidable ? Est-il +semi-décidable ? On justifiera soigneusement les réponses. + +\begin{corrige} +Le langage proposé n'est pas rationnel car il n'est pas algébrique. + +Il est décidable car il est évident qu'on peut algorithmiquement d'une +part vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci +correspond à l'expression rationnelle $a{*}b{*}c{*}$, c'est faisable +par automate fini) et d'autre part vérifier qu'il a autant de $a$ que +de $b$ que de $c$. + +Étant décidable, il est notamment semi-décidable. +\end{corrige} + +\smallskip + +(2) On rappelle la définition du problème de l'arrêt : c'est +l'ensemble $H$ des couples\footnote{Pour être rigoureux, on a fixé un + codage permettant de représenter les programmes $e$, les entrées $x$ + à ces programmes, et les couples $(e,x)$, comme des éléments + de $\mathbb{N}$ (ou bien de $\Sigma^*$ sur un alphabet + $\Sigma\neq\varnothing$ arbitraire). Il n'est pas nécessaire de + faire apparaître ce codage dans la description des algorithmes + proposés, qui peut rester informelle.} $(e,x)$ formés d'un programme +(= algorithme) $e$ et d'une entrée $x$, tels que l'exécution du +programme $e$ sur l'entrée $x$ termine en temps fini. On a vu en +cours que $H$ était semi-décidable mais non décidable. + +On considère l'ensemble $J$ des triplets $(e_1,e_2,x)$ tels que +$(e_1,x) \in H$ et $(e_2,x) \not\in H$. Autrement dit, le programme +$e_1$ termine en temps fini quand on l'exécute sur l'entrée $x$ mais +le programme $e_2$, lui, ne termine pas sur cette même entrée. +L'ensemble $J$ est-il décidable ? Semi-décidable ? On justifiera +soigneusement. + +\begin{corrige} +L'ensemble $J$ n'est pas semi-décidable. + +Pour le montrer, supposons par l'absurde qu'on dispose d'un algorithme +$T$ qui semi-décide $J$ (où « semi-décider » un ensemble $Z$ +signifie : terminer en renvoyant $1$ (=vrai) si l'entrée $z$ fournie +appartient à $Z$, et ne pas terminer sinon). Fixons une fois pour +toutes (le code d')un programme $f$ qui, donnée une entrée $x$, +termine immédiatement (en ignorant $x$). Alors trivialement $(f,x) +\in H$ quel que soit $x$ ; donc, par définition de $J$, on a $(f,e,x) +\in J$ si et seulement si $(e,h) \not \in H$. + +On considère alors l'algorithme $T'$, défini de la manière suivante : +donnés $(e,x)$, on applique l'algorithme $T$ (qu'on a supposé exister) +au triplet $(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in +J$), on renvoie $1$ (sinon, bien sûr, on ne termine jamais). Par +construction, $T'$ termine en renvoyant $1$ sur l'entrée $(e,x)$ si +$(f,e,x) \in J$, c'est-à-dire $(e,x) \not\in H$, et sinon il ne +termine pas. Ceci signifie que $T'$ semi-décide le complémentaire +de $H$. + +Or le complémentaire de $H$ n'est pas semi-décidable (car si le +complémentaire de $H$ était semi-décidable, on aurait à la fois $H$ et +son complémentaire semi-décidables, donc $H$ serait décidable, et on +sait qu'il ne l'est pas), donc un tel algorithme $T'$ ne peut pas +exister. C'est une contradiction : $J$ n'est donc pas semi-décidable. + +\textit{A fortiori}, $J$ n'est pas décidable. +\end{corrige} + + +% +% +% +\end{document} diff --git a/controle-20220616.tex b/controle-20220616.tex new file mode 100644 index 0000000..7439a45 --- /dev/null +++ b/controle-20220616.tex @@ -0,0 +1,674 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +\usepackage{hyperref} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +\newenvironment{commentaire}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}} +{{\hbox{}\nobreak\hfill\maltese}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% NOTE: compile dot files with +% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} +\ifcorrige +\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{16 juin 2022} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants (le premier teste +l'application d'algorithmes vus en cours, le second est de nature plus +théorique). Ils pourront être traités dans un ordre quelconque, mais +on demande de faire apparaître de façon très visible dans les copies +où commence chaque exercice. + +\medbreak + +Le sujet étant long pour le temps imparti, il ne sera pas nécessaire +de traiter toutes les questions pour obtenir la totalité des points. + +\medbreak + +L'usage de tous les documents (notes de cours manuscrites ou +imprimées, feuilles d'exercices, livres) est autorisé. + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 1h30 + +Barème \emph{indicatif} : autant de points pour chaque exercice. + +\ifcorrige +Ce corrigé comporte 9 pages (page de garde incluse). +\else +Cet énoncé comporte 4 pages (page de garde incluse). +\fi + +\vfill + +{\tiny\noindent +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On considère +l'expression rationnelle $r := a{*}b{*}a{*}$, et soit $L := L(r)$ le +langage qu'elle dénote. + +(0) Pour chacun des mots suivants, dire si oui ou non il appartient +à $L$ (c'est-à-dire s'il vérifie $r$) : $\varepsilon$ (le mot vide), +$a$, $b$, $ab$, $ba$, $aa$, $aba$, $bab$, $abab$. On ne demande pas +de justifier les réponses. + +\begin{corrige} +Les mots $\varepsilon$, $a$, $b$, $ab$, $ba$, $aa$, $aba$ +appartiennent à $L$ ; les mots $bab$ et $baba$ n'appartiennent pas +à $L$. +\end{corrige} + +\emph{Il est fortement conseillé, dans toutes les questions suivantes, + d'utiliser les mots qui viennent d'être listés pour vérifier les + automates successifs qu'on calculera.} (Par exemple, pour un +automate censé reconnaître le langage $L$, on vérifiera qu'il accepte +bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux +qu'on a identifiés comme n'appartement pas à $L$.) Les fautes qui +auraient dû être détectées par cette vérification pourront être plus +lourdement sanctionnées. + +(1) Traiter l'une \emph{ou} l'autre des questions suivantes : +(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ; +(ii) construire l'automate de Thompson de $r$, puis éliminer les +transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on +retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$ +l'automate ainsi obtenu. + +(Dans les deux cas, on obtient le même automate fini $\mathscr{A}_1$, +et il a $4$ états. À défaut de donner l'automate de Glushkov ou de +Thompson, donner un NFA reconnaissant $L$ pourra apporter une partie +des points.) + +\begin{corrige} +L'automate $\mathscr{A}_1$ trouvé est le suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,final,accepting below] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,final] {$3$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q0) to[out=295,in=245] node[auto,below]{$b$} (q2); +\draw[->] (q1) to[out=295,in=245] node[auto,below]{$a$} (q3); +\draw[->] (q0) to[out=270,in=270] node[auto,below]{$a$} (q3); +\end{tikzpicture} +\end{center} +(on remarquera notamment que tous ses états sont finaux). +\end{corrige} + +(2) Déterminiser l'automate $\mathscr{A}_1$. On appellera +$\mathscr{A}_2$ l'automate en question. On rappelle qu'on attend ici +un automate fini \emph{déterministe complet} ; pour information, il a +$5$ états. + +\begin{corrige} +L'automate $\mathscr{A}_2$ trouvé est le suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$\scriptstyle\{0\}$}; +\node (q1) at (30bp,52bp) [draw,circle,state,final,accepting right] {$\scriptstyle\{1,3\}$}; +\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{2\}$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{3\}$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (q0) -- node[auto]{$b$} (q2); +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto,near end]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (qF); +\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(3) Minimiser l'automate $\mathscr{A}_2$. On appellera +$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du +langage $L$). Pour information, cet automate a $4$ états : pour la +commodité du correcteur, on les appellera $1,2,3,\bot$ dans l'ordre +dans lequel ils sont parcourus lorsque l'automate consomme le +mot $bab$. + +\begin{corrige} +L'automate $\mathscr{A}_2$ est déterministe complet sans état +inaccessible. On commence l'algorithme de minimisation en séparant +les états finaux $\{0\},\{1,3\},\{2\},\{3\}$ et l'état +non-final $\varnothing$. On sépare ensuite les premiers selon que la +transition étiquetée $b$ conduit à un état non-final, ce qui +sépare $\{3\}$ du reste, et enfin selon que la transition +étiquetée $a$ conduit à cet état $\{3\}$, ce qui sépare $\{2\}$ du +reste. Finalement, on aboutit aux classes suivantes : $\{0\} \equiv +\{1,3\}$, $\{2\}$, $\{3\}$ et $\varnothing$ (qu'on rebaptise +$1,2,3,\bot$ respectivement), et à l'automate minimal $\mathscr{A}_3$ +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$}; +\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$}; +\draw[->] (q1) to[loop above] node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (qF); +\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(4) Donner de même l'automate minimal $\mathscr{A}_4$ du langage $L' +:= L(r')$ dénoté par l'expression rationnelle $r' := b{*}a{*}b{*}$. +Comme cette expression, et donc cet automate, sont simplement obtenus +en échangeant $a$ et $b$ par rapport à ce qui précède, on donnera +directement l'automate sans passer par les questions intermédiaires. + +\begin{corrige} +L'automate minimal $\mathscr{A}_4$ de $L'$ s'obtient simplement en +échangeant $a$ et $b$ dans $\mathscr{A}_3$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$}; +\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$}; +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$a$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$a$} (q2); +\draw[->] (q2) -- node[auto]{$b$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$b$} (q3); +\draw[->] (q3) -- node[auto]{$a$} (qF); +\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(5) En utilisant une construction de type « automate produit », donner +un automate déterministe complet $\mathscr{A}_5$, ayant $4\times 4 = +16$ états, qui reconnaît le langage $M := L \cap L'$ (constitué des +mots vérifiant à la fois $r$ et $r'$). On prendra garde pour la +question suivante au fait que cet automate possède des états +inaccessibles. + +\begin{corrige} +En prenant le produit des automates +$\mathscr{A}_3$ et $\mathscr{A}_4$, on aboutit à l'automate suivant +(où on a noté $q,q'$ l'état correspondant au couple $(q,q')$ d'un état +$q$ de $\mathscr{A}_3$ et $q'$ de $\mathscr{A}_4$ ; par exemple, +$\delta((1,1),a) = (1,2)$ car $\delta_{\mathscr{A}_3}(1,a) = 1$ et +$\delta_{\mathscr{A}_4}(1,a) = 2$) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q11) at (0bp,0bp) [draw,circle,state,initial,accepting by double] {\footnotesize$1,1$}; +\node (q12) at (60bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,2$}; +\node (q13) at (120bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,3$}; +\node (q1F) at (180bp,0bp) [draw,circle,state] {\footnotesize$1,\bot$}; +\node (q21) at (0bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,1$}; +\node (q22) at (60bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,2$}; +\node (q23) at (120bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,3$}; +\node (q2F) at (180bp,-60bp) [draw,circle,state] {\footnotesize$2,\bot$}; +\node (q31) at (0bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,1$}; +\node (q32) at (60bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,2$}; +\node (q33) at (120bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,3$}; +\node (q3F) at (180bp,-120bp) [draw,circle,state] {\footnotesize$3,\bot$}; +\node (qF1) at (0bp,-180bp) [draw,circle,state] {\footnotesize$\bot,1$}; +\node (qF2) at (60bp,-180bp) [draw,circle,state] {\footnotesize$\bot,2$}; +\node (qF3) at (120bp,-180bp) [draw,circle,state] {\footnotesize$\bot,3$}; +\node (qFF) at (180bp,-180bp) [draw,circle,state] {\footnotesize$\bot,\bot$}; +\draw[->] (q11) -- node[auto]{$b$} (q21); +\draw[->] (q11) -- node[auto]{$a$} (q12); +\draw[->] (q12) -- node[auto]{$b$} (q23); +\draw[->] (q12) to[loop above] node[auto]{$a$} (q12); +\draw[->] (q13) -- node[auto]{$b$} (q23); +\draw[->] (q13) -- node[auto]{$a$} (q1F); +\draw[->] (q1F) -- node[auto]{$b$} (q2F); +\draw[->] (q1F) to[loop right] node[auto]{$a$} (q1F); +\draw[->] (q21) to[loop left] node[auto]{$b$} (q21); +\draw[->] (q21) -- node[auto]{$a$} (q32); +\draw[->] (q22) -- node[auto]{$b$} (q23); +\draw[->] (q22) -- node[auto]{$a$} (q32); +\draw[->] (q23) to[loop right] node[auto]{$b$} (q23); +\draw[->] (q23) -- node[auto]{$a$} (q3F); +\draw[->] (q2F) to[loop right] node[auto]{$b$} (q2F); +\draw[->] (q2F) -- node[auto]{$a$} (q3F); +\draw[->] (q31) -- node[auto]{$b$} (qF1); +\draw[->] (q31) -- node[auto]{$a$} (q32); +\draw[->] (q32) -- node[auto]{$b$} (qF3); +\draw[->] (q32) to[loop below] node[auto]{$a$} (q32); +\draw[->] (q33) -- node[auto]{$b$} (qF3); +\draw[->] (q33) -- node[auto]{$a$} (q3F); +\draw[->] (q3F) -- node[auto]{$b$} (qFF); +\draw[->] (q3F) to[loop right] node[auto]{$a$} (q3F); +\draw[->] (qF1) to[loop below] node[auto]{$b$} (qF1); +\draw[->] (qF1) -- node[auto]{$a$} (qF2); +\draw[->] (qF2) -- node[auto]{$b$} (qF3); +\draw[->] (qF2) to[loop below] node[auto]{$a$} (qF2); +\draw[->] (qF3) to[loop below] node[auto]{$b$} (qF3); +\draw[->] (qF3) -- node[auto]{$a$} (qFF); +\draw[->] (qFF) to[loop below] node[auto]{$a,b$} (qFF); +\end{tikzpicture} +\end{center} +Pour plus de lisibilité, on a ici noté les états finaux en les +entourant deux fois plutôt qu'avec une flèche sortante. +\end{corrige} + +(6) Minimiser l'automate $\mathscr{A}_5$. On appellera +$\mathscr{A}_6$ l'automate minimal ainsi obtenu (automate canonique du +langage $M = L \cap L'$). Pour information, cet automate a $6$ états. + +\begin{corrige} +On commence par ne conserver que les états accessibles depuis l'état +initial, c'est-à-dire ceux étiquetés $(1,1)$, $(1,2)$, $(2,1)$, +$(2,3)$, $(3,2)$, $(3,\bot)$, $(\bot,3)$ et $(\bot,\bot)$ dans la +représentation ci-dessus, pour avoir un automate déterministe complet +sans état inaccessible. On applique ensuite l'algorithme de +minimisation de manière semblable à la question (3) : les états +non-finaux vont toujours rester groupés, et les états finaux sont +séparés un par un. Finalement, on aboutit à l'automate +$\mathscr{A}_6$ suivant comme automate minimal du langage $M$ (on a +rebaptisé les états ainsi : $(1,1)\rightsquigarrow 1$, +$(2,1)\rightsquigarrow 2$, $(3,2)\rightsquigarrow 3$, +$(1,2)\rightsquigarrow 2'$, $(2,3)\rightsquigarrow 3'$, et +$(3,\bot)\equiv (\bot,3) \equiv (\bot,\bot) \rightsquigarrow \bot$) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$}; +\node (q2a) at (60bp,42bp) [draw,circle,state,final,accepting below] {$2'$}; +\node (q3a) at (120bp,42bp) [draw,circle,state,final,accepting below] {$3'$}; +\node (q2) at (60bp,-42bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (120bp,-42bp) [draw,circle,state,final,accepting below] {$3$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$}; +\draw[->] (q1) -- node[auto]{$a$} (q2a); +\draw[->] (q1) -- node[auto,below]{$b$} (q2); +\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a); +\draw[->] (q2a) -- node[auto]{$b$} (q3a); +\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a); +\draw[->] (q3a) -- node[auto]{$a$} (qF); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto,below]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto,below]{$b$} (qF); +\draw[->] (qF) to[loop right] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(7) En appliquant l'algorithme d'élimination des états, déduire +de $\mathscr{A}_6$ une expression rationnelle $s$ dénotant le +langage $M$. Pour obtenir une expression raisonnablement simple, on +recommande d'éliminer les états en commençant par ceux qui sont à la +distance la plus éloignée de l'état initial. + +\begin{corrige} +On commence par effacer l'état puits (qui ne sert à rien) et par créer +un unique état final sans transition qui en parte : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$}; +\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$}; +\node (q3a) at (120bp,42bp) [draw,circle,state] {$3'$}; +\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$}; +\node (q3) at (120bp,-42bp) [draw,circle,state] {$3$}; +\node (qT) at (180bp,0bp) [draw,circle,state,final] {$\infty$}; +\draw[->] (q1) -- node[auto]{$a$} (q2a); +\draw[->] (q1) -- node[auto,below]{$b$} (q2); +\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a); +\draw[->] (q2a) -- node[auto]{$b$} (q3a); +\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a); +\draw[->] (q2a) -- node[auto,below]{$\varepsilon$} (qT); +\draw[->] (q3a) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q2) to[loop below] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto,below]{$a$} (q3); +\draw[->] (q3) to[loop below] node[auto]{$a$} (q3); +\draw[->] (q2) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q3) -- node[auto,below]{$\varepsilon$} (qT); +\end{tikzpicture} +\end{center} + +On peut alors éliminer les états $3$ et $3'$ (il n'y a pas +d'interaction entre eux) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$}; +\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$}; +\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$}; +\node (qT) at (120bp,0bp) [draw,circle,state,final] {$\infty$}; +\draw[->] (q1) -- node[auto]{$a$} (q2a); +\draw[->] (q1) -- node[auto,below]{$b$} (q2); +\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a); +\draw[->] (q2a) -- node[auto]{$\varepsilon|bb{*}$} (qT); +\draw[->] (q2) to[loop below] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto,below,near end]{$\varepsilon|aa{*}$} (qT); +\end{tikzpicture} +\end{center} + +Et finalement, en éliminant les états $2$ et $2'$, on trouve +l'expression rationnelle suivante qui dénote le langage $M$ : +\[ +\varepsilon\,|\,aa{*}(\varepsilon|bb{*})\,|\,bb{*}(\varepsilon|aa{*}) +\] +(il y a bien sûr d'autres écritures possibles ; par exemple, si on +élimine d'abord $2$ et $2'$ puis $3$ et $3'$ on obtient : +$\varepsilon\,|\,aa{*}\,|\,bb{*}\,|\,aa{*}bb{*}\,|\,bb{*}aa{*}$ ; +l'expression rationnelle $\varepsilon\,|\,aa{*}b{*}\,|\,bb{*}a{*}$ est +encore équivalente, mais elle ne s'obtient pas par la procédure +d'élimination des états). +\end{corrige} + + +% +% +% + +\exercice + +Les parties (A), (B) et (C) de cet exercice sont indépendantes. On ne +demande pas de justifications très longues. + +\medskip + +\textbf{(A)} On se propose de montrer que la question de savoir si +une grammaire hors contexte $G$ (sur un alphabet $\Sigma$ fixé) +vérifie $L(G) \neq \varnothing$ est décidable. Autrement dit, on +veut montrer qu'il existe un algorithme qui prend en entrée une +grammaire hors contexte $G$, termine toujours en temps fini, et +renvoie « vrai » si $L(G) \neq \varnothing$ et « faux » si $L(G) = +\varnothing$. + +(1) Expliquer pourquoi $L(G) \neq \varnothing$ si et seulement si il +existe un arbre d'analyse $\mathscr{T}$ pour $G$. (Un « arbre +d'analyse pour $G$ » désigne un arbre d'analyse d'un mot quelconque +selon $G$.) + +\begin{corrige} +Tout mot de $L(G)$ a (au moins) un arbre d'analyse pour $G$, et tout +arbre d'analyse pour $G$ est l'arbre d'analyse d'un mot de $L(G)$ : +ainsi, si $L(G) \neq \varnothing$, il existe un arbre d'analyse +pour $G$, et si $L(G) = \varnothing$ il n'existe pas d'arbre d'analyse +pour $G$. +\end{corrige} + +$\bullet$ Pour les questions suivantes, on introduit la terminologie +suivante : si $\mathscr{T}$ est un arbre et $n$ un nœud (=sommet) +de $\mathscr{T}$, on dit qu'un nœud $n'$ est un \textbf{descendant} de +$n$ lorsque $n'$ est soit égal à $n$, soit est un fils de $n$, soit +est un fils d'un fils de $n$, etc., à n'importe quelle profondeur. +L'ensemble des descendants de $n$ (y compris $n$ lui-même) est donc un +arbre ayant $n$ pour racine, qu'on appelle \textbf{sous-arbre qui + descend} de $n$. + +(2) Montrer que s'il existe un arbre d'analyse $\mathscr{T}$ pour $G$, +il en existe un vérifiant la propriété additionnelle suivante : +($\dagger$) « si un nœud $n$ est étiqueté par un nonterminal $X$, +alors aucun nœud $n' \neq n$ descendant de $n$ ne porte la même +étiquette $X$ ». + +\textit{Indication.}\quad Pour cela, on pourra remarquer que si un +arbre $\mathscr{T}$ ne vérifie pas ($\dagger$), on peut en construire +un autre ayant strictement moins de nœuds, en remplaçant le sous-arbre +qui descend de $n$ par celui qui descend de $n'$, et expliquer +pourquoi c'est encore un arbre d'analyse pour $G$ si $\mathscr{T}$ en +est un (pas nécessairement du même mot). + +\begin{corrige} +Si $\mathscr{T}$ est un arbre d'analyse pour $G$ dans lequel un nœud +$n'$ descendant d'un autre nœud $n$ est étiqueté par le même +symbole $X$, alors on peut fabriquer un arbre $\mathscr{T}'$ en +remplaçant le sous-arbre qui descend de $n$ par celui qui descend +de $n'$. Cet arbre $\mathscr{T}'$ a strictement moins de nœuds +que $\mathscr{T}$ car ses nœuds sont exactement ceux de $\mathscr{T}$ +à l'exception de ceux qui descendent de $n$ mais pas de $n'$. Par +ailleurs, c'est toujours un arbre d'analyse pour $G$ car chaque nœud a +des fils étiquetés exactement de la même manière (le seul pour lequel +ce n'est pas évident est le nœud parent de $n$, mais c'est bien vrai +car $n'$ et $n$ ont la même étiquette $X$). + +Si on considère maintenant $\mathscr{T}$ l'arbre d'analyse pour $G$ +ayant le nombre minimal de nœuds, il vérifie forcément ($\dagger$), +sans quoi la construction qu'on vient de donner produirait un arbre +$\mathscr{T}'$ ayant strictement moins de nœuds, contredisant la +minimalité. Il existe donc bien un arbre d'analyse pour $G$ +vérifiant ($\dagger$) (dès lors qu'il existe un arbre d'analyse +pour $G$ tout court). +\end{corrige} + +$\bullet$ Pour la question suivante, on dira qu'un arbre $\mathscr{T}$ +est de \textbf{valence} $\leq k$ lorsque chaque nœud de $\mathscr{T}$ +a au plus $k$ fils. + +(3) Montrer que, quels que soient les entiers naturels $k$ et $m$, il +n'y a qu'un nombre fini d'arbres de valence $\leq k$, dont les sommets +sont étiquetés par des étiquettes prises dans un ensemble +$\{Z_1,\ldots,Z_m\}$ de cardinal $m$, et vérifiant la propriété +($\dagger$) de la question précédente. Plus précisément, on pourra +montrer que le nombre de tels arbres est donné par $N(k,m)$ défini par +la récurrence $N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$ (et $N(k,0) = +0$) en considérant l'étiquette de la racine (parmi $m$ possibles) et +les $r \leq k$ sous-arbres qui descendent de ses fils. + +\begin{corrige} +Un arbre $\mathscr{T}$ de valence $\leq k$ vérifiant ($\dagger$) et +dont les étiquettes sont prises parmi $\{Z_1,\ldots,Z_m\}$ s'obtient +en choisissant l'étiquette $Z_i$ de la racine parmi $m$ possibles, le +nombre $0\leq r\leq k$ de fils de la racine, et les sous-arbres +$\mathscr{T}_1,\ldots,\mathscr{T}_r$ qui en descendent, qui sont +eux-mêmes des arbres de valence $\leq k$ vérifiant ($\dagger$) et dont +les étiquettes sont prises parmi $\{Z_1,\ldots,Z_m\} \setminus +\{Z_i\}$, c'est-à-dire parmi $m-1$ possibles. Par récurrence sur $m$, +on montre donc que ce nombre est fini, et précisément qu'il vérifie +$N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$. +\end{corrige} + +(4) En déduire un algorithme répondant à la question posée. + +\textit{Indication.}\quad Si $k$ est la longueur maximale d'une +production de la grammaire $G$, on pourra chercher à construire tous +les arbres de valence $\leq k$, étiquetés par des terminaux ou +nonterminaux ou $\varepsilon$, vérifiant de plus la +propriété ($\dagger$), et regarder s'il y a un arbre d'analyse parmi +eux. + +\begin{corrige} +Si $k$ est la longueur maximale d'une production de la grammaire $G$ +et $m$ le nombre d'étiquettes possibles d'un arbre d'analyse selon $G$ +(c'est-à-dire le nombre de nonterminaux plus le nombre de terminaux +plus $1$ pour $\varepsilon$, mais peu importe), on commence par +énumérer tous les arbres de valence $\leq k$, étiquetés par les tokens +en question, ce qui est possible d'après la question précédente (et +effectif avec la récursion évidente sur $m$). Il suffit ensuite de +tester tous ces arbres concevables et de vérifie si, à chaque nœud, +les contraintes imposées à un arbre d'analyse sont vérifiées. Soit on +trouve un arbre d'analyse pour $G$, auquel cas on a montré $L(G) \neq +\varnothing$ et on peut répondre « vrai » ; soit il n'y a aucun arbre +d'analyse pour $G$ vérifiant ($\dagger$), donc aucun d'arbre d'analyse +pour $G$ d'après la question (2), donc $L(G) = \varnothing$ +d'après (1) et on peut répondre « faux ». +\end{corrige} + +\medbreak + +\textbf{(B)} Montrer que la question de savoir si (pour un alphabet +$\Sigma$ fixé) une grammaire hors contexte $G$ vérifie $L(G) \neq +\Sigma^*$, est semi-décidable. Autrement dit, montrer qu'il existe un +algorithme qui prend en entrée une grammaire hors contexte $G$, +termine en temps fini et renvoie « vrai » si $L(G) \neq \Sigma^*$, et +ne termine pas si $L(G) = \Sigma^*$. + +\textit{Indication.}\quad On pourra pour cela énumérer tous les mots +possibles à la recherche d'un mot qui \emph{n'appartient pas} +à $L(G)$, et utiliser le fait que tester si $w \in L(G)$ est +décidable. + +\begin{corrige} +L'algorithme suivant convient : énumérer tous les mots $w \in +\Sigma^*$ et, pour chacun, utiliser la procédure de décision connue +pour déterminer en temps fini si $w \in L(G)$. Si ce n'est pas le +cas, on termine immédiatement en renvoyant « vrai » (on a $L(G) \neq +\Sigma^*$) ; si c'est le cas, on continue (on passe au mot suivant). +Cet algorithme termine (et renvoie « vrai » dans ce cas) exactement +lorsque $L(G) \neq \Sigma^*$ : il montre donc la semi-décidabilité du +problème considéré. +\end{corrige} + +\medbreak + +\textbf{(C)} (1) Montrer qu'il existe un algorithme qui, donnés une +expression rationnelle $r_1$ et une grammaire hors contexte $G_1$ (sur +un même alphabet $\Sigma$), calcule (= renvoie) une grammaire hors +contexte $G_2$ telle que $L(G_2) = L(G_1) \cup (\Sigma^* \setminus +L(r_1))$. + +\begin{corrige} +D'après divers résultats du cours : donnée une expression rationnelle +$r_1$, on sait calculer algorithmiquement un NFA $A_1$ tel que $L(r_1) += L(A_1)$ (par exemple avec la construction de Glushkov), on sait +calculer algorithmiquement un DFA $A_2$ tel que $L(A_1) = L(A_2)$ (en +déterminisant $A_1$), on sait calculer algorithmiquement un DFA $A_2$ +tel que $L(A_3) = \Sigma^* \setminus L(A_2)$ (en échangeant états +finaux et non-finaux), on sait calculer algorithmiquement une +grammaire hors contexte $G_3$ telle que $L(G_3) = L(A_3)$ (en +construisant une grammaire régulière), et à partir de $G_1$ et $G_3$ +on sait calculer algorithmiquement une grammaire hors contexte $G_2$ +telle que $L(G_2) = L(G_1) \cup L(G_3)$ (stabilité algorithmique des +langages algébriques par union) : on a alors $L(G_2) = L(G_1) \cup +(\Sigma^* \setminus L(r_1))$ comme annoncé. +\end{corrige} + +(2) On \underline{admet} que le problème suivant n'est pas décidable +(pour un alphabet $\Sigma$ fixé de cardinal $\#\Sigma \geq 2$) : +donnés $G$ une grammaire hors contexte et $r$ une expression +rationnelle, savoir si $L(r) \subseteq L(G)$. En déduire que le +problème suivant (qui en est un cas particulier) n'est lui-même pas +décidable : donnée $G$ une grammaire hors contexte, savoir si $L(G) = +\Sigma^*$. + +\textit{Indication.}\quad Pour cela, on pourra supposer par l'absurde +que le problème de reconnaître si $L(G) = \Sigma^*$ est décidable et, +donnés $G_1$ et $r_1$, construire algorithmiquement une grammaire hors +contexte $G_2$ telle que $L(G_2) = \Sigma^*$ si et seulement si +$L(r_1) \subseteq L(G_1)$. + +\begin{corrige} +Supposons par l'absurde qu'on dispose d'un algorithme $\mathfrak{A}$ +qui prend une grammaire hors contexte $G$ en entrée et décide si $L(G) += \Sigma^*$. Considérons l'algorithme suivant qui prend en entrée une +grammaire hors contexte $G_1$ et une expression rationnelle $r_1$ : on +commence par calculer une grammaire $G_2$ telle que $L(G_2) = L(G_1) +\cup (\Sigma^* \setminus L(r_1))$ comme expliqué en question (1), et +on applique à $G_2$ l'algorithme $\mathfrak{A}$ qu'on a supposé +exister pour décider si $L(G_2) = \Sigma^*$. Comme $L(G_2) = L(G_1) +\cup (\Sigma^* \setminus L(r_1))$, dont le complémentaire est $L(r_1) +\setminus L(G_1)$, on a $L(G_2) = \Sigma^*$ si et seulement si $L(r_1) +\subseteq L(G_1)$ : on peut donc renvoyer « vrai » dans ce cas et +« faux » sinon. Ceci montre l'existence d'un algorithme décidant si +$L(r_1) \subseteq L(G_1)$, ce qui est impossible (résultat admis). +C'est donc que l'hypothèse de l'existence de $\mathfrak{A}$ était +absurde, et le problème en question n'est pas décidable. +\end{corrige} + + +% +% +% +\end{document} diff --git a/controle-20220825.tex b/controle-20220825.tex new file mode 100644 index 0000000..c3cf461 --- /dev/null +++ b/controle-20220825.tex @@ -0,0 +1,683 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +\usepackage{hyperref} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +\newenvironment{commentaire}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}} +{{\hbox{}\nobreak\hfill\maltese}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% NOTE: compile dot files with +% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} +\ifcorrige +\title{INF105\\Contrôle de rattrapage — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de rattrapage\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{25 août 2022} +\maketitle + +% NOTE: Initially copied from controle-20180206.tex + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +\medbreak + +Documents autorisés : uniquement une feuille A4 recto-verso +(manuscrite ou typographiée). + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 1h30 + +Barème \emph{indicatif} : 7 points par exercice + +\ifcorrige +Ce corrigé comporte 9 pages (page de garde incluse) +\else +Cet énoncé comporte 4 pages (page de garde incluse) +\fi + +\vfill + +{\tiny\noindent +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On s'intéresse au +langage $L$ formé des mots (éléments de $\Sigma^*$) ayant $aa$ ou $bb$ +comme facteur (c'est-à-dire contenant deux $a$ consécutifs, ou bien +deux $b$ consécutifs), ainsi qu'à son +complémentaire $M := \Sigma^* \setminus L$. + +(1) Donner une expression rationnelle dénotant $L$. + +\begin{corrige} +Le langage des mots contenant deux $a$ consécutifs est dénoté par +l'expression rationnelle $(a|b){*}\,aa\,(a|b){*}$, et celui des mots +contenant deux $b$ consécutifs par $(a|b){*}\,bb\,(a|b){*}$. On peut +donc proposer l'expression rationnelle $(a|b){*}\,aa\,(a|b){*} \; | \; +(a|b){*}\,bb\,(a|b){*}$ ou encore, si on préfère, +$(a|b){*}\,(aa|bb)\,(a|b){*}$. +\end{corrige} + +(2) \emph{Indépendamment} de la question (1), expliquer brièvement pourquoi +l'automate $\mathscr{A}_2$ suivant reconnaît le langage $L$ : + +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (A) at (70bp,35bp) [draw,circle,state] {$A$}; +\node (B) at (70bp,-35bp) [draw,circle,state] {$B$}; +\node (T) at (140bp,0bp) [draw,circle,state,final] {$T$}; +\draw [->] (S) to[loop above] node[auto] {$a,b$} (S); +\draw [->] (S) -- node[auto,near end] {$a$} (A); +\draw [->] (S) -- node[auto] {$b$} (B); +\draw [->] (T) to[loop above] node[auto] {$a,b$} (T); +\draw [->] (A) -- node[auto,near start] {$a$} (T); +\draw [->] (B) -- node[auto] {$b$} (T); +\end{tikzpicture} +\end{center} + +De quelle sorte d'automate s'agit-il ? (DFA ? NFA ?...) + +\begin{corrige} +Un chemin de l'unique état initial $S$ à l'unique état final $T$ de +$\mathscr{A}_2$ doit passer soit par l'état $A$ soit par l'état $B$, +donc la lecture de ses étiquettes contient le facteur $aa$ +(correspondant aux transitions $S\to A$ et $A\to T$) ou $bb$ ; et +réciproquement, un mot contenant le facteur $aa$ ou $bb$ peut se lire +en suivant un chemin de $S$ à $T$ dans l'automate (en plaçant le +facteur $aa$ au niveau des transitions $S\to A$ et $A\to T$ ou de +façon analogue pour $bb$). + +Il s'agit là d'un automate non déterministe (l'état $S$ a plusieurs +transitions sortantes étiquetées par $a$), mais sans transitions +spontanées ou en abrégé, NFA. +\end{corrige} + +(3) Déterminiser (si nécessaire) l'automate $\mathscr{A}_2$ représenté +en (2) ; on appellera $\mathscr{A}_3$ l'automate résultant. + +\begin{corrige} +En notant $S$, $SA$, $SB$, $SAT$ et $SBT$ les états de l'automate +déterministe $\mathscr{A}_3$ qui correspondent aux ensembles d'états +de l'automate $\mathscr{A}_2$ donnés par les lettres en question, la +déterminisation conduit à l'automate $\mathscr{A}_3$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$}; +\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$}; +\node (SAT) at (140bp,35bp) [draw,circle,state,final] {$SAT$}; +\node (SBT) at (140bp,-35bp) [draw,circle,state,final] {$SBT$}; +\draw [->] (S) -- node[auto,near end] {$a$} (SA); +\draw [->] (S) -- node[auto,below] {$b$} (SB); +\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB); +\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA); +\draw [->] (SA) -- node[auto] {$a$} (SAT); +\draw [->] (SB) -- node[auto,below] {$b$} (SBT); +\draw [->] (SAT) to[out=300,in=60] node[auto] {$b$} (SBT); +\draw [->] (SBT) to[out=120,in=240] node[auto] {$a$} (SAT); +\draw [->] (SAT) to[loop above] node[auto] {$a$} (SAT); +\draw [->] (SBT) to[loop below] node[auto] {$b$} (SBT); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(4) Minimiser (si nécessaire) l'automate $\mathscr{A}_3$ obtenu +en (3) ; on appellera $\mathscr{A}_4$ l'automate minimal (=canonique) +résultant. + +\begin{corrige} +On part bien d'un automate $\mathscr{A}_3$ déterministe complet sans +état inaccessible. La première étape de l'algorithme de minimisation +sépare deux classes d'états : $S,SA,SB$ (non finaux) d'une part et +$SAT,SBT$ de l'autre. Ensuite on sépare $S$ et $SA$ et $SB$ (car le +premier ne conduit qu'à des états non finaux, le deuxième conduit à un +état final par la transition étiquetée $a$, et le troisième conduit à +un état final par la transition étiquetée $b$). Les étapes suivantes +ne conduisent pas à d'autres séparations d'états. On obtient +finalement un automate $\mathscr{A}_4$ à quatre états, qu'on peut +appeler $S,SA,SB,U$ où $U$ est la classe de $SAT$ et $SBT$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$}; +\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$}; +\node (U) at (140bp,0bp) [draw,circle,state,final] {$U$}; +\draw [->] (S) -- node[auto,near end] {$a$} (SA); +\draw [->] (S) -- node[auto,below] {$b$} (SB); +\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB); +\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA); +\draw [->] (SA) -- node[auto] {$a$} (U); +\draw [->] (SB) -- node[auto,below] {$b$} (U); +\draw [->] (U) to[loop above] node[auto] {$a,b$} (U); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(5) Construire un automate $\mathscr{A}_5$ reconnaissant le +langage $M$ complémentaire de $L$. + +\begin{corrige} +On obtient $\mathscr{A}_5$ en échangeant états finaux et non finaux +dans $\mathscr{A}_4$, c'est-à-dire l'automate $\mathscr{A}_5$ +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$S$}; +\node (SA) at (70bp,35bp) [draw,circle,state,final] {$SA$}; +\node (SB) at (70bp,-35bp) [draw,circle,state,final] {$SB$}; +\node (U) at (140bp,0bp) [draw,circle,state] {$U$}; +\draw [->] (S) -- node[auto,near end] {$a$} (SA); +\draw [->] (S) -- node[auto,below] {$b$} (SB); +\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB); +\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA); +\draw [->] (SA) -- node[auto] {$a$} (U); +\draw [->] (SB) -- node[auto,below,near end] {$b$} (U); +\draw [->] (U) to[loop above] node[auto] {$a,b$} (U); +\end{tikzpicture} +\end{center} +(L'état $U$ est maintenant un puits.) +\end{corrige} + +(6) En appliquant à $\mathscr{A}_5$ la méthode d'élimination des +états, déterminer une expression rationnelle dénotant le langage $M$. + +\begin{corrige} +On va manipuler des automates finis à transitions étiquetées par des +expressions rationnelles (ou « RNFA »). Dans un premier temps, on +donne à l'automate un unique état final $F$ en faisant pointer vers +lui une transition spontanée (i.e., étiquetée +par $\underline{\varepsilon}$) depuis tout état qui était final. +L'état $U$ peut être éliminé d'emblée puisqu'il est inutile (il n'est +pas co-accessible : c'est un puits !). On a donc affaire à l'automate +suivant +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$}; +\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$}; +\node (F) at (140bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (S) -- node[auto,near end] {$a$} (SA); +\draw [->] (S) -- node[auto,below] {$b$} (SB); +\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB); +\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA); +\draw [->] (SA) -- node[auto] {$\underline{\varepsilon}$} (F); +\draw [->] (SB) -- node[auto,below,near end] {$\underline{\varepsilon}$} (F); +\draw [->] (S) to[out=270,in=90] (0,-30bp) to[out=270,in=270] node[auto,below] {$\underline{\varepsilon}$} (140bp,-30bp) to[in=270,out=90] (F); +\end{tikzpicture} +\end{center} +On élimine maintenant l'état $SB$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$}; +\node (F) at (140bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (S) -- node[auto,near end] {$a|ba$} (SA); +\draw [->] (SA) -- node[auto] {$\underline{\varepsilon}|b$} (F); +\draw [->] (S) to[out=270,in=270] node[auto,below] {$\underline{\varepsilon}|b$} (F); +\draw [->] (SA) to[loop below] node[auto] {$ba$} (SA); +\end{tikzpicture} +\end{center} +Et l'élimination de l'état $SA$ conduit à l'expression rationnelle +$\underline{\varepsilon}\,|\,b\,|\penalty0\,(a|ba)(ba){*}(\underline{\varepsilon}|b)$ +(il y a bien sûr toutes sortes d'autres expressions rationnelles +équivalentes : par exemple, on peut la réécrire comme +$\underline{\varepsilon}\,|\,b\,|\penalty0\,(\varepsilon|b)a(ba){*}(\underline{\varepsilon}|b)$ +ou encore comme +$(\varepsilon|b)(\underline{\varepsilon}|a(ba){*}(\underline{\varepsilon}|b))$ ; +si on avait éliminé l'état $SA$ en premier, on serait plutôt tombé sur +$\underline{\varepsilon}\,|\,a\,|\penalty0\,(b|ab)(ab){*}(\underline{\varepsilon}|a)$, +et ainsi de suite). +\end{corrige} + + + +% +% +% + +\exercice + +On considère la grammaire hors-contexte $G$ d'axiome $S$ et de +nonterminaux $N = \{S, T, U, V\}$ sur l'alphabet $\Sigma = +\{{\#},{@},{(},{)}, x, y, z\}$ (soit $7$ lettres) donnée par +\[ +\begin{aligned} +S &\rightarrow T \;|\; S\mathbin{\#}T\\ +T &\rightarrow U \;|\; U\mathbin{@}T\\ +U &\rightarrow V \;|\; (\,S\,)\\ +V &\rightarrow x \;|\; y \;|\; z\\ +\end{aligned} +\] +(On pourra imaginer que $\#$ et $@$ sont deux opérations binaires, les +parenthèses servent comme on s'y attend, et $x,y,z$ sont trois opérandes +auxquelles on peut vouloir appliquer ces opérations.) + +La grammaire en question est inambiguë (on ne demande pas de le +démontrer). + +(1) Donner les arbres d'analyse (=de dérivation) des mots suivants : +(a) $x\mathbin{\#}y\mathbin{\#}z$, (b) $x\mathbin{\#}y\mathbin{@}z$, +(c) $x\mathbin{@}y\mathbin{\#}z$, (d) $x\mathbin{@}y\mathbin{@}z$, +(e) $(x\mathbin{\#}y)\mathbin{@}z$. + +\begin{corrige} +On obtient les arbres d'analyse suivants : +(a) % S<S<S<T<U<V<x.>>>>#.T<U<V<y.>>>>#.T<U<V<z.>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (53.333bp,0.000bp) [draw=none] {$S$}; +\node (S1) at (20.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (S2) at (0.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (T0) at (0.000bp,-80.000bp) [draw=none] {$T$}; \draw (S2) -- (T0); +\node (U0) at (0.000bp,-100.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (V0) at (0.000bp,-120.000bp) [draw=none] {$V$}; \draw (U0) -- (V0); +\node (x0) at (0.000bp,-140.000bp) [draw=none] {$x$}; \draw (V0) -- (x0); +\node (o0) at (20.000bp,-60.000bp) [draw=none] {$\#$}; \draw (S1) -- (o0); +\node (T1) at (40.000bp,-60.000bp) [draw=none] {$T$}; \draw (S1) -- (T1); +\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (V1) at (40.000bp,-100.000bp) [draw=none] {$V$}; \draw (U1) -- (V1); +\node (y0) at (40.000bp,-120.000bp) [draw=none] {$y$}; \draw (V1) -- (y0); +\node (o1) at (60.000bp,-30.000bp) [draw=none] {$\#$}; \draw (S0) -- (o1); +\node (T2) at (80.000bp,-30.000bp) [draw=none] {$T$}; \draw (S0) -- (T2); +\node (U2) at (80.000bp,-50.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (V2) at (80.000bp,-70.000bp) [draw=none] {$V$}; \draw (U2) -- (V2); +\node (z0) at (80.000bp,-90.000bp) [draw=none] {$z$}; \draw (V2) -- (z0); +\end{tikzpicture} +\hskip1cmplus5cmminus.5cm +(b) % S<S<T<U<V<x.>>>>#.T<U<V<y.>>@.T<U<V<z.>>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (26.667bp,0.000bp) [draw=none] {$S$}; +\node (S1) at (0.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (T0) at (0.000bp,-50.000bp) [draw=none] {$T$}; \draw (S1) -- (T0); +\node (U0) at (0.000bp,-70.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (V0) at (0.000bp,-90.000bp) [draw=none] {$V$}; \draw (U0) -- (V0); +\node (x0) at (0.000bp,-110.000bp) [draw=none] {$x$}; \draw (V0) -- (x0); +\node (o0) at (20.000bp,-30.000bp) [draw=none] {$\#$}; \draw (S0) -- (o0); +\node (T1) at (60.000bp,-30.000bp) [draw=none] {$T$}; \draw (S0) -- (T1); +\node (U1) at (40.000bp,-60.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (V1) at (40.000bp,-80.000bp) [draw=none] {$V$}; \draw (U1) -- (V1); +\node (y0) at (40.000bp,-100.000bp) [draw=none] {$y$}; \draw (V1) -- (y0); +\node (o1) at (60.000bp,-60.000bp) [draw=none] {$@$}; \draw (T1) -- (o1); +\node (T2) at (80.000bp,-60.000bp) [draw=none] {$T$}; \draw (T1) -- (T2); +\node (U2) at (80.000bp,-80.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (V2) at (80.000bp,-100.000bp) [draw=none] {$V$}; \draw (U2) -- (V2); +\node (z0) at (80.000bp,-120.000bp) [draw=none] {$z$}; \draw (V2) -- (z0); +\end{tikzpicture} +\hskip1cmplus5cmminus.5cm +(c) % S<S<T<U<V<x.>>@.T<U<V<y.>>>>>#.T<U<V<z.>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (53.333bp,0.000bp) [draw=none] {$S$}; +\node (S1) at (20.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (T0) at (20.000bp,-50.000bp) [draw=none] {$T$}; \draw (S1) -- (T0); +\node (U0) at (0.000bp,-80.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (V0) at (0.000bp,-100.000bp) [draw=none] {$V$}; \draw (U0) -- (V0); +\node (x0) at (0.000bp,-120.000bp) [draw=none] {$x$}; \draw (V0) -- (x0); +\node (o0) at (20.000bp,-80.000bp) [draw=none] {$@$}; \draw (T0) -- (o0); +\node (T1) at (40.000bp,-80.000bp) [draw=none] {$T$}; \draw (T0) -- (T1); +\node (U1) at (40.000bp,-100.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (V1) at (40.000bp,-120.000bp) [draw=none] {$V$}; \draw (U1) -- (V1); +\node (y0) at (40.000bp,-140.000bp) [draw=none] {$y$}; \draw (V1) -- (y0); +\node (o1) at (60.000bp,-30.000bp) [draw=none] {$\#$}; \draw (S0) -- (o1); +\node (T2) at (80.000bp,-30.000bp) [draw=none] {$T$}; \draw (S0) -- (T2); +\node (U2) at (80.000bp,-50.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (V2) at (80.000bp,-70.000bp) [draw=none] {$V$}; \draw (U2) -- (V2); +\node (z0) at (80.000bp,-90.000bp) [draw=none] {$z$}; \draw (V2) -- (z0); +\end{tikzpicture} +\hskip1cmplus5cmminus.5cm +(d) % S<T<U<V<x.>>@.T<U<V<y.>>@.T<U<V<z.>>>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (26.667bp,0.000bp) [draw=none] {$S$}; +\node (T0) at (26.667bp,-20.000bp) [draw=none] {$T$}; \draw (S0) -- (T0); +\node (U0) at (0.000bp,-50.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (V0) at (0.000bp,-70.000bp) [draw=none] {$V$}; \draw (U0) -- (V0); +\node (x0) at (0.000bp,-90.000bp) [draw=none] {$x$}; \draw (V0) -- (x0); +\node (o0) at (20.000bp,-50.000bp) [draw=none] {$@$}; \draw (T0) -- (o0); +\node (T1) at (60.000bp,-50.000bp) [draw=none] {$T$}; \draw (T0) -- (T1); +\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (V1) at (40.000bp,-100.000bp) [draw=none] {$V$}; \draw (U1) -- (V1); +\node (y0) at (40.000bp,-120.000bp) [draw=none] {$y$}; \draw (V1) -- (y0); +\node (o1) at (60.000bp,-80.000bp) [draw=none] {$@$}; \draw (T1) -- (o1); +\node (T2) at (80.000bp,-80.000bp) [draw=none] {$T$}; \draw (T1) -- (T2); +\node (U2) at (80.000bp,-100.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (V2) at (80.000bp,-120.000bp) [draw=none] {$V$}; \draw (U2) -- (V2); +\node (z0) at (80.000bp,-140.000bp) [draw=none] {$z$}; \draw (V2) -- (z0); +\end{tikzpicture} +\hskip1cmplus5cmminus.5cm +(e) % S<T<U<(.S<S<T<U<V<x.>>>>#.T<U<V<y.>>>>).>@.T<U<V<z.>>>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (86.667bp,0.000bp) [draw=none] {$S$}; +\node (T0) at (86.667bp,-20.000bp) [draw=none] {$T$}; \draw (S0) -- (T0); +\node (U0) at (40.000bp,-50.000bp) [draw=none] {$U$}; \draw (T0) -- (U0); +\node (p0) at (0.000bp,-80.000bp) [draw=none] {$($}; \draw (U0) -- (p0); +\node (S1) at (40.000bp,-80.000bp) [draw=none] {$S$}; \draw (U0) -- (S1); +\node (S2) at (20.000bp,-110.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (T1) at (20.000bp,-130.000bp) [draw=none] {$T$}; \draw (S2) -- (T1); +\node (U1) at (20.000bp,-150.000bp) [draw=none] {$U$}; \draw (T1) -- (U1); +\node (V0) at (20.000bp,-170.000bp) [draw=none] {$V$}; \draw (U1) -- (V0); +\node (x0) at (20.000bp,-190.000bp) [draw=none] {$x$}; \draw (V0) -- (x0); +\node (o0) at (40.000bp,-110.000bp) [draw=none] {$\#$}; \draw (S1) -- (o0); +\node (T2) at (60.000bp,-110.000bp) [draw=none] {$T$}; \draw (S1) -- (T2); +\node (U2) at (60.000bp,-130.000bp) [draw=none] {$U$}; \draw (T2) -- (U2); +\node (V1) at (60.000bp,-150.000bp) [draw=none] {$V$}; \draw (U2) -- (V1); +\node (y0) at (60.000bp,-170.000bp) [draw=none] {$y$}; \draw (V1) -- (y0); +\node (p1) at (80.000bp,-80.000bp) [draw=none] {$)$}; \draw (U0) -- (p1); +\node (o1) at (100.000bp,-50.000bp) [draw=none] {$@$}; \draw (T0) -- (o1); +\node (T3) at (120.000bp,-50.000bp) [draw=none] {$T$}; \draw (T0) -- (T3); +\node (U3) at (120.000bp,-70.000bp) [draw=none] {$U$}; \draw (T3) -- (U3); +\node (V2) at (120.000bp,-90.000bp) [draw=none] {$V$}; \draw (U3) -- (V2); +\node (z0) at (120.000bp,-110.000bp) [draw=none] {$z$}; \draw (V2) -- (z0); +\end{tikzpicture} +\end{corrige} + +(2) En considérant que $(w)$ a le même effet ou la même valeur +que $w$ : (a) L'une des deux opérations $\#$ et $@$ est-elle +prioritaire\footnote{On dit qu'une opération binaire $\boxtimes$ est + \emph{prioritaire} sur $\boxplus$ lorsque « $u\boxtimes v\boxplus + w$ » se comprend comme « $(u\boxtimes v)\boxplus w$ » (i.e., les + deux ont le même effet ou la même valeur), et « $u\boxplus + v\boxtimes w$ » comme « $u\boxplus (v\boxtimes w)$ ».} sur +l'autre ? Laquelle ?\quad (b) L'opération $\#$ +s'associe-t-elle\footnote{On dit qu'une opération binaire $\boxdot$ + \emph{s'associe à gauche} lorsque « $u\boxdot v\boxdot w$ » se + comprend comme « $(u\boxdot v)\boxdot w$ », et \emph{s'associe à + droite} lorsque « $u\boxdot v\boxdot w$ » se comprend comme + « $u\boxdot (v\boxdot w)$ ».} à gauche ou à droite ?\quad +(c) L'opération $@$ s'associe-t-elle à gauche ou à droite ? + +\begin{corrige} +(a) Les arbres d'analyse (b) et (c) de la question (1) montrent que + l'opération $@$ est prioritaire sur $\#$ (elle est toujours plus + profonde dans l'arbre, c'est-à-dire appliquée en premier aux + opérandes).\quad (b) L'arbre d'analyse (a) de la question (1) montre + que $\#$ s'associe à gauche (le $\#$ entre les deux opérandes gauche + est plus profond, c'est-à-dire appliqué en premier).\quad + (c) Symétriquement, l'arbre d'analyse (d) de la question (1) montre + que $@$ s'associe à droite. +\end{corrige} + +\smallskip + +(La question (3) est indépendante de (1) et (2). Par ailleurs, on +pourra, si on souhaite s'épargner des confusions, choisir de renommer +en $a$ la lettre « parenthèse ouvrante » de $\Sigma$ et en $b$ la +lettre « parenthèse fermante » afin de les distinguer des parenthèses +mathématiques.) + +(3) Soit $L = L(G)$ le langage engendré par $G$. Soit $M$ le langage +des mots sur $\Sigma$ formés d'un certain nombre de parenthèses +ouvrantes, puis de la lettre $x$, puis d'un certain nombre +(possiblement différent) de parenthèses fermantes : autrement dit, des +mots de la forme « ${(}^i\, x\, {)}^j$ », où on a noté « ${(}^i$ » une +succession de $i$ parenthèses ouvrantes et « ${)}^j$ » une succession +de $j$ parenthèses fermantes (on pourra noter ce mot $a^i x b^j$ si on +préfère).\quad (a) Décrire le langage $L\cap M$ (des mots de $L$ qui +appartiennent aussi à $M$).\quad (b) Ce langage $L\cap M$ est-il +rationnel ?\quad (c) Le langage $L$ est-il rationnel ? + +\begin{corrige} +(a) Cherchons pour quelles valeurs $(i,j) \in \mathbb{N}^2$ le mot + « ${(}^i\, x\, {)}^j$ » de $M$ appartient à $L$. La dérivation $S + \Rightarrow T \Rightarrow U \Rightarrow (S) \Rightarrow (T) + \Rightarrow (U) \Rightarrow ((S)) \Rightarrow \cdots + \Rightarrow{(}^i\, S\, {)}^i \Rightarrow{(}^i\, T\, {)}^i + \Rightarrow{(}^i\, U\, {)}^i \Rightarrow{(}^i\, V\, {)}^i + \Rightarrow{(}^i\, x\, {)}^i$ montre que c'est le cas si $j=i$, + autrement dit s'il y a autant de parenthèses fermantes qu'ouvrantes. + Mais réciproquement, la propriété d'avoir autant de parenthèses + fermantes qu'ouvrantes est préservée par toutes les productions + de $G$ (et est satisfaite par l'axiome), donc est vérifiée par tout + mot de $L=L(G)$. On a donc prouvé que le $L\cap M$ est l'ensemble + des mots de la forme « ${(}^i\, x\, {)}^i$ » où $i\in \mathbb{N}$. + +(b) Le langage $L\cap M$ constitué des mots de la forme « ${(}^n\, + x\, {)}^n$ » où $i\in \mathbb{N}$ n'est pas rationnel. Cela résulte + du lemme de pompage (presque exactement comme l'exemple du langage + $\{a^n b^n : i\in\mathbb{N}\}$ donné en cours) : donnons l'argument + en remplaçant la parenthèse ouvrante par $a$ et la parenthèse + fermante par $b$ pour plus de clarté notationnelle. Appliquons le + lemme de pompage pour les langages rationnels au langage $L \cap M = + \{a^n x b^n : i\in\mathbb{N}\}$ supposé par l'absurde être + rationnel : appelons $k$ l'entier dont le lemme de pompage garantit + l'existence. Considérons le mot $t := a^k x b^k$ : il doit alors + exister une factorisation $t = uvw$ pour laquelle on a (i) $|v|\geq + 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in L\cap M$ pour tout $i\geq + 0$. La propriété (ii) assure que $uv$ est formé d'un certain nombre + de répétitions de la lettre $a$ (car tout préfixe de longueur $\leq + k$ de $a^k x b^k$ est de cette forme) ; disons $u = a^\ell$ et $v = + a^m$, si bien que $w = a^{k-\ell-m} x b^k$. La propriété (i) + donne $m\geq 1$. Enfin, la propriété (iii) affirme que le mot + $uv^iw = a^{k+(i-1)m} x b^k$ appartient à $L\cap M$ ; mais dès que + $i\neq 1$, ceci est faux : il suffit donc de prendre $i=0$ pour + avoir une contradiction. + +(c) Le langage $M$ est rationnel puisqu'il est dénoté par l'expression + rationnelle $a{*}xb{*}$ (toujours en notant $a$ la parenthèse + ouvrante et $b$ la parenthèse fermante). Si le langage $L$ était + rationnel, le langage $L\cap M$ le serait aussi (on sait que + l'intersection de deux langages rationnels est rationnelle), ce qui + n'est pas le cas d'après la question (b). Le langage $L$ n'est donc + pas rationnel. +\end{corrige} + + +% +% +% + +\exercice + +(On pourra si on le souhaite remplacer $\mathbb{N}$ partout dans cet +exercice par l'ensemble $\Sigma^*$ des mots sur un alphabet $\Sigma$ +[fini] non vide fixé quelconque : grâce au codage de Gödel, ceci ne +change rien au problème ni aux raisonnements.) + +Dans cet exercice, on appelle « langage » une partie de $\mathbb{N}$ +(cf. le paragraphe précédent). + +On dira que deux langages $L,M$ disjoints (c'est-à-dire tels que +$L\cap M = \varnothing$) sont \emph{calculablement séparables} +lorsqu'il existe un langage $E$ \underline{décidable} tel que $L +\subseteq E$ et $M \subseteq (\mathbb{N}\setminus E)$ (où +$\mathbb{N}\setminus E$ désigne le complémentaire de $E$) ; dans le +cas contraire, on dit que $L$ et $M$ sont \emph{calculablement + inséparables}. + +(1) Expliquer pourquoi deux langages $L,M$ disjoints sont +calculablement séparables si et seulement s'il existe un algorithme +qui, prenant en entrée un élément $x$ de $\mathbb{N}$ : +\begin{itemize} +\item termine toujours en temps fini, +\item répond « vrai » si $x\in L$ et « faux » si $x \in M$ (rien n'est + imposé si $x\not\in L\cup M$ à part de terminer en temps fini). +\end{itemize} + +\begin{corrige} +Si $E$ est décidable tel que $L \subseteq E$ et $M \subseteq +(\mathbb{N}\setminus E)$, alors un algorithme qui décide $E$ +(c'est-à-dire, quand on lui fournit l'entrée $x$, répond « vrai » si +$x\in E$, et « faux » si $x \not\in E$) répond bien aux critères +demandés. Réciproquement, donné un algorithme qui répond aux critères +demandés, si $E$ est l'ensemble des $x$ sur lesquels il répond +« vrai », alors $E$ est bien décidable (on peut toujours modifier +l'algorithme si nécessaire pour qu'il ne réponde que « vrai » ou +« faux »), et on a $L \subseteq E$ et $M \subseteq +(\mathbb{N}\setminus E)$. +\end{corrige} + +(2) Expliquer pourquoi deux langages \emph{décidables} disjoints sont +toujours calculablement séparables. + +\begin{corrige} +Si $L,M$ sont décidables disjoints, on peut poser $E = L$, qui est +décidable et vérifie à la fois $L \subseteq E$ (trivialement) et $M +\subseteq (\mathbb{N}\setminus E)$ (c'est une reformulation du fait +que $M$ est disjoint de $E=L$). +\end{corrige} + +On cherche maintenant à montrer qu'il existe deux langages $L,M$ +\emph{semi-décidables} disjoints et calculablement inséparables. + +Pour cela, on appelle $L$ l'ensemble des couples\footnote{Pour être + rigoureux, on a fixé un codage de Gödel permettant de représenter + les programmes $e$, les entrées $x$ à ces programmes, et les couples + $(e,x)$, comme des éléments de $\mathbb{N}$. Il n'est pas + nécessaire de faire apparaître ce codage dans la description des + algorithmes proposés, qui peut rester informelle.} $(e,x)$ formés +d'un programme (=algorithme) $e$ et d'une entrée $x$, tels que +l'exécution du programme $e$ sur l'entrée $x$ termine en temps fini et +renvoie la valeur $1$ (ce qui peut se noter $\varphi_e(x) = 1$) ; et +$M$ le langage défini de la même manière mais avec la valeur $2$, +i.e., $\varphi_e(x) = 2$. (Ici, $1$ et $2$ peuvent être remplacés par +deux éléments distincts quelconques de $\mathbb{N}$ : si on a souhaité +remplacer $\mathbb{N}$ par $\Sigma^*$, on peut prendre deux mots +distincts quelconques, par exemple $a$ et $aa$.) + +(3) Pourquoi $L$ et $M$ sont-ils disjoints ? + +\begin{corrige} +Comme $L$ est l'ensemble des couples $(e,x)$ tels que $\varphi_e(x) = +1$ et $M$ l'ensemble des couples $(e,x)$ tels que $\varphi_e(x) = 2$, +aucun couple ne peut appartenir aux deux, c'est-à-dire qu'ils sont +disjoints. +\end{corrige} + +(4) Pourquoi $L$ et $M$ sont-ils semi-décidables ? + +\begin{corrige} +Pour semi-décider si un couple $(e,x)$ appartient à $L$, il suffit de +lancer l'exécution du programme $e$ sur l'entrée $x$ et, si elle +termine en retournant $1$, renvoyer « vrai », tandis que si elle +termine en renvoyant n'importe quelle autre valeur, faire une boucle +infinie (bien sûr, si le programme $e$ ne termine jamais sur +l'entrée $x$, on ne termine pas non plus). Ceci montre que $L$ est +semi-décidable. Le même raisonnement s'applique pour $M$. +\end{corrige} + +(5) En imitant la démonstration du théorème de Turing sur +l'indécidabilité du problème de l'arrêt, montrer qu'il n'existe aucun +algorithme qui, prenant en entrée un couple $(e,x)$, termine toujours +en temps fini et répond « vrai » si $(e,x)\in L$ et « faux » si $(e,x) +\in M$ (indication : si un tel algorithme existait, on pourrait s'en +servir pour faire le contraire de ce qu'il prédit). + +\begin{corrige} +Montrons par l'absurde qu'il n'existe aucun algorithme $T$ comme +annoncé. Définissons un nouvel algorithme $T'$ qui, donné un +entier $e$, effectue les calculs suivants : (1º) interroger +l'algorithme $T$ (supposé exister !) en lui fournissant le couple +$(e,e)$ comme entrée, et ensuite (2º) s'il répond vrai, renvoyer la +valeur $2$, tandis que s'il répond n'importe quoi d'autre, renvoyer la +valeur $1$. L'algorithme $T'$ qui vient d'être décrit aurait un +certain numéro, disons, $p$, et la description de l'algorithme fait +qu'il termine toujours, que la valeur $\varphi_p(e)$ qu'il renvoie +vaut toujours soit $1$ soit $2$, et qu'elle vaut $2$ si $(e,e) \in L$ +(c'est-à-dire si $\varphi_e(e) = 1$) et $1$ si $(e,e) \in M$ +(c'est-à-dire si $\varphi_e(e) = 2$). En particulier, en prenant +$e=p$, on voit que $\varphi_p(p)$ doit valoir $1$ ou $2$, doit valoir +$2$ si $\varphi_p(p) = 1$ et $1$ si $\varphi_p(p) = 2$, ce qui est une +contradiction. +\end{corrige} + +(6) Conclure. + +\begin{corrige} +La question (5) montre (compte tenu de la question (1)) que $L$ et $M$ +ne sont pas calculablement séparables, i.e.., sont calculablement +inséparables, tandis que (4) et (5) montrent que $L$ et $M$ sont +disjoints et semi-décidables. On a donc bien montré l'existence de +langages semi-décidables disjoints et calculablement inséparables. +\end{corrige} + + + +% +% +% +\end{document} diff --git a/controle-20230615.tex b/controle-20230615.tex new file mode 100644 index 0000000..d9bc00d --- /dev/null +++ b/controle-20230615.tex @@ -0,0 +1,870 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +\usepackage{hyperref} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +\newenvironment{commentaire}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}} +{{\hbox{}\nobreak\hfill\maltese}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% NOTE: compile dot files with +% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} +\ifcorrige +\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{15 juin 2023} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +\medbreak + +L'usage de tous les documents (notes de cours manuscrites ou +imprimées, feuilles d'exercices, livres) est autorisé. + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 1h30 + +Barème \emph{indicatif} et \emph{approximatif} : exercice 1 : +(a) $1.5$, (b) $1.5$, (c) $1$, (d) $4$, (e) $3$, (f) $3$ (soit au +total $14$) ; exercice 2 : (a) $1$, (b) $2$, (c) $1$, (d) $2$ (soit au +total $6$). + +\ifcorrige +Ce corrigé comporte 8 pages (page de garde incluse). +\else +Cet énoncé comporte 4 pages (page de garde incluse). +\fi + +\vfill + +{\tiny\noindent +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On considère les huit +automates suivants +($A_{\mathrm{s}},A_{\mathrm{t}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{w}},A_{\mathrm{x}},A_{\mathrm{y}},A_{\mathrm{z}}$) +sur l'alphabet $\Sigma$ : + +\begin{center} +\begin{tabular}{|c|c|} +\hline +$A_{\mathrm{s}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{t}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{u}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{v}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{w}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0); +\draw[->] (q1) to[loop above] node[auto]{$a,b$} (q1); +\draw[->] (q2) to[loop above] node[auto]{$a,b$} (q2); +\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3); +\draw[->] (q4) to[loop above] node[auto]{$a,b$} (q4); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{x}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting below] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting below] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting below] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting below] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting below] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting below] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{y}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,initial above] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,initial above] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,initial above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,initial above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,initial above,final] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +$A_{\mathrm{z}}$\rule[-2ex]{0pt}{0pt}& +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial above,accepting below] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,initial above,accepting below] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,initial above,accepting below] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,initial above,accepting below] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,initial above,accepting below] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,initial above,accepting below] {$5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\end{tikzpicture} +}\\ +\hline +\end{tabular} +\end{center} + +On définit aussi les douze langages suivants, où $w_0$ désigne le +mot $ababb$ : +\begin{itemize} +\item $L_0 = \varnothing$ : le langage vide. +\item $L_1 = \{w_0\}$ : le langage constitué du seul mot $w_0$. +\item $L_2$ : le langage constitué des mots qui sont un sous-mot de + $w_0$. +\item $L_3$ : le langage constitué des mots qui ont $w_0$ comme + sous-mot. +\item $L_4$ : le langage constitué des mots qui sont un facteur de + $w_0$. +\item $L_5$ : le langage constitué des mots qui ont $w_0$ comme + facteur. +\item $L_6$ : le langage constitué des mots qui sont un préfixe de + $w_0$. +\item $L_7$ : le langage constitué des mots qui ont $w_0$ comme + préfixe. +\item $L_8$ : le langage constitué des mots qui sont un suffixe de + $w_0$. +\item $L_9$ : le langage constitué des mots qui ont $w_0$ comme + suffixe. +\item $L_{10} = \{w_0^i : i\in\mathbb{N}\}$ : le langage constitué des + mots qui sont une répétition d'un nombre quelconque ($i$) de copies + de $w_0$ (par exemple, $ababbababb$). +\item $L_{11} = \{b^i w_0 a^i : i\in\mathbb{N}\}$ : le langage + constitué des mots obtenus en précédant $w_0$ d'un nombre + quelconque ($i$) de copies de la lettre $b$ et en le suivant du même + nombre de copies de la lettre $a$ (par exemple, $bbababbaa$). +\end{itemize} + +\textbf{(a)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire lequel ou +lesquels parmi les douze langages $L_0,\ldots,L_{11}$ est celui +reconnu par l'automate $A$. On ne demande pas de justifier la +réponse. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ reconnaît le langage $L_1 = \{w_0\}$. + +L'automate $A_{\mathrm{t}}$ reconnaît le langage $L_9$ des mots ayant +$w_0$ comme suffixe (car un chemin dans $A_{\mathrm{t}}$ finit par un +chemin consommant $w_0$). + +L'automate $A_{\mathrm{u}}$ reconnaît le langage $L_7$ des mots ayant +$w_0$ comme préfixe (car un chemin dans $A_{\mathrm{u}}$ commence +par un chemin consommant $w_0$). + +L'automate $A_{\mathrm{v}}$ reconnaît le langage $L_5$ des mots ayant +$w_0$ comme facteur (car un chemin dans $A_{\mathrm{u}}$ passe par un +chemin consommant $w_0$). + +L'automate $A_{\mathrm{w}}$ reconnaît le langage $L_3$ des mots ayant +$w_0$ comme sous-mot (car un chemin dans $A_{\mathrm{u}}$ consomme les +lettres $a,b,a,b,b$ dans cet ordre, intercalées par un nombre +quelconque de lettres quelconques). + +L'automate $A_{\mathrm{x}}$ reconnaît le langage $L_6$ des préfixes +de $w_0$ (car un chemin dans $A_{\mathrm{x}}$ consomme le début +de $w_0$). + +L'automate $A_{\mathrm{y}}$ reconnaît le langage $L_8$ des suffixes +de $w_0$ (car un chemin dans $A_{\mathrm{y}}$ consomme la fin +de $w_0$). + +L'automate $A_{\mathrm{z}}$ reconnaît le langage $L_4$ des facteurs +de $w_0$ (car un chemin dans $A_{\mathrm{z}}$ consomme un intervalle +de lettres consécutives de $w_0$). + +(Les justifications entre parenthèses n'étaient pas demandées.) +\end{corrige} + +\textbf{(b)} Pour chacun des sept automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}\}$ (cette question-ci n'est pas posée +pour $A_{\mathrm{z}}$), donner une expression rationnelle dénotant le +langage $L$ reconnu par $A$. On ne demande pas de justifier la +réponse, et il n'est pas obligatoire d'appliquer un algorithme vu en +cours. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ reconnaît le langage dénoté par $ababb$. + +L'automate $A_{\mathrm{t}}$ reconnaît le langage dénoté +par $(a|b){*}ababb$. + +L'automate $A_{\mathrm{u}}$ reconnaît le langage dénoté +par $ababb(a|b){*}$. + +L'automate $A_{\mathrm{v}}$ reconnaît le langage dénoté +par $(a|b){*}ababb(a|b){*}$. + +L'automate $A_{\mathrm{w}}$ reconnaît le langage dénoté +par $(a|b){*}a(a|b){*}b(a|b){*}a(a|b){*}b(a|b){*}b(a|b){*}$. + +L'automate $A_{\mathrm{x}}$ reconnaît le langage dénoté +par $\underline{\varepsilon}|a|ab|aba|abab|ababb$ (simple énumération +de tous les préfixes de $w_0$) ou, si on préfère, par +$\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|b))))$ +(obtenue en éliminant les états de $A_{\mathrm{x}}$ dans +l'ordre $5,4,3,2,1,0$). + +L'automate $A_{\mathrm{y}}$ reconnaît le langage dénoté +par $\underline{\varepsilon}|b|bb|abb|babb|ababb$ (simple énumération +de tous les suffixes de $w_0$) ou, si on préfère, par +$\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|a)b)a)b)b$ +(obtenue en éliminant les états de $A_{\mathrm{y}}$ dans +l'ordre $0,1,2,3,4,5$). +\end{corrige} + +\textbf{(c)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire de quel type +d'automate vu en cours (DFA complet, DFA à spécification incomplète, +NFA ou bien NFA à transitions spontanées) est l'automate $A$. On +donnera à chaque fois le type le plus particulier applicable. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{t}}$ est un NFA (à cause de la double +transition étiquetée $a$ depuis l'état $0$). + +L'automate $A_{\mathrm{u}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{v}}$ est un NFA. + +L'automate $A_{\mathrm{w}}$ est un NFA. + +L'automate $A_{\mathrm{x}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{y}}$ est un NFA (à cause des multiples états +initiaux). + +L'automate $A_{\mathrm{z}}$ est un NFA. +\end{corrige} + +\textbf{(d)} Pour chacun des cinq automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{x}}, A_{\mathrm{z}}\}$ +(cette question-ci n'est pas posée pour $A_{\mathrm{t}}, +A_{\mathrm{w}}, A_{\mathrm{y}}$), donner un DFA complet sans état +inaccessible qui soit équivalent à $A$ (c'est-à-dire, reconnaissant le +langage $L$). On appliquera un algorithme vu en cours en le nommant. + +{\footnotesize Conseil sur la présentation graphique : pour s'éviter + des maux de tête dans le placement des états (et en éviter aussi au + correcteur), il est conseillé de commencer par placer + horizontalement de gauche à droite les états successifs rencontrés + lors de la consommation du mot $w_0 = ababb$ par l'automate + construit, et d'ajouter ensuite les autres états éventuellement + nécessaires.\par} + +\begin{corrige} +S'agissant de $A_{\mathrm{s}}$, comme c'est un DFAi, il s'agit +simplement de lui ajouter un état « puits », noté $\bot$ ci-dessous, +où aboutissent toutes les transitions manquantes : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax +La construction est analogue pour $A_{\mathrm{u}}$ : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax S'agissant de $A_{\mathrm{v}}$, on a affaire à +un « vrai » non-déterminisme et on applique donc l'algorithme de +déterminisation vu en cours, qui donne (en omettant les accolades dans +le nommage des états) : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {\small $0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {\small $0,1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {\small $0,2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {\small $0,1,3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {\small $0,2,4$}; +\node (q5) at (300bp,-45bp) [draw,circle,state,final] {\small $0,5$}; +\node (q1X) at (30bp,-90bp) [draw,circle,state,accepting below] {\small $0,1,5$}; +\node (q2X) at (110bp,-90bp) [draw,circle,state,accepting below] {\small $0,2,5$}; +\node (q3X) at (190bp,-90bp) [draw,circle,state,accepting below] {\small $0,1,3,5$}; +\node (q4X) at (270bp,-90bp) [draw,circle,state,accepting below] {\small $0,2,4,5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop below] node[auto]{$b$} (q0); +\draw[->] (q1) to[loop below] node[auto]{$a$} (q1); +\draw[->] (q2) to[out=120,in=60] node[auto,swap]{$b$} (q0); +\draw[->] (q3) to[out=120,in=60] node[auto,swap]{$a$} (q1); +\draw[->] (q4) to[out=120,in=60] node[auto,swap]{$a$} (q3); +\draw[->] (q5) to[loop above] node[auto]{$b$} (q5); +\draw[->] (q5) to[out=165,in=45] node[auto,swap,near end]{$a$} (q1X); +\draw[->] (q1X) -- node[auto]{$b$} (q2X); +\draw[->] (q2X) -- node[auto]{$a$} (q3X); +\draw[->] (q3X) -- node[auto]{$b$} (q4X); +\draw[->] (q4X) -- node[auto,swap]{$b$} (q5); +\draw[->] (q1X) to[loop left] node[auto]{$a$} (q1X); +\draw[->] (q2X) to[out=45,in=195] node[auto]{$b$} (q5); +\draw[->] (q3X) to[out=240,in=300] node[auto]{$a$} (q1X); +\draw[->] (q4X) to[out=240,in=300] node[auto]{$a$} (q3X); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax {\footnotesize\textbf{Note:} Une version + précédente de ce corrigé donnait un automate certes correct (DFA + complet sans état inaccessible qui soit équivalent à $A$) mais qui + n'est pas celui, représenté ci-dessus, obtenu en appliquant + l'algorithme de déterminisation. (L'automate qui était représenté + était, en fait, l'automate minimal obtenu en identifiant tous les + états contenant $5$ dans celui ci-dessus.)\par} +La construction pour $A_{\mathrm{x}}$ est exactement comme pour +$A_{\mathrm{s}}$ sauf que les états $0$ à $5$ sont tous marqués +finaux : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax +S'agissant de $A_{\mathrm{z}}$, on a de nouveau affaire à un « vrai » +non-déterminisme et on applique donc l'algorithme de déterminisation +vu en cours, qui donne (en omettant les accolades dans le nommage des +états) : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)] +\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2,4$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (q245) at (120bp,-120bp) [draw,circle,state,accepting below] {\small $2,4,5$}; +\node (qbot) at (300bp,-90bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (qI) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (qI) to[out=270,in=150] node[auto,swap]{$b$} (q245); +\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot); +\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5); +\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto,near start]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (q245) to[out=60,in=240] node[auto]{$a$} (q3); +\draw[->] (q245) to[out=30,in=240] node[auto,swap,very near end]{$b$} (q5); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +où on a noté $I$ au lieu de $\{0,1,2,3,4,5\}$. +\end{corrige} + +\textbf{(e)} Pour $A = A_{\mathrm{z}}$ (et seulement celui-ci), +minimiser le DFA trouvé à la question (d). + +\begin{corrige} +On a affaire à un DFA complet sans état inaccessible : on va le +minimiser avec l'algorithme de Moore. + +Dans une première étape, on fait deux classes d'état : celle des états +finaux, c'est-à-dire $I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ +et celle des états non-finaux, c'est-à-dire le seul +état $\varnothing$. + +Séparons maintenant les états selon la cible de la transition +étiquetée par $a$ : la classe formée de +$I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ se scinde en deux : +$I,\{2,4\},\{2,4,5\}$ d'une part, où elle mène à un état final, et +$\{1,3\},\{3\},\{4\},\{5\}$ d'autre part, où elle mène à un état +non-final. La cible de la transition étiquetée par $b$, pour sa part, +sépare $\{5\}$ de tous les autres états (le seul où elle mène à un +état non-final). À ce stade, on a quatre classes : la classe formée +de $I,\{2,4\},\{2,4,5\}$, celle de $\{1,3\},\{3\},\{4\}$, et deux +classes singleton, $\{5\}$ et $\varnothing$. + +À l'étape suivante, la cible de la transition étiquetée par $a$ ne +sépare rien (les états de la première classe mènent à la seconde et +les états de la seconde mènent au puits). La cible de la transition +étiquetée par $b$, en revanche, sépare la classe formée de +$I,\{2,4\},\{2,4,5\}$ en $I$ d'une part (qui mène à cette même classe) +et $\{2,4\},\{2,4,5\}$ de l'autre (qui mène à $\{5\}$) ; et elle +sépare la classe formée de $\{1,3\},\{3\},\{4\}$ en trois (puisque les +cibles sont dans trois classes distinctes). À ce stade, les seuls +états qui n'ont pas été séparés sont $\{2,4\}$ et $\{2,4,5\}$. Or +comme ils ont exactement les mêmes cibles de transitions étiquetées +par $a$ et $b$, ils ne sont pas séparés, donc l'algorithme s'applique +ici : il fusionne exactement deux états, à savoir +$\{2,4\}$ et $\{2,4,5\}$, en un seul, que nous noterons $B$ : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)] +\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$B$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (qI) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (qI) to[out=60,in=120] node[auto]{$b$} (q2); +\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot); +\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5); +\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +\textbf{(f)} Parmi les douze langages $L_0,\ldots,L_{11}$, lesquels +sont rationnels ? Lesquels sont algébriques ? Lesquels sont +décidables ? Lesquels sont semi-décidables ? On justifiera la +réponse à chaque fois (par exemple en donnant une expression +rationnelle, un automate, une grammaire hors-contexte, un algorithme, +ou n'importe quel autre type d'argument permettant de conclure). + +\begin{corrige} +Les langages $L_1,L_3,L_4,L_5,L_6,L_7,L_8,L_9$ sont rationnels car ils +sont reconnaissables : on a vu que les automates $A_{\mathrm{s}}, +A_{\mathrm{w}}, A_{\mathrm{z}}, A_{\mathrm{v}}, A_{\mathrm{x}}, +A_{\mathrm{u}}, A_{\mathrm{y}}, A_{\mathrm{t}}$ respectivement les +reconnaissent. Il reste donc à traiter le cas de +$L_0,L_2,L_{10},L_{11}$. + +Les langages $L_0$ et $L_2$ sont rationnels car ils sont finis (on +peut donner des expressions rationnelles pour les deux, à savoir +$\bot$ pour $L_0$ et, en énumérant systématiquement tous les +sous-mots, $\varepsilon | b | bb | a | ab | abb | bbb | ba | bab | +babb | aa | aab | aabb | abbb | aba | abab | ababb$ pour $L_2$, mais +ce n'est pas très intéressant et ce n'était pas demandé). + +Le langage $L_{10} = \{w_0^i : i\in\mathbb{N}\} = L_1^*$ est rationnel +car il est l'étoile de Kleene d'un langage rationnel (si on préfère, +il est dénoté par l'expression rationnelle $(ababb){*}$). + +Tous les langages $L_0$ à $L_{10}$ sont donc rationnels, et, en +particulier, algébriques, décidables et semi-décidables. + +Reste à évoquer le cas du langage $L_{11} = \{b^i w_0 a^i : +i\in\mathbb{N}\}$. Montrons qu'il n'est pas rationnel, et montrons +qu'il est algébrique. + +Il n'est pas rationnel par le lemme de pompage. En effet, supposons +par l'absurde que $\{b^i w_0 a^i : i\in\mathbb{N}\}$ soit rationnel, +et soit $k$ tel que donné par le lemme de pompage. Considérons le mot +$t := b^k ababb a^k \in L_{11}$. D'après la propriété de $k$, il +existe une factorisation $t = uvw$ vérifiant les propriétés garanties +par le lemme de pompage. Le fait que $|uv|\leq k$, comme le préfixe +de longueur $k$ de $t$ est formé uniquement de la lettre $b$, assure +que $u = b^{\ell_1}$ et $v = b^{\ell_2}$ pour certains $\ell_1,\ell_2$ +avec, de plus, $\ell_2 > 0$ (car $v\neq\varepsilon$) et +$\ell_1+\ell_2\leq k$. On a alors $w = b^{k-\ell_1-\ell_2} ababb +a^k$, et $uv^iw = b^{k+(i-1)\ell_2} ababb a^k$. Comme les mots de +$L_{11}$ ont la propriété nécessaire que leur nombre initial de $b$ +(i.e., la longueur de leur plus long préfixe formé uniquement de la +lettre $b$) est égale à leur nombre final de $a$ (i.e., la longueur de +leur plus long suffixe formé uniquement de la lettre $a$), on devrait +avoir $k+(i-1)\ell_2 = k$, ce qui est une contradiction dès que $i\neq +1$. + +En revanche, le langage $L_{11}$ est algébrique, car il est engendré +par la grammaire suivante d'axiome $S$ : +\[ +S \rightarrow ababb \;|\; bSa +\] +Étant algébrique, le langage $L_{11}$ est décidable et semi-décidable. +(Au demeurant, il est facile de donner un algorithme qui décide si un +mot appartient à $L_{11}$ : on vérifie que son nombre initial de $b$ +est égal à son nombre final de $a$ et, une fois ce fait vérifié, on +vérifie qu'une fois retiré le préfixe et le suffixe en question il +reste exactement le mot $ababb$.) + +Pour résumer, tous les langages dont on a parlé sont algébriques, +décidables et semi-décidables, et tous sauf $L_{11}$ sont rationnels. +\end{corrige} + + +% +% +% + +\exercice + +{\footnotesize Dans cet exercice, les questions (1) et (2) sont + indépendantes, et la question (4) ne dépend que de la + question (2).\par} + +\textbf{(1)} La fonction $h\colon \mathbb{N} \to \mathbb{N}$ suivante +est-elle calculable ? +\[ +h(0) = 1\;\;,\;\; +h(1) = 10\;\;,\;\; +h(2) = 10^{10}\;\;,\;\; +h(3) = 10^{10^{\scriptstyle 10}}\;\;,\;\; +h(4) = 10^{10^{\scriptstyle 10^{\scriptstyle 10}}}\;\;,\;\; +\] +\[ +\left.\begin{matrix} h(n) = 10^{\scriptstyle 10^{\scriptstyle \cdots^{\scriptstyle 10}}}\end{matrix}\right\} n +\] +(Autrement dit, $h(n)$ est une tour d'exponentielle de hauteur $n$ sur +le nombre $10$. Bien sûr, $10^{10^{\scriptstyle 10}}$ se comprend +comme $10^{\big(10^{\scriptstyle 10}\big)}$.) + +\begin{corrige} +La fonction $g\colon n\mapsto 10^n$ est calculable : en effet, on peut +exécuter une boucle à $n$ itérations en multipliant par $10$ la valeur +d'une variable en partant de $1$. On en déduit que la fonction $h$ +est calculable : en effet, on peut exécuter une boucle à $n$ +itérations en appliquant la fonction $g$ à une variable en partant +de $1$. +\end{corrige} + +\medskip + +Fixons maintenant une numérotation (« codage de Gödel ») des +algorithmes prenant en entrée un entier et renvoyant un entier, et +appelons $\varphi_e(n)$ le résultat de l'exécution du programme codé +par l'entier $e$ sur l'entrée $n$, si cette exécution termine (et +$\varphi_e(n)$ non défini si cette exécution ne termine pas). +Considérons la fonction $b\colon \mathbb{N} \to \mathbb{N}$ suivante : +\[ +b(n) = \max\{\varphi_e(n) : 0\leq e\leq n +\text{~et~}\varphi_e(n)\text{~défini}\} +\] +(Autrement dit, $b(n)$ est la plus grande des valeurs $\varphi_e(n)$ +qui sont définies lorsque $e$ parcourt les entiers de $0$ à $n$.) + +\textbf{(2)} On veut montrer que pour toute fonction calculable +$f\colon \mathbb{N} \to \mathbb{N}$, il existe un $n_0$ tel que pour +tout $n\geq n_0$ on ait $b(n) > f(n)$. Supposons donc $f\colon +\mathbb{N} \to \mathbb{N}$ calculable.\quad\textbf{(a)} Expliquer +pourquoi il existe $p$ tel que $\varphi_p = f+1$ (c'est-à-dire +$\varphi_p(n) = f(n)+1$ pour tout $n$).\quad\textbf{(b)} En déduire +que $b(n) > f(n)$ lorsque $n\geq p$, et conclure. + +\begin{corrige} +\textbf{(a)} La fonction $n \mapsto f(n)+1$ est calculable puisque $f$ +l'est et que l'addition l'est. Il existe donc un algorithme qui la +calcule, c'est-à-dire un $p$ tel que $\varphi_p = f+1$. + +\textbf{(b)} Sachant que $\varphi_p = f+1$, si $n \geq p$, la valeur +$b(n)$ est le maximum des valeurs $\varphi_e(n)$ qui sont définies +lorsque $e$ et $n$ parcourent les entiers de $0$ à $n$. En +particulier, puisque $0\leq p\leq n$, parmi ces entiers se trouve la +valeur $\varphi_p(n) = f(n)+1$ (qui est bien définie car $f$ est une +fonction totale ici). On a donc $b(n) \geq \varphi_p(n) = f(n)+1 > +f(n)$. On a bien montré que si $n \geq p$ alors $b(n) > f(n)$, ce qui +était voulu (pour $n_0 = p$). +\end{corrige} + +\textbf{(3)} Montrer que (pour les fonctions $h$ et $b$ introduites +ci-dessus) : +\[ +\lim_{n\to+\infty} \frac{b(n)}{h(n)} = +\infty +\] + +\begin{corrige} +On souhaite montrer que pour tout $C>0$ il existe $n_0$ tel que si +$n\geq n_0$ alors $\frac{b(n)}{h(n)} > C$. Pour cela, soit $C$ un +réel $>0$, et, quitte à l'augmenter encore un peu, on peut supposer +$C$ entier. La fonction $C\cdot h$ (c'est-à-dire $n \mapsto C\cdot +h(n)$) est calculable car $h$ l'est (question (1)) et que la +multiplication l'est. D'après la question (2), il existe $n_0$ tel +que pour tout $n\geq n_0$ on ait $b(n) > C\cdot h(n)$ : c'est ce qu'on +voulait montrer. +\end{corrige} + +\textbf{(4)} On se propose ici de redémontrer l'indécidabilité du +problème de l'arrêt de manière légèrement différente de ce qui a été +vu en cours. Supposons donc par l'absurde que le problème de l'arrêt +$H = \{(e,n) : \varphi_e(n)\text{~défini}\}$ soit +décidable.\quad\textbf{(a)} Montrer soigneusement, sous cette +hypothèse, que $b$ est calculable.\quad\textbf{(b)} Conclure. + +\begin{corrige} +\textbf{(a)} Supposons par l'absurde qu'il existe un algorithme $T$ +qui décide le problème de l'arrêt : autrement dit, donnés $e$ et $n$, +cet algorithme est censé terminer en temps fini et répondre « oui » si +le programme codé par $e$ termine sur l'entrée $n$, « non » sinon. On +peut alors calculer $b(n)$ de la manière suivante : on démarre avec +$m=0$ et on effectue une boucle pour $e$ allant de $0$ à $n$, et pour +chacune des valeurs en question, on utilise $T$ pour savoir si +$\varphi_e(n)$ est défini, puis, \emph{si} c'est le cas, on caclcule +cette valeur $\varphi_e(n)$ au moyen de la machine universelle (ce +calcul termine en temps fini justement puisque $\varphi_e(n)$ est +défini), et on remplace la variable $m$ par $\max(m, \varphi_e(n))$. +À la fin de la boucle, on a bien calculé le max de toutes les valeurs +$\varphi_e(n)$ qui sont définies, c'est-à-dire $b(m)$. La fonction +$b$ est donc calculable (de nouveau, sous l'hypothèse que le problème +de l'arrêt l'est). + +\textbf{(b)} On a vu en (2) que pour toute fonction calculable $f$ il +existe un $n_0$ tel que pour tout $n\geq n_0$ on ait $b(n) > f(n)$. +Comme on vient de voir que (sous l'hypothèse que le problème de +l'arrêt est calculable) la fonction $b$ est calculable, en appliquant +ce résultat à $f = b$, il doit exister un $n_0$ tel que tout $n\geq +n_0$ on ait $b(n) > b(n)$, ce qui est absurde. C'est donc que +l'hypothèse était absurde : le problème de l'arrêt n'est pas +décidable. +\end{corrige} + + +% +% +% +\end{document} diff --git a/errata-notes-inf105.tex b/errata-notes-inf105.tex index 4afd008..05f6445 100644 --- a/errata-notes-inf105.tex +++ b/errata-notes-inf105.tex @@ -71,187 +71,144 @@ Git: \input{vcline.tex} % % +\newlength{\oldparindent} +\oldparindent=\parindent +\renewcommand{\narrower}{\advance\leftskip\oldparindent\advance\rightskip\oldparindent} +\parindent=0pt +\parskip=6ptplus6pt + Les errata suivants sur le document « THL (Théorie des langages) / Notes de cours » sont relatifs à la version étiquetée -\verb=f1826f0 Tue Nov 14 13:05:17 2017 +0100= -et distribuée pour l'année universitaire 2017–2018. - -\medskip - -¶1.2.6, dernier paragraphe, (page 5), l'affirmation « Le suffixe -correspondant au préfixe $abb$ est $bcab$ puisque $abbcab = -(abb)(bcab)$ » est incorrecte, il faut remplacer $bcab$ par $cab$ et -lire : « Le suffixe correspondant au préfixe $abb$ est $cab$ puisque -$abbcab = (abb)(cab)$ ». - -\medskip - -{\footnotesize - -¶1.5.3, dernier paragraphe, (page 14), au lieu de « racourcis », lire -« raccourcis ». +\verb=28531fc Thu Jan 23 14:37:46 2020 +0100= +et distribuée pour l'année universitaire 2020–2021. \medskip -Démonstration de la proposition 2.4.6, deuxième paragraphe, (page 27), -dans la phrase « on crée une transition $q\to q'$ étiquetée par $x$ », -la précision que $x \in \Sigma$ peut être utile : remplacer par « on -crée une transition $q\to q'$ étiquetée par $x \in \Sigma$ ». +Dans la démonstration de la proposition 3.2.4, qui constitue la +construction de l'automate de Glushkov d'une concaténation, la +construction donnée affirme à tort que les états finaux de l'automate +construit sont uniquement ceux du second automate ($A_2$) concaténé. +Or il faut aussi marquer comme finaux les états finaux de $A_1$ +\emph{lorsque (et seulement lorsque)} l'état initial $q_2$ de $A_2$ +était final. -\par} +Pour corriger cette erreur, ajouter à la fin de la phrase (page 32, +lignes 11–13) -\medskip +{\narrower -Démonstration du lemme 3.2.2, deuxième paragraphe, (page 30), le -traitement des états finaux de l'automate $A'$ construit n'est pas -correct, il faut marquer le nouvel état $q_0$ créé comme final -lorsqu'il existait un état initial qui était aussi final. En -conséquence, remplacer les $F$ de ce paragraphe par $F'$, retirer le -mot « et » devant « $\delta'$ est la réunion », et ajouter à la fin du -paragraphe : « et enfin $F' = F$ ou $F' = F\cup\{q_0\}$ selon que -$I\cap F = \varnothing$ ou $I\cap F \neq \varnothing$ respectivement -(i.e., $q_0$ est final lorsqu'il existait déjà un état à la fois -initial et final) ». Le paragraphe ainsi modifié est le suivant : - -{\smallskip - -Formellement : soit $A = (Q,I,F,\delta)$. On définit alors $A' = -(Q',\{q_0\},F',\delta')$ de la manière suivante : $Q' = Q \uplus -\{q_0\}$ (où $\uplus$ désigne une réunion disjointe), $\delta'$ est la -réunion de l'ensemble des transitions $(q,x,q')$ qui étaient déjà -dans $\delta$ et de l'ensemble des $(q_0,x,q')$ telles qu'il existe -une transition $(q,x,q') \in \delta$ avec $q\in I$, et enfin $F' = F$ -ou $F' = F\cup\{q_0\}$ selon que $I\cap F = \varnothing$ ou $I\cap F -\neq \varnothing$ respectivement (i.e., $q_0$ est final lorsqu'il -existait déjà un état à la fois initial et final). +L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant +que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant +chaque transition sortant de $q_2$ par une transition identiquement +étiquetée, et de même cible, partant de \emph{chaque} état final +de $A_1$. \par} -\medskip - -{\footnotesize - -¶3.6.3 (page 56), au lieu de « fącon », lire « façon ». +la parenthèse suivante -\medskip +{\narrower -¶4.0.1 (page 50), au lieu de « démarré », lire « démarrée ». +(ces derniers seront marqués finaux si $q_2$ était final dans $A_2$) -\medskip +\par} -¶4.1.7, second paragraphe, (page 53), pour alléger la syntaxe, -déplacer la parenthèse commençant par « plus le numéro du type » à la -fin du paragraphe : « Les grammaires de types 0 et 1, avec celles de -type 2 c'est-à-dire hors contexte, et celles de type 3 (= régulières) -qui seront définies en 4.2.2 ci-dessous, forment une hiérarchie -appelée hiérarchie de Chomsky : plus le numéro du type est élevé plus -la grammaire est contrainte et plus la classe de langages définie est -petite. ». +et remplacer la phrase (page 32, lignes 15–18) -\medskip +{\narrower -¶4.2.4, deuxième paragraphe, (page 55), au lieu de « racourci », lire -« raccourci ». +On définit alors l'automate $A'$ dont l'ensemble d'états est $Q'$, +l'état initial est $q_1$, les états finaux $F' = F_2$, et la relation +de transition $\delta$ est la réunion de $\delta_1$, de l'ensemble des +triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$, et enfin de +l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q') \in \delta_2$ +et que $q\in F_1$. \par} -\medskip +par -¶4.4.1 (page 58), la rédaction ne rend pas suffisamment explicite le -fait que tout nœud qui n'est pas une feuille doit être étiqueté par un -nonterminal. Pour rendre ce fait plus explicite, remplacer dans le -deuxième tiret « si un nœud de l'arbre est étiqueté par $T$ et n'est -pas une feuille (i.e., s'il a des fils) » par « si un nœud de l'arbre -n'est pas une feuille (i.e., s'il a des fils) et si on appelle $T$ son -étiquette », et ajouter après les deux sous-cas de ce tiret -(c'est-à-dire après « dans $G$ », en passant à la ligne) la -parenthèse : « dans ces deux sous-cas, il résulte de l'existence d'une -règle $T\rightarrow\cdots$ que $T$ est un nonterminal : seules les -feuilles peuvent être étiquetées par un terminal ou $\varepsilon$ ». -Le passage ainsi modifié est le suivant : - -{\smallskip - -Soit $G$ une grammaire hors contexte sur un alphabet $\Sigma$ et $N$ -l'ensemble de ses nonterminaux. Un \textbf{arbre d'analyse} (ou -\textbf{arbre de dérivation} ; en anglais \textbf{parse tree}) -\textbf{incomplet} pour $G$ est un arbre (fini, enraciné et ordonné) -dont les nœuds sont étiquetés par des éléments de $\Sigma \cup N \cup -\{\varepsilon\}$, vérifiant les propriétés suivantes : -\begin{itemize} -\item la racine de l'arbre est étiquetée par l'axiome $S$ de $G$ ; -\item si un nœud de l'arbre n'est pas une feuille (i.e., s'il a des - fils) et si on appelle $T$ son étiquette, alors -\begin{itemize} -\item soit ce nœud a un unique fils étiqueté $\varepsilon$ et il - existe une règle $T \rightarrow \varepsilon$ dans $G$, -\item soit ce nœud a des fils étiquetés par des éléments $x_1\cdots - x_n$ (où $n\geq 1$) de $\Sigma \cup N$ et il existe une règle $T - \rightarrow x_1\cdots x_n$ dans $G$, -\end{itemize} -(dans ces deux sous-cas, il résulte de l'existence d'une règle -$T\rightarrow\cdots$ que $T$ est un nonterminal : seules les feuilles -peuvent être étiquetées par un terminal ou $\varepsilon$). -\end{itemize} +{\narrower + +On définit alors l'automate $A'$ dont l'ensemble d'états est $Q'$, +l'état initial est $q_1$, l'ensemble $F'$ des états finaux est $F_2$ +si $q_2$ n'était pas final dans $A_2$ et $F_1 \cup F_2$ si $q_2$ était +final dans $A_2$, la relation de transition $\delta'$ est la réunion +de $\delta_1$, de l'ensemble des triplets $(q,x,q') \in \delta_2$ tels +que $q\neq q_2$, et enfin de l'ensemble des triplets $(q,x,q')$ tels +que $(q_2,x,q') \in \delta_2$ et que $q\in F_1$. \par} -\medskip +On notera que, en revanche, la remarque qui suit la démonstration, et +qui décrit une façon de voir la construction en passant par l'ajout +temporaire de transitions spontanées, est correcte (l'élimination des +transitions spontanées en question conduira à rendre finaux les états +de $A_1$ lorsque $q_2$ l'état), et est probablement la façon la plus +simple de mémoriser cette construction sans se tromper. -¶4.5.2, avant-dernier paragraphe (en-dessous des arbres, page 61), -l'affirmation « Cette grammaire n'est donc pas ambiguë » est -incorrecte. Lire à la place : « Cette grammaire est donc ambiguë ». +\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill} \medskip -{\footnotesize - -¶4.7.5, dernier paragraphe, (page 66), au lieu de « complexitée », -lire « complexité ». +Dans la démonstration de la proposition 3.4.7, qui constitue la +procédure d'élimination des états, il n'est pas suffisamment clair +quelles sont les paires d'états concernées par l'élimination de +l'état $q$. Pour remédier à ce manque de clarté, ajouter une note en +bas de page après « simultanément pour toute paire » (page 40, +ligne 14 en partant du bas) : -\smallskip +{\narrower -¶4.7.6, premier paragraphe, (page 66), au lieu de « meme », lire -« même ». +Plutôt qu'examiner toutes les paires, on peut se contenter d'examiner +les cas où \emph{soit} il existe une transition de $q_1$ vers $q_2$ +\emph{soit} il existe à la fois une transition de $q_1$ vers $q$ et +une transition de $q$ vers $q_2$. En revanche, insistons bien sur le +fait que le cas où $q_1$ et $q_2$ coïncide doit être traité comme les +autres. \par} -\medskip - -Définition 5.1.5, premier paragraphe, (page 70), retirer la parenthèse -« (fonction) » après « calculable » (qui était destinée à l'index -uniquement). +\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill} \medskip -{\footnotesize +Paragraphe 2.1.7, l'expression rationnelle donnée entre parenthèses +comporte une faute de frappe : page 18, ligne 9 en partant du bas, +remplacer $(b|c){*}a(b|c){*}b(a|b|c){*}$ par +$(b|c){*}a(a|c){*}b(a|b|c){*}$. -Définition 5.1.5, deuxième paragraphe, (page 66), pour éclaircir la -syntaxe, ajouter « et » devant « « non » ($0$) ». +\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill} \medskip -¶5.1.10 (page 72), il manque « comme » avant le dernier mot : -remplacer « donne bien le résultat final de $T$ résultat » par « donne -bien le résultat final de $T$ comme résultat ». - -\medskip +Paragraphe 4.3.2, la grammaire ne devrait pas avoir de +production $\varepsilon$ compte tenu de ce qui en est dit +en-dessous : page 56, ligne 18, remplacer $S \rightarrow U \;|\; V +\;|\; \varepsilon$ par $S \rightarrow U \;|\; V$. -¶5.2.1, note en bas de page 28, (page 73), retirer la virgule après -« Java ». +\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill} \medskip -Démonstration du théorème 5.2.4, premier paragraphe, (page 74), -remplacer « on n'a pas de choix que de ne pas terminer » par « la -seule possibilité est de ne pas terminer ». - -\medskip +Paragraphe 4.3.5, il manque à la grammaire $G'$ des productions $U +\rightarrow \varepsilon$ et $V \rightarrow \varepsilon$ : page 58, +lignes 4–5, remplacer +\[ +\begin{aligned} +U &\rightarrow aUbU\\ +V &\rightarrow bVaV\\ +\end{aligned} +\] +par +\[ +\begin{aligned} +U &\rightarrow aUbU \;|\; \varepsilon\\ +V &\rightarrow bVaV \;|\; \varepsilon\\ +\end{aligned} +\] -Démonstration du théorème 5.2.4, deuxième paragraphe, (page 74), pour -éclaircir la syntaxe, ajouter « et ensuite » devant « (2º) ». -\par} % % diff --git a/exemples-automates.xoj b/exemples-automates.xoj Binary files differnew file mode 100644 index 0000000..0b60119 --- /dev/null +++ b/exemples-automates.xoj diff --git a/misc/quiz-extract-automata.pl b/misc/quiz-extract-automata.pl new file mode 100755 index 0000000..8327ce3 --- /dev/null +++ b/misc/quiz-extract-automata.pl @@ -0,0 +1,53 @@ +#! /usr/local/bin/perl -w + +use strict; +use warnings; + +my $inputfile = $ARGV[0]; +die "please pass input file as argument" unless defined($inputfile); +my $outputdir = "/tmp/automata"; + +my $f; + +open $f, "<", $inputfile or die "can't open $inputfile: $!"; +my %automata; +my $thisname; +while (<$f>) { + $thisname = undef if defined($thisname) && /^\\end\{center\}/; + $automata{$thisname} .= $_ if defined($thisname); + $thisname = $1 if /^\\begin\{center\}\s*\%+\s*NAME:\s*(\S+)/; +} +close $f; + +my $prologue = <<'__EOF__'; +\documentclass[crop,tikz]{standalone} +% +% +% +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +% +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +__EOF__ + +mkdir $outputdir; + +foreach my $name (keys(%automata)) { + chdir $outputdir; + print "Processing $name\n"; + open $f, ">", "${outputdir}/${name}.tex"; + print $f $prologue; + print $f "\\begin{document}\n\n"; + print $f $automata{$name}; + print $f "\n\\end{document}\n"; + close $f; + system "pdflatex", "${name}.tex"; + system "pdf2svg", "${name}.pdf", "${name}.raw.svg"; + system "scour", "-i", "${name}.raw.svg", "-o", "${name}.svg"; + system "rsvg-convert", "${name}.svg", "-d", "300", "-p", "300", "-b", "white", "-o", "${name}.png"; +} diff --git a/notes-inf105.tex b/notes-inf105.tex index 74b3147..b56b958 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1167,7 +1167,7 @@ L'extension la plus fréquente est celle des \emph{références arrière} facteur du mot se retrouve aussi à un autre emplacement. Par exemple, pour beaucoup de moteurs (notamment \texttt{egrep}), l'expression régulière « \texttt{(a*)b\char"5C\relax 1} » désigne le langage -$\{a^nba^n : a\in\mathbb{N}\} = \{b,aba, aabaa,\ldots\}$ des mots +$\{a^nba^n : n\in\mathbb{N}\} = \{b,aba, aabaa,\ldots\}$ des mots formés d'un nombre quelconque de $a$ puis d'un $b$ puis de la \emph{même suite de $a$} (le « \texttt{\char"5C\relax 1} » désigne « une copie de la chaîne de caractères qui a été capturée par le @@ -1229,7 +1229,7 @@ servent à ancrer l'expression au début et à la fin de la chaîne respectivement : c'est-à-dire que rechercher « \texttt{a} » recherche un \texttt{a} quelconque à l'intérieur de la chaîne donnée, rechercher « \texttt{\char"5E\relax a} » demande que le \texttt{a} soit au début -de la chaîne donnée rechercher « \texttt{a\char"24} » demande que le +de la chaîne donnée, rechercher « \texttt{a\char"24} » demande que le \texttt{a} soit à la fin de la chaîne donnée, et rechercher « \texttt{\char"5E\relax a\char"24} » demande que la chaîne donnée soit exactement \texttt{a} (cet exemple n'est donc pas très utile, @@ -1547,7 +1547,7 @@ accepte exactement les mots contenant un $a$ suivi, pas forcément immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un sous-mot (cf. \ref{definition-subword}). Ce langage est donc reconnaissable. (Il est aussi rationnel puisque dénoté par -l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.) +l'expression rationnelle $(b|c){*}a(a|c){*}b(a|b|c){*}$.) \thingy\label{definition-dfa-accessible-state} Un état $q$ d'un DFA est dit \defin[accessible (état)]{accessible} lorsqu'il existe un mot @@ -2757,11 +2757,11 @@ $(\varphi_2(q),x,q')$ où $(q,x,q') \in \delta_2$. (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord un unique état initial $q'_0$ à la réunion disjointe -de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$, -puis en éliminant les ε-transitions qu'on vient d'ajouter -(cf. \ref{removal-of-epsilon-transitions}) ainsi que les états $q_1$ -et $q_2$ devenus inutiles. Cela donne le même résultat que ce qui -vient d'être dit.) +de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$ +(qui cessent d'être initiaux), puis en éliminant les ε-transitions +qu'on vient d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi +que les états $q_1$ et $q_2$ devenus inutiles. Cela donne le même +résultat que ce qui vient d'être dit.) Il est alors clair qu'un chemin de l'état initial à un état final dans cet automate $A'$ consiste soit en un chemin d'un état initial à un @@ -2788,7 +2788,8 @@ L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant chaque transition sortant de $q_2$ par une transition identiquement étiquetée, et de même cible, partant de \emph{chaque} état final -de $A_1$. Graphiquement : +de $A_1$ (ces derniers seront marqués finaux si $q_2$ était final +dans $A_2$). Graphiquement : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] @@ -2852,19 +2853,20 @@ et De façon plus formelle, considérons un nouvel ensemble d'états $Q' = (Q_1 \uplus Q_2) \setminus \{q_2\}$ où $\uplus$ désigne la réunion disjointe. On définit alors l'automate $A'$ dont l'ensemble d'états -est $Q'$, l'état initial est $q_1$, les états finaux $F' = F_2$, et la -relation de transition $\delta$ est la réunion de $\delta_1$, de -l'ensemble des triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$, -et enfin de l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q') -\in \delta_2$ et que $q\in F_1$. +est $Q'$, l'état initial est $q_1$, l'ensemble $F'$ des états finaux +est $F_2$ si $q_2$ n'était pas final dans $A_2$ et $F_1 \cup F_2$ si +$q_2$ était final dans $A_2$, la relation de transition $\delta'$ +est la réunion de $\delta_1$, de l'ensemble des triplets $(q,x,q') \in +\delta_2$ tels que $q\neq q_2$, et enfin de l'ensemble des triplets +$(q,x,q')$ tels que $(q_2,x,q') \in \delta_2$ et que $q\in F_1$. (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord à la réunion disjointe de $A_1$ et $A_2$ une -ε-transition de chaque état final de $A_1$ vers $q_2$, puis en -éliminant les ε-transitions qu'on vient d'ajouter -(cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état $q_2$ -devenu inutile. Cela donne le même résultat que ce qui vient d'être -dit.) +ε-transition de chaque état final de $A_1$ vers $q_2$ (qui cesse +d'être initial), puis en éliminant les ε-transitions qu'on vient +d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état +$q_2$ devenu inutile. Cela donne le même résultat que ce qui vient +d'être dit.) Il est alors clair qu'un chemin de l'état initial $q_1$ à un état final dans cet automate $A'$ consiste en un chemin de $q_1$ à un état @@ -3639,21 +3641,35 @@ Symboliquement : \end{tikzpicture} \end{center} -Cette transformation doit être effectuée \emph{simultanément pour - toute paire} $(q_1,q_2)$ d'états de $A$ pour laquelle -$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$ : pour chaque -telle paire, on remplace l'étiquette de la transition $r_{12}$ entre -eux par $(r_{12}|r_1(s){*}r_2)$. Ceci ne change pas le fonctionnement -de l'automate, car tout chemin dans $A$ peut être remplacé par un -chemin dans $A'$ en effaçant simplement les $q$ (si on considère -$q_1$ et $q_2$ les états avant un bloc de $q$ dans le chemin, on -voit que le chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se -transformer en $q_1 \to q_2$ en consommant un mot qui vérifie -l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$). - -En éliminant (dans n'importe quel ordre) tous les états autres que -$q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant une unique -transition $(q_0,r,q_\infty)$, qui est donc essentiellement +Pour éliminer l'état $q$, cette transformation doit être effectuée +\emph{simultanément pour toute paire} $(q_1,q_2)$ d'états de $A$ (avec +$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$) pour laquelle il +existe une transition de $q_1$ vers $q$ et une transition de +$q$ vers $q_2$, \emph{y compris} s'il n'y avait pas déjà une +transition de $q_1$ vers $q_2$, et \emph{y compris} si $q_1=q_2$ : +pour \emph{chaque} telle paire, on remplace l'étiquette de la +transition $r_{12}$ entre eux par $(r_{12}|r_1(s){*}r_2)$. (On +prendra garde aux cas particuliers suivants : si la transition de $q$ +vers lui-même n'existait pas, ce qui revient à prendre $s=\bot$, alors +on remplace la transition $r_{12}$ par $(r_{12}|r_1 r_2)$ en vertu du +fait que $(\bot){*}$ est équivalente à $\underline{\varepsilon}$ ; et +si la transition de $q_1$ vers $q_2$ n'existait pas, ce qui revient à +prendre $r_{12}=\bot$, alors on la crée avec l'étiquette +$r_1(s){*}r_2$ ; et bien sûr, en combinant ces deux cas particuliers, +s'il n'y avait ni transition de $q$ vers lui-même ni de +$q_1$ vers $q_2$, on crée cette dernière avec l'étiquette $r_1 r_2$.) + +La transformation qui vient d'être décrite ne change pas le +fonctionnement de l'automate, car tout chemin dans $A$ peut être +remplacé par un chemin dans $A'$ en effaçant simplement les $q$ (si on +considère $q_1$ et $q_2$ les états avant un bloc de $q$ dans le +chemin, on voit que le chemin $q_1 \to q \to q \to \cdots \to q \to +q_2$ peut se transformer en $q_1 \to q_2$ en consommant un mot qui +vérifie l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$). + +En éliminant (successivement dans n'importe quel ordre) tous les états +autres que $q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant +une unique transition $(q_0,r,q_\infty)$, qui est donc essentiellement l'expression rationnelle $r$. \end{proof} @@ -5028,7 +5044,7 @@ langage $L(G)$ que la précédente (elle est donc faiblement équivalente l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire (d'axiome $S$) \[ \begin{aligned} -S &\rightarrow U \;|\; V \;|\; \varepsilon\\ +S &\rightarrow U \;|\; V\\ U &\rightarrow aUb \;|\; ab\\ V &\rightarrow aVbb \;|\; abb\\ \end{aligned} @@ -5154,8 +5170,8 @@ Un raisonnement analogue montre que la grammaire $G'$ donnée par \[ \begin{aligned} S &\rightarrow aUbS \;|\; bVaS \;|\; \varepsilon\\ -U &\rightarrow aUbU\\ -V &\rightarrow bVaV\\ +U &\rightarrow aUbU \;|\; \varepsilon\\ +V &\rightarrow bVaV \;|\; \varepsilon\\ \end{aligned} \] engendre le même langage $L = \{w \in\Sigma^* : |w|_a = |w|_b\}$ que diff --git a/programme-inf105.tex b/programme-inf105.tex index 909924c..a65fc55 100644 --- a/programme-inf105.tex +++ b/programme-inf105.tex @@ -102,39 +102,23 @@ peut décider algorithmiquement si deux expressions rationnelles sont \thingy TD sur les automates finis et langages rationnels. -\thingy Grammaires hors contexte\footnote{Je propose pour gagner du - temps de ne faire que mentionner au passage le fait qu'il existe des - grammaires plus générales, sans entrer dans les détails.}, langages -algébriques (=définis par une grammaire hors contexte). Dérivations, -dérivations gauches et droites. Arbre d'analyse (=de dérivation). -Ambiguïté (grammaires inambiguës et ambiguës, exemple sans -démonstration de langage intrinsèquement ambigu). +\thingy Grammaires hors contexte, langages algébriques (=définis par +une grammaire hors contexte). Dérivations\footnote{On pourra même + sauter complètement la notion de dérivation et définir le langage + engendré par une grammaire à travers les arbres d'analyse.}. Arbre +d'analyse (=de dérivation). Ambiguïté (grammaires inambiguës et +ambiguës). Stabilité des langages algébriques par réunion, concaténation et étoile de Kleene. Les langages rationnels sont algébriques : d'après ce qu'on vient de dire et directement en associant une grammaire à un DFA ou NFA. -\thingy L'intersection d'un langage algébrique et d'un langage +L'intersection d'un langage algébrique et d'un langage rationnel est algébrique (admis sans démonstration). -Lemme de pompage pour les langages algébriques (admis sans -démonstration, mais on peut esquisser l'idée). - L'appartenance d'un mot au langage défini par une grammaire hors -contexte est algorithmiquement décidable (l'énoncer et éventuellement -expliquer une approche possible\footnote{Par ex., en montrant qu'on - peut trouver une grammaire monotone équivalente ; ou bien esquisser - comment on peut mettre la grammaire sous forme normale de Chomsky et - utiliser l'algorithme de programmation dynamique (CYK) ?} si le -temps le permet). - -Selon le temps disponible : quelques notions sur l'analyse syntaxique -en pratique : notion d'analyseurs descendants et ascendants (sans -entrer dans les détails). - - -\thingy TD sur les grammaires hors contexte et langages algébriques. +contexte est algorithmiquement décidable (admis sans démonstration). \thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas @@ -154,7 +138,8 @@ semi-décidables. Un ensemble est semi-décidable ssi il est (vide ou) \thingy Notion de machine universelle. Indécidabilité du problème de l'arrêt. -Petit TD sur la calculabilité. +\thingy TD sur les grammaires hors contexte / langages algébriques, et +sur la calculabilité. % diff --git a/quiz-20220428.tex b/quiz-20220428.tex new file mode 100644 index 0000000..faec769 --- /dev/null +++ b/quiz-20220428.tex @@ -0,0 +1,238 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\newcounter{quescnt} +\newenvironment{question}% +{\stepcounter{quescnt}\bigskip\noindent\textbf{Question~\arabic{quescnt}.}\par\nobreak} +{\relax} +\newcounter{answcnt}[quescnt] +\newcommand\answer{% +\stepcounter{answcnt}\smallskip\textbf{(\Alph{answcnt})}~} +\newcommand\rightanswer{% +\stepcounter{answcnt}\smallskip\leavevmode\llap{$\rightarrow$}\textbf{(\Alph{answcnt})}~} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +% +\begin{document} + +\textbf{Questions pour INF105 pour le QCM du 2022-04-28.} + +Chaque question comporte \emph{une et une seule réponse correcte}. +Elle a été indiquée par une flèche ci-dessous : + + +% +% +% + +\begin{question} + +Lequel des mots suivants est un facteur de $abcabcabc$ sur +l'alphabet $\Sigma := \{a,b,c\}$ ? + +\answer +$abab$ + +\answer +$aaac$ + +\answer +$bcbc$ + +\rightanswer +$cabc$ + +\end{question} + + +% +% +% + +\begin{question} + +Lequel des mots suivants est un sous-mot de $abcabcabc$ sur +l'alphabet $\Sigma := \{a,b,c\}$ ? + +\answer +$abacbab$ + +\rightanswer +$acbbc$ + +\answer +$aabbcc$ + +\answer +$acbacb$ + +\end{question} + + +% +% +% + +\begin{question} + +Lequel des mots suivants appartient au langage dénoté par l'expression +rationnelle $(ab){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ? + +\answer +$aabbab$ + +\answer +$bababa$ + +\rightanswer +$ababab$ + +\answer +$aaabbb$ + +\end{question} + + +% +% +% + +\begin{question} + +Lequel des mots suivants appartient au langage dénoté par l'expression +rationnelle $a{*}b{*}a{*}b{*}$ sur l'alphabet $\Sigma := \{a,b\}$ ? + +\rightanswer +$aaabbb$ + +\answer +$ababab$ + +\answer +$babbba$ + +\answer +$baaaba$ + +\end{question} + + +% +% +% + +\begin{question} + +Lequel des mots suivants appartient au langage dénoté par l'expression +rationnelle $a{*}(bba{*}){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ? + +\rightanswer +$abbbba$ + +\answer +$aaabbb$ + +\answer +$abbaab$ + +\answer +$abaabb$ + +\end{question} + + +% +% +% + +\begin{question} + +Quel langage dénote l'expression rationnelle $a{*}(ba{*}ba{*}){*}$ sur +l'alphabet $\Sigma := \{a,b\}$ ? + +\answer +l'ensemble $\Sigma^*$ de tous les mots + +\rightanswer +l'ensemble des mots dont le nombre total de $b$ est pair + +\answer +l'ensemble des mots dont le nombre total de $b$ est $\geq 2$ + +\answer +l'ensemble des mots commençant et finissant à la fois par un $a$ + +\answer +l'ensemble des mots commençant par un $a$ + +\end{question} + + +% +% +% + +\begin{question} + +Laquelle des expressions rationnelles suivantes est équivalente à +l'expression $(aa\,|\,aba)$ sur l'alphabet $\Sigma := \{a,b\}$ ? + +\answer +$ab{*}a$ + +\answer +$a{*}ba{*}$ + +\rightanswer +$a(\underline{\varepsilon}|b)a$ + +\answer +$(a|ab)(ab|a)$ + +\end{question} + + +% +% +% + +\begin{question} + +Laquelle des expressions rationnelles suivantes est équivalente à +l'expression $(ab){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ? + +\answer +$(a|b){*}$ + +\answer +$ab(ab){*}$ + +\answer +$(ba){*}$ + +\rightanswer +$\underline{\varepsilon} \,|\, a(ba){*}b$ + +\end{question} + + +% +% +% +\end{document} diff --git a/quiz-20220602.tex b/quiz-20220602.tex new file mode 100644 index 0000000..93183ff --- /dev/null +++ b/quiz-20220602.tex @@ -0,0 +1,432 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +% +\newcounter{quescnt} +\newenvironment{question}% +{\stepcounter{quescnt}\bigskip\noindent\textbf{Question~\arabic{quescnt}.}\par\nobreak} +{\relax} +\newcounter{answcnt}[quescnt] +\newcommand\answer{% +\stepcounter{answcnt}\smallskip\textbf{(\Alph{answcnt})}~} +\newcommand\rightanswer{% +\stepcounter{answcnt}\smallskip\leavevmode\llap{$\rightarrow$}\textbf{(\Alph{answcnt})}~} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} + +\textbf{Questions pour INF105 pour le QCM du 2022-06-02.} + +Chaque question comporte \emph{une et une seule réponse correcte}. +Elle a été indiquée par une flèche ci-dessous : + + +% +% +% + +\begin{question} + +Parmi les différents langages ci-dessous sur l'alphabet $\Sigma := +\{a,b\}$, qui sont tous des sous-ensembles du langage rationnel $L_0 +:= L(a{*}b{*}) = \{a^i b^j : i,j \in \mathbb{N}\}$, un seul est +rationnel : lequel ? + +\answer +Le langage $\{a^i b^j : i=j\}$ formé des mots de $L_0$ ayant le même +nombre de $a$ que de $b$. + +\answer +Le langage $\{a^i b^j : i\geq j\}$ formé des mots de $L_0$ ayant au +moins autant de $a$ que de $b$. + +\answer +Le langage $\{a^i b^j : i\neq j\}$ formé des mots de $L_0$ ayant un +nombre différent de $a$ et de $b$. + +\rightanswer +Le langage $\{a^i b^j : i\equiv j \pmod{12}\}$ formé des mots de $L_0$ +tels que le nombre de $a$ et de $b$ soient congrus l'un à l'autre modulo $12$ +(c'est-à-dire que la différence entre ces deux nombres soit multiple +de $12$). + +\end{question} + + +% +% +% + +\begin{question} + +Parmi les différents langages ci-dessous sur l'alphabet $\Sigma := +\{a,b\}$, un seul \emph{n'est pas} rationnel : lequel ? + +\answer +Le langage des mots $w$ comportant exactement $42$ lettres $a$ (au +total, c'est-à-dire $|w|_a = 42$). + +\rightanswer +Le langage des mots $w$ comportant exactement autant de lettres $a$ +que de lettres $b$ (au total, c'est-à-dire $|w|_a = |w|_b$). + +\answer +Le langage des mots qui \emph{n'ont pas} le mot “$abbab$” comme facteur. + +\answer +Le langage des mots qui \emph{n'ont pas} le mot “$abbab$” comme sous-mot. + +\answer +Le langage des mots qui \emph{ne sont pas} un sous-mot de “$abbab$”. + +\end{question} + + +% +% +% + +\begin{question} + +Parmi les différents langages ci-dessous sur l'alphabet $\Sigma := +\{a,b,c\}$, un seul \emph{n'est pas} rationnel : lequel ? + +\answer +Le langage des mots de longueur $\geq 3$ dont la troisième lettre (à +partir du début) est identique à la troisième lettre à partir de la +fin. + +\answer +Le langage des mots de longueur $\geq 3$ dont chaque troisième lettre +(c'est-à-dire la troisième, la sixième, la neuvième, etc., jusqu'à la +fin du mot) sont toutes identiques. + +\rightanswer +Le langage des mots de longueur impaire dont la lettre du milieu est +un $a$. + +\end{question} + + +% +% +% + +\begin{question} + +Quel langage reconnaît l'automate fini sur l'alphabet $\Sigma := +\{a,b\}$ représenté ci-dessous ? + +\begin{center} %% NAME: q4 +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$}; +\node (q2) at (70bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (00bp,-70bp) [draw,circle,state] {$3$}; +\node (q4) at (70bp,-70bp) [draw,circle,state,final] {$4$}; + \draw [->] (q1) to node[auto] {$a$} (q2); + \draw [->] (q3) to node[auto] {$a$} (q4); + \draw [->] (q1) to node[auto] {$b$} (q3); + \draw [->] (q2) to node[auto] {$b$} (q4); + \draw [->] (q1) to[loop above] node[auto] {$a,b$} (q1); + \draw [->] (q4) to[loop below] node[auto] {$a,b$} (q4); +\end{tikzpicture} +\end{center} + +\rightanswer +Le langage formé des mots de longueur $\geq 2$ dont toutes les lettres +ne sont pas identiques. + +\answer +Le langage formé des mots de longueur $\geq 2$ dont la dernière lettre +est identique à la première. + +\answer +Le langage formé des mots comportant au moins deux $a$ ou bien +comportant au moins deux $b$. + +\answer +Le langage formé des mots dont le nombre de $a$ et le nombre de $b$ +sont tous les deux pairs. + +\answer +Le langage formé des mots ayant $ab$ comme facteur. + +\end{question} + + +% +% +% + +\begin{question} + +L'élimination des transitions spontanées sur l'automate fini sur +l'alphabet $\Sigma := \{a,b\}$ représenté ci-dessous + +\begin{center} %% NAME: q5 +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$}; +\node (q2) at (70bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (140bp,0bp) [draw,circle,state,final] {$3$}; + \draw [->] (q1) to node[auto] {$a$} (q2); + \draw [->] (q2) to node[auto] {$b$} (q3); + \draw [->,out=270,in=270] (q3) to node[above] {$\varepsilon$} (q1); +\end{tikzpicture} +\end{center} + +\noindent s'obtient-elle... + +\rightanswer +En supprimant la transition étiquetée $\varepsilon$ reliant $3$ à $1$ +et en ajoutant une transition étiquetée $a$ reliant $3$ à $2$ ? + +\answer +En supprimant la transition étiquetée $\varepsilon$ reliant $3$ à $1$ +et en ajoutant une transition étiquetée $a$ reliant $2$ à $1$ ? + +\answer +En remplaçant la transition étiquetée $\varepsilon$ reliant $3$ à $1$ +par une transition étiquetée $a$ (toujours reliant $3$ à $1$) ? + +\answer +En remplaçant la transition étiquetée $\varepsilon$ reliant $3$ à $1$ +par une transition étiquetée $b$ (toujours reliant $3$ à $1$) ? + +\end{question} + + +% +% +% + +\begin{question} + +Quel est le langage reconnu par l'automate ci-dessous ? + +\begin{center} %% NAME: q6 +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial above,final,accepting below] {$1$}; +\node (q2) at (70bp,0bp) [draw,circle,state,initial above,final,accepting below] {$2$}; +\node (q3) at (140bp,0bp) [draw,circle,state,initial above,final,accepting below] {$3$}; + \draw [->] (q1) to node[auto] {$a$} (q2); + \draw [->] (q2) to node[auto] {$b$} (q3); +\end{tikzpicture} +\end{center} + +\rightanswer +$\{\varepsilon,a,b,ab\}$ + +\answer +$\{\varepsilon,ab\}$ + +\answer +$\{\varepsilon,a,b,ab,ba\}$ + +\answer +$\{\varepsilon,ab,ba\}$ + +\answer +$\{a,b,ab\}$ + +\answer +$\{ab\}$ + +\answer +$\varnothing$ + +\end{question} + + +% +% +% + +\begin{question} + +Quel est le langage reconnu par l'automate ci-dessous ? + +\begin{center} %% NAME: q7 +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,final,accepting below] {$1$}; +\node (q2) at (70bp,0bp) [draw,circle,state,initial above,final,accepting below] {$2$}; +\node (q3) at (140bp,0bp) [draw,circle,state,initial above] {$3$}; + \draw [->] (q1) to node[auto] {$a$} (q2); + \draw [->] (q2) to node[auto] {$b$} (q3); +\end{tikzpicture} +\end{center} + +\answer +$\{\varepsilon,a,b,ab\}$ + +\answer +$\{\varepsilon,ba\}$ + +\answer +$\{\varepsilon,a,b,ab,ba\}$ + +\answer +$\{\varepsilon,ab,ba\}$ + +\answer +$\{\varepsilon,a,b\}$ + +\rightanswer +$\{\varepsilon\}$ + +\answer +$\varnothing$ + +\end{question} + + +% +% +% + +\begin{question} + +L'automate canonique (= automate fini déterministe complet ayant le +nombre minimum possible d'états) équivalent à l'automate $\mathscr{A}$ +représenté ci-dessous + +\begin{center} %% NAME: q8 +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$}; +\node (q2) at (70bp,0bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (140bp,0bp) [draw,circle,state,final] {$3$}; + \draw [->] (q1) to[loop above] node[auto] {$a$} (q1); + \draw [->] (q1) to node[auto] {$b$} (q2); + \draw [->] (q2) to[loop above] node[auto] {$b$} (q2); + \draw [->] (q2) to node[auto] {$a$} (q3); + \draw [->] (q3) to[loop above] node[auto] {$a,b$} (q3); +\end{tikzpicture} +\end{center} + +\noindent s'obtient-il... + +\answer +En ne changeant rien (l'automate $\mathscr{A}$ est déjà minimal) ? + +\rightanswer +En fusionnant les états $2$ et $3$ (donnant un automate minimal à deux états) ? + +\answer +En fusionnant les états $1$ et $2$ (donnant un automate minimal à deux états) ? + +\answer +En fusionnant tous les états (donnant un automate minimal à un seul état) ? + +\end{question} + + +% +% +% + +\begin{question} + +Parmi les expressions rationnelles ci-dessous, laquelle dénote le +langage reconnu par l'automate suivant ? + +\begin{center} %% NAME: q9 +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$}; +\node (q2) at (70bp,0bp) [draw,circle,state,final] {$2$}; + \draw [->] (q1) to[loop above] node[auto] {$a$} (q1); + \draw [->,out=30,in=150] (q1) to node[auto] {$\varepsilon$} (q2); + \draw [->,out=210,in=330] (q2) to node[auto] {$\varepsilon$} (q1); + \draw [->] (q2) to[loop above] node[auto] {$b$} (q2); +\end{tikzpicture} +\end{center} + +\rightanswer +$(a|b){*}$ + +\answer +$(ab|ba){*}$ + +\answer +$(aa|bb){*}$ + +\answer +$a{*}\,|\,b{*}$ + +\answer +$a(a|b){*}b$ + +\end{question} + + +% +% +% + +\begin{question} + +Parmi les expressions rationnelles ci-dessous, laquelle dénote le +langage reconnu par l'automate suivant ? (Note : l'expression +correcte ci-dessous est obtenue en éliminant les états dans +l'ordre $3,2,1$.) + +\begin{center} %% NAME: q10 +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (60bp,35bp) [draw,circle,state] {$2$}; +\node (q3) at (60bp,-35bp) [draw,circle,state] {$3$}; + \draw [<-] (q1) -- ++(-20bp,20bp); + \draw [->] (q1) -- ++(-20bp,-20bp); + \draw [->,out=90,in=150] (q1) to node[auto] {$a$} (q2); + \draw [->,out=330,in=30] (q2) to node[auto] {$b$} (q3); + \draw [->,out=210,in=270] (q3) to node[auto] {$c$} (q1); + \draw [->] (q2) to node[auto] {$a$} (q1); + \draw [->] (q3) to node[auto] {$b$} (q2); + \draw [->] (q1) to node[auto] {$c$} (q3); +\end{tikzpicture} +\end{center} + +\rightanswer +$(cc\,|\,(a|cb)(bb){*}(a|bc)){*}$ + +\answer +$(a(b(cc){*}b){*}a){*}$ + +\answer +$(abc|cba){*}$ + +\answer +$(aa|b(aa|cc)b|cc){*}$ + +\end{question} + + +% +% +% +\end{document} diff --git a/rattrapage-20230621.tex b/rattrapage-20230621.tex new file mode 100644 index 0000000..27d0168 --- /dev/null +++ b/rattrapage-20230621.tex @@ -0,0 +1,575 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +\usepackage{hyperref} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +\newenvironment{commentaire}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}} +{{\hbox{}\nobreak\hfill\maltese}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% NOTE: compile dot files with +% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} +\ifcorrige +\title{INF105\\Contrôle de connaissances (rattrapage) — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de connaissances (rattrapage)\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{21 juin 2023} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +\medbreak + +Documents autorisés : uniquement une feuille A4 recto-verso +(manuscrite ou typographiée). + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 1h30 + +\ifcorrige +Ce corrigé comporte 6 pages (page de garde incluse). +\else +Cet énoncé comporte 3 pages (page de garde incluse). +\fi + +\vfill + +{\tiny\noindent +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +% NOTE: Initially copied from controle-20180322.tex + +Dans cet exercice, on pose $\Sigma = \{a,b,c\}$. On appelle $L$ le +langage des mots sur $\Sigma$ qui ont $abc$ comme sous-mot, +c'est-à-dire, qui contiennent un $a$, un $b$ et un $c$ dans cet ordre +mais non nécessairement consécutivement (à titre d'exemple, $abac \in +L$). + +\textbf{(1)} Proposer un automate non-déterministe (NFA), sans +transition spontanée, $\mathscr{A}_1$ qui reconnaît le langage $L$. +On justifiera rapidement pourquoi l'automate proposé convient. + +\begin{corrige} +On peut proposer l'automate $\mathscr{A}_1$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3$}; +\draw [->] (q0) to[loop below] node[auto] {$a,b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,b,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b,c$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +Pour se convaincre qu'il convient, on remarque qu'un chemin de +l'unique état initial ($0$) à l'unique état final ($3$) dans cet +automate est formé par trois transitions $0\to 1$, $1\to 2$ et $2\to +3$, étiquetées par les lettres $a$, $b$ et $c$ respectivement, +intercalées d'un nombre quelconque de transitions d'un état vers +lui-même, étiquetées par une lettre quelconque : la lecture de ses +étiquettes donne bien un mot ayant $abc$ comme sous-mot ; et +réciproquement, tout tel mot étiquette un chemin de $0$ à $3$ (une +fois choisies les lettres $a,b,c$ dans l'ordre qui correspondront aux +transitions changeant d'état). + +\emph{Remarque :} il est correct de donner directement l'automate +déterministe $\mathscr{A}_2$ représenté ci-dessous (puisque tout DFA +est, en particulier, un NFA), à condition de justifier proprement +qu'il convient. +\end{corrige} + +\textbf{(2)} Déterminiser (si nécessaire) l'automate $\mathscr{A}_1$ +trouvé en (1) ; on appellera $\mathscr{A}_2$ l'automate résultant. + +\begin{corrige} +En notant $0':=\{0\}$, $1' := \{0,1\}$, $2' := \{0,1,2\}$ et $3' := +\{0,1,2,3\}$ les états de l'automate déterministe $\mathscr{A}_2$ qui +correspondent aux ensembles d'états de l'automate $\mathscr{A}_1$ +qu'on vient d'indiquer, la déterminisation conduit à l'automate +$\mathscr{A}_2$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$}; +\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3'$}; +\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +\textbf{(3)} Minimiser (si nécessaire) l'automate $\mathscr{A}_2$ +obtenu en (2) ; on appellera $\mathscr{A}_3$ l'automate minimal +(=canonique) résultant. + +\begin{corrige} +On part bien d'un automate $\mathscr{A}_2$ déterministe complet sans +état inaccessible. La première étape de l'algorithme de minimisation +sépare deux classes d'états : $0',1',2'$ (non finaux) d'une part et +$3'$ (final) de l'autre. Ensuite on sépare $0',1'$ d'une part et $2'$ +de l'autre (car les premiers ne conduisent qu'à des états non finaux, +tandis que $2'$ conduit à un état final par la transition +étiquetée $c$). L'étape suivante sépare $0'$ et $1'$ (car le premier +ne conduit qu'à un état de la classe $\{0',1'\}$ de l'étape +précédente, tandis que $1'$ conduit à un état de la classe $\{2'\}$ +par la transition étiquetée $b$). On a donc séparé tous les états, ce +qui montre que $\mathscr{A}_3 = \mathscr{A}_2$ est minimal. + +\emph{Remarque :} on pouvait aussi invoquer l'argument suivant : +puisque le mot $abc$ doit être accepté et qu'aucun de ses sous-mots +stricts ne l'est (ce qui exclut qu'il y ait une boucle dans le chemin +d'acceptation), il faut au moins $|abc|+1 = 4$ états dans n'importe +quel automate reconnaissant $L$. Comme $\mathscr{A}_2$ a +effectivement $4$ états, il est forcément minimal. +\end{corrige} + +\textbf{(4)} Construire un automate $\mathscr{A}_4$ reconnaissant le +langage $M := \Sigma^*\setminus L$ complémentaire de $L$. + +\begin{corrige} +On obtient $\mathscr{A}_4$ en échangeant états finaux et non finaux +dans $\mathscr{A}_3 = \mathscr{A}_2$, c'est-à-dire l'automate +$\mathscr{A}_4$ suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state,final,accepting above] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state,final,accepting above] {$2'$}; +\node (q3) at (210bp,0bp) [draw,circle,state] {$3'$}; +\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2); +\draw [->] (q2) -- node[auto] {$c$} (q3); +\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +\textbf{(5)} En appliquant à $\mathscr{A}_4$ la méthode d'élimination +des états, déterminer une expression rationnelle dénotant le +langage $M$. (Si on souhaite obtenir une expression plus compacte, il +est recommandé de commencer l'élimination des états par ceux qui sont +le plus loin de l'état initial.) + +\begin{corrige} +On va manipuler des automates finis à transitions étiquetées par des +expressions rationnelles (ou « RNFA »). Dans un premier temps, on +donne à l'automate un unique état final $F$ en faisant pointer vers +lui une transition spontanée (i.e., étiquetée +par $\underline{\varepsilon}$) depuis tout état qui était final, et un +unique état initial $I$ depuis lequel on fait partir une transition +spontanée vers $0'$. L'état $3'$ peut être éliminé d'emblée puisqu'il +est inutile (il n'est pas co-accessible : c'est un puits !). Par +ailleurs, deux transitions entre les mêmes états sont remplacées par +une seule étiquetée par la disjonction des étiquettes (par exemple, +les deux transitions $0'\to 0'$ étiquetées $b$ et $c$ sont remplacées +par une seule étiquetée $b|c$). On a donc affaire à l'automate +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1); +\draw [->] (q1) -- node[auto] {$b$} (q2); +\draw [->] (q2) to[loop below] node[auto] {$a|b$} (q2); +\draw [->] (q2) -- node[auto] {$\underline{\varepsilon}$} (qF); +\draw [->] (q1) to[out=45,in=135] node[auto] {$\underline{\varepsilon}$} (qF); +\draw [->] (q0) to[out=90,in=180] (70bp,60bp) to node[auto] {$\underline{\varepsilon}$} (140bp,60bp) to[out=0,in=90] (qF); +\end{tikzpicture} +\end{center} +On élimine maintenant l'état $2'$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$a$} (q1); +\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1); +\draw [->] (q1) -- node[auto] {$\underline{\varepsilon}|b(a|b){*}$} (qF); +\draw [->] (q0) to[out=90,in=180] (70bp,40bp) to node[auto] {$\underline{\varepsilon}$} (140bp,40bp) to[out=0,in=90] (qF); +\end{tikzpicture} +\end{center} +(on a fait usage du fait évident que l'expression rationnelle +$r\underline{\varepsilon}$ est équivalente à $r$). On élimine +ensuite l'état $1'$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$}; +\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$}; +\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$}; +\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0); +\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0); +\draw [->] (q0) -- node[auto] {$\underline{\varepsilon}|a(a|c){*}(\underline{\varepsilon}|b(a|b){*})$} (qF); +\end{tikzpicture} +\end{center} +Enfin, l'élimination de l'état $0'$ conduit au RNFA ayant seulement +deux états $I$ et $F$ reliés par une transition étiquetée par +\[ +(b|c){*}\Big(\underline{\varepsilon}|a(a|c){*}\big(\underline{\varepsilon}|b(a|b){*}\big)\Big) +\] +qui est l'expression rationnelle recherchée (dénotant $M$). + +L'élimination des états dans l'ordre $0',1',2'$ conduirait à +l'expression rationnelle moins compacte +\[ +\underline{\varepsilon}\;|\;(b|c){*}\;|\;(b|c){*}a(a|c){*}\;|\;(b|c){*}a(a|c){*}b(a|b){*} +\] +qui est cependant sans doute plus lisible. + +\emph{Remarque :} le langage $M$ est aussi dénoté par l'expression +rationnelle plus simple $(b|c){*}\,(a|c){*}\,(a|b){*}$, mais celle-ci +ne répond pas à la question car elle ne peut pas s'obtenir par +élimination des états à partir de $\mathscr{A}_4$. +\end{corrige} + + +% +% +% + +\exercice + +% NOTE: Initially copied from controle-20180322.tex + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On appelle $L = L(G)$ +le langage défini par la grammaire hors-contexte $G$ d'axiome $S$ et de +nonterminaux $N = \{S\}$ sur l'alphabet $\Sigma$ donnée par +\[ +\begin{aligned} +S &\rightarrow aSbS \;|\; aS \;|\; \varepsilon\\ +\end{aligned} +\] + +Les questions de cet exercice sont essentiellement indépendantes, si +ce n'est que la question (6) fait appel à la conclusion (énoncée) des +questions (2) à (5). + +\smallskip + +\textbf{(1)} Donner deux arbres d'analyse (pour $G$) différents du +mot $aab$. Que peut-on dire de la grammaire $G$ ? + +\begin{corrige} +On peut proposer les arbres d'analyse suivants :\\ +% S<a.S<a.S<e.>>b.S<e.>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (42.500bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S1) at (30.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a1); +\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S2) -- (e0); +\node (b0) at (60.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (S3) at (80.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S3); +\node (e1) at (80.000bp,-50.000bp) [draw=none] {$\varepsilon$}; \draw (S3) -- (e1); +\end{tikzpicture} +d'une part,\hfill et +% S<a.S<a.S<e.>b.S<e.>>> +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (25.000bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S1) at (50.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a1); +\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S2) -- (e0); +\node (b0) at (60.000bp,-60.000bp) [draw=none] {$b$}; \draw (S1) -- (b0); +\node (S3) at (80.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S3); +\node (e1) at (80.000bp,-80.000bp) [draw=none] {$\varepsilon$}; \draw (S3) -- (e1); +\end{tikzpicture} +d'autre part\\ +(en fait, on peut se convaincre que ce sont les seuls possibles). +La grammaire $G$ est donc ambiguë. +\end{corrige} + +L'objet des questions suivantes est de montrer que $L$ n'est pas +rationnel. + +Soit $M$ le langage $\{a^i b^j : i,j\in\mathbb{N}\}$ constitué des +mots de la forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels +quelconques. + +\textbf{(2)} Donner une expression rationnelle qui dénote $M$. + +\begin{corrige} +Le langage $M$ est dénoté par l'expression rationnelle $a{*}b{*}$. +\end{corrige} + +Soit $P$ le langage $\{a^i b^j : i\geq j\}$ constitué des mots de la +forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels vérifiant $i\geq +j$ (autrement dit, les mots de $M$ qui ont au moins autant de $a$ que +de $b$). + +\textbf{(3)} Montrer que $P \subseteq L$. + +\begin{corrige} +Soient $i\geq j$ deux entiers naturels : on va expliquer comment +produire le mot $a^i b^j$ selon les règles de $G$. À partir de +l'axiome $S$, on commence par appliquer $i-j$ fois la règle $a +\rightarrow aS$, ce qui donne $a \Rightarrow aS \Rightarrow aaS +\Rightarrow \cdots \Rightarrow a^{i-j} S$. Appliquons maintenant $j$ +fois la règle $S\rightarrow aSbS$, suivie à chaque fois de +$S\rightarrow\varepsilon$ sur le $S$ de droite : on obtient ainsi +$a^{i-j} S \Rightarrow a^{i-j+1} S bS \Rightarrow a^{i-j+1} S b +\Rightarrow a^{i-j+2} S b S b \Rightarrow a^{i-j+2} S bb \Rightarrow +\cdots \Rightarrow a^i S b^j$. Il suffit de terminer par une +application de $S \rightarrow \varepsilon$ : on obtient ainsi une +dérivation $S \mathrel{\Rightarrow^*} a^i b^j$ qui prouve que $a^i b^j +\in L$. + +(On pouvait aussi, plus informellement, esquisser l'allure d'un arbre +de dérivation de $a^i b^j$ un peu à la manière de l'un ou l'autre de +ceux de la question (1), mais en appliquant $i-j$ fois la règle $a +\rightarrow aS$ et $j$ fois la règle $S \rightarrow aSbS$.) +\end{corrige} + +\textbf{(4)} Montrer que $L\cap M \subseteq P$. + +\begin{corrige} +Considérons la propriété « avoir (au total) au moins autant de $a$ que +de $b$ », ou si on veut $|\xi|_a\geq |\xi|_b$, sur un pseudo-mot $\xi$ +(un « pseudo-mot » signifiant, par définition, un mot sur $\Sigma\cup +N = \{a,b,S\}$). Cette propriété est vérifiée par le pseudo-mot $S$. +Elle est préservée si on remplace $S$ par $aSbS$ ou $aS$ ou +$\varepsilon$ puisque dans chacun de ces cas le nombre de $a$ augmente +d'au moins autant que le nombre de $b$. Elle est donc possédée par +tout pseudo-mot, et en particulier tout mot, qui dérive de $S$ +selon $G$. On vient donc de prouver que tout mot de $L$ a au moins +autant de $a$ que de $b$. Notamment, tout mot de $L\cap M$ est un mot +de la forme $a^i b^j$ (par définition de $M$), et qui vérifie $i\geq +j$ (c'est ce qu'on vient de prouver). Il est donc dans $P$. +\end{corrige} + +\textbf{(5)} Montrer que $P$ n'est pas rationnel. + +\begin{corrige} +Supposons par l'absurde que $P = \{a^i b^j : i\geq j\}$ soit +rationnel. Appliquons le lemme de pompage pour les langages +rationnels au langage $P$ : appelons $k$ l'entier dont le lemme de +pompage garantit l'existence. Considérons le mot $t := a^k b^k$ (qui +appartient bien à $P$ et est bien de longueur $\geq k$) : il doit +alors exister une factorisation $t = uvw$ (avec $u,v,w \in \Sigma^*$, +non nécessairement dans $P$) pour laquelle on a +(i) $|v|\geq 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in P$ pour +tout $i\geq 0$. La propriété (ii) assure que $uv$ est formé d'un +certain nombre de répétitions de la lettre $a$ (car tout préfixe de +longueur $\leq k$ de $a^k b^k$ est de cette forme) ; disons $u = +a^\ell$ et $v = a^m$, si bien que $w = a^{k-\ell-m} b^k$. La +propriété (i) donne $m\geq 1$. Enfin, la propriété (iii) affirme que +le mot $uv^iw = a^{k+(i-1)m} b^k$ appartient à $P$ ; or pour $i=0$, +ceci est faux puisque $a^{k-m} b^k$ vérifie $k-m < k$. On a donc +abouti à une contradiction, et c'est que $P$ n'est pas rationnel. +\end{corrige} + +\textbf{(6)} Déduire des questions (2) à (5) que $L$ n'est pas +rationnel (on explicitera très soigneusement le raisonnement). + +\begin{corrige} +On a vu à la question (3) que $P \subseteq L$ ; il est par ailleurs +trivial que $P \subseteq M$, et on a donc $P \subseteq L\cap M$. Mais +on a vu à la question (4) que $L\cap M \subseteq P$ : on a donc $L\cap +M = P$. Le langage $M$ est rationnel d'après la question (2). Si le +langage $L$ était lui aussi rationnel, le langage $L\cap M$ +(c'est-à-dire $P$) le serait car l'intersection de deux langages +rationnels est rationnelle. Or on a vu à la question (5) que $P$ +n'est pas rationnel. C'est donc que $L$ ne l'est pas. +\end{corrige} + + +% +% +% + +\exercice + +% NOTE: Initially copied from controle-20210618.tex + +(Les deux questions suivantes sont indépendantes.) + +\smallskip + +\textbf{(1)} Le langage $\{a^n b^n c^n : n\in\mathbb{N}\}$ n'est pas +algébrique\footnote{Ce fait est démontré dans le poly, dans la section + consacrée au lemme de pompage pour les langages algébriques et comme + illustration de ce dernier ; on ne demande pas ici de le + redémontrer : on peut le tenir pour admis.}. Est-il rationnel ? +Est-il décidable ? Est-il semi-décidable ? On justifiera +soigneusement les réponses. + +\begin{corrige} +Le langage proposé n'est pas rationnel car il n'est pas algébrique. + +Il est décidable car il est évident qu'on peut algorithmiquement d'une +part vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci +correspond à l'expression rationnelle $a{*}b{*}c{*}$, c'est faisable +par automate fini) et d'autre part vérifier qu'il a autant de $a$ que +de $b$ que de $c$. + +Étant décidable, il est notamment semi-décidable. +\end{corrige} + +\smallskip + +\textbf{(2)} On rappelle la définition du problème de l'arrêt : c'est +l'ensemble $H$ des couples\footnote{Pour être rigoureux, on a fixé un + codage permettant de représenter les programmes $e$, les entrées $x$ + à ces programmes, et les couples $(e,x)$, comme des éléments + de $\mathbb{N}$ (ou bien de $\Sigma^*$ sur un alphabet + $\Sigma\neq\varnothing$ arbitraire). Il n'est pas nécessaire de + faire apparaître ce codage dans la description des algorithmes + proposés, qui peut rester informelle.} $(e,x)$ formés d'un programme +(= algorithme) $e$ et d'une entrée $x$, tels que l'exécution du +programme $e$ sur l'entrée $x$ termine en temps fini. On a vu en +cours que $H$ était semi-décidable mais non décidable. + +On considère l'ensemble $J$ des triplets $(e_1,e_2,x)$ tels que +$(e_1,x) \in H$ et $(e_2,x) \not\in H$. Autrement dit, le programme +$e_1$ termine en temps fini quand on l'exécute sur l'entrée $x$ mais +le programme $e_2$, lui, ne termine pas sur cette même entrée. +L'ensemble $J$ est-il décidable ? Semi-décidable ? On justifiera +soigneusement. + +\begin{corrige} +L'ensemble $J$ n'est pas semi-décidable. + +Pour le montrer, supposons par l'absurde qu'on dispose d'un algorithme +$T$ qui semi-décide $J$ (où « semi-décider » un ensemble $Z$ +signifie : terminer en renvoyant $1$ (=vrai) si l'entrée $z$ fournie +appartient à $Z$, et ne pas terminer sinon). Fixons une fois pour +toutes (le code d')un programme $f$ qui, donnée une entrée $x$, +termine immédiatement (en ignorant $x$). Alors trivialement $(f,x) +\in H$ quel que soit $x$ ; donc, par définition de $J$, on a $(f,e,x) +\in J$ si et seulement si $(e,h) \not \in H$. + +On considère alors l'algorithme $T'$, défini de la manière suivante : +donnés $(e,x)$, on applique l'algorithme $T$ (qu'on a supposé exister) +au triplet $(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in +J$), on renvoie $1$ (sinon, bien sûr, on ne termine jamais). Par +construction, $T'$ termine en renvoyant $1$ sur l'entrée $(e,x)$ si +$(f,e,x) \in J$, c'est-à-dire $(e,x) \not\in H$, et sinon il ne +termine pas. Ceci signifie que $T'$ semi-décide le complémentaire +de $H$. + +Or le complémentaire de $H$ n'est pas semi-décidable (car si le +complémentaire de $H$ était semi-décidable, on aurait à la fois $H$ et +son complémentaire semi-décidables, donc $H$ serait décidable, et on +sait qu'il ne l'est pas), donc un tel algorithme $T'$ ne peut pas +exister. C'est une contradiction : $J$ n'est donc pas semi-décidable. + +\textit{A fortiori}, $J$ n'est pas décidable. +\end{corrige} + + +% +% +% +\end{document} |