Write test for 2021.

1 files changed, 268 insertions, 0 deletions

diff --git a/controle-20210618.tex b/controle-20210618.tex
new file mode 100644
index 0000000..4993f1d
--- /dev/null
+++ b/controle-20210618.tex
@@ -0,0 +1,268 @@
+%% 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} : \textcolor{red}{à remplir}
+
+\ifcorrige
+Ce corrigé comporte \textcolor{red}{nnn} pages (page de garde incluse)
+\else
+Cet énoncé comporte \textcolor{red}{nnn} 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.
+
+\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 pouvant
+être détectées par cette vérification seront 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.)
+
+(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}.
+
+(3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
+$\mathscr{A}_3$ l'automate canonique du langage $L$ ainsi obtenu.
+
+(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$.
+
+(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$).
+
+
+%
+%
+%
+
+\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 \varepsilon \;|\; aSbc \;|\; abSc
+\]
+On appellera « $0$ » la règle $S \rightarrow \varepsilon$, 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) Montrer que 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 commençant
+par\footnote{C'est-à-dire : tout mot $w$ possédant une dérivation
+  selon $G$ de la forme $S \Rightarrow aSc \mathrel{\Rightarrow^*} w$
+  où $\mathrel{\Rightarrow^*}$ désigne une succession quelconque de
+  dérivations.  Ou, ce qui revient au même (on pourra tenir ce point
+  pour acquis) : tout mot $w$ possédant un arbre d'analyse dont la
+  racine a trois fils étiquetés $a,S,b$ dans cet ordre.} la règle $1$
+a nécessairement $aa$ ou $ac$ comme préfixe.  Montrer de même que tout
+mot de $L$ dérivé en commençant par la règle $2$ a nécessairement $ab$
+comme préfixe.
+
+(4) En déduire comment, d'après la longueur d'un mot $w$ de $L$ et ses
+deux premières lettres, on peut savoir par quelle règle commence
+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}