%% 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 \textcolor{red}{nnn} 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és 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 de lui ajouter un puits pour obtenir l'automate $\mathscr{A}_2$ : \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. 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\}$, 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 : \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.) 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$). (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. (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$). (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. (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. % % % \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. \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. % % % \end{document}