Possible exam for 2018-02-06.

1 files changed, 288 insertions, 0 deletions

diff --git a/controle-20180206.tex b/controle-20180206.tex
new file mode 100644
index 0000000..c18064b
--- /dev/null
+++ b/controle-20180206.tex
@@ -0,0 +1,288 @@
+%% 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}\smallbreak\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
+\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\relax\else\egroup\fi\par}
+\newenvironment{commentaire}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
+{{\hbox{}\nobreak\hfill\maltese}%
+\ifcorrige\relax\else\egroup\fi\par}
+%
+%
+% 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{6 février 2018}
+\maketitle
+
+%% {\footnotesize
+%% \immediate\write18{sh ./vc > vcline.tex}
+%% \begin{center}
+%% Git: \input{vcline.tex}
+%% \end{center}
+%% \immediate\write18{echo ' (stale)' >> vcline.tex}
+%% \par}
+
+\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
+
+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} : 8 points par exercices
+
+\ifcorrige
+%Ce corrigé comporte 10 pages (page de garde incluse)
+\else
+%Cet énoncé comporte 4 pages (page de garde incluse)
+\fi
+
+\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, ou bien deux $c$ consécutifs), ainsi qu'à son
+complémentaire $M := \Sigma^* \setminus L$.
+
+(1) Donner une expression rationnelle dénotant $L$.
+
+(2) 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 ?
+
+(3) Déterminiser (si nécessaire) l'automate $\mathscr{A}_2$ représenté
+en (2) ; on appellera $\mathscr{A}_3$ l'automate résultant.
+
+(4) Minimiser (si nécessaire) l'automate $\mathscr{A}_3$ obtenu
+en (3) ; on appellera $\mathscr{A}_4$ l'automate résultant.
+
+(5) Construire un automate $\mathscr{A}_5$ reconnaissant le
+langage $M$ complémentaire de $L$.
+
+(6) En appliquant à $\mathscr{A}_5$ la méthode d'élimination des
+états, déterminer une expression rationnelle dénotant le langage $M$.
+
+
+
+%
+%
+%
+
+\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 choses
+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 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$.
+
+(2) En considérant que $(w)$ a le même effet / la même valeur
+que $w$ : (a) Quelle opération parmi $\#$ et $@$ est
+prioritaire\footnote{On dit qu'une opération binaire $\boxtimes$ est
+  \emph{prioritaire} sur $\boxplus$ lorsque « $u\boxtimes v\boxplus
+  w$ » se comprend comme « $(u\boxtimes v)\boxplus w$ » et
+  « $u\boxplus v\boxtimes w$ » comme « $u\boxplus (v\boxtimes w)$ ».}
+sur l'autre ?  (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 ?  (c) L'opération $@$ s'associe-t-elle à gauche ou à droite ?
+
+
+%
+%
+%
+
+\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.)
+
+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 $L\cap M = \varnothing$) sont
+\emph{calculablement séparables} lorsqu'il existe un $E$ 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 les dit \emph{calculablement inséparables}.
+
+(1) Expliquer pourquoi deux langages $L,M$ disjoints sont
+calculablement séparables si et seulement si 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$).
+\end{itemize}
+
+(2) Expliquer pourquoi deux langages $L,M$ disjoints sont
+calculablement séparables si et seulement si il existe deux langages
+$E,F$ \emph{décidables disjoints} tels que $L \subseteq E$ et $M
+\subseteq F$.
+
+(3) Deux langages décidables disjoints peuvent-ils être calculablement
+inséparables ?
+
+On cherche maintenant à montrer qu'il existe deux langages $L,M$
+\emph{semi-décidables} disjoints et calculablement inséparables.
+
+Pour cela, appelle $L$ l'ensemble 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}$.  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
+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$.)
+
+(4) Pourquoi $L$ et $M$ sont-ils disjoints ?
+
+(5) Pourquoi $L$ et $M$ sont-ils semi-décidables ?
+
+(6) En calquant 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).
+
+(7) Conclure.
+
+
+
+%
+%
+%
+\end{document}