1 files changed, 193 insertions, 0 deletions
diff --git a/controle-20190328.tex b/controle-20190328.tex
new file mode 100644
index 0000000..e3e1391
--- /dev/null
+++ b/controle-20190328.tex
@@ -0,0 +1,193 @@
+%% 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{28 mars 2019}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+\textcolor{red}{À remplir}
+
+\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}{xxx}.
+
+\ifcorrige
+Ce corrigé comporte \textcolor{red}{xxx} pages (page de garde incluse)
+\else
+Cet énoncé comporte \textcolor{red}{xxx} 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\}$.
+
+(1) Soit $L_1$ le langage formé des mots de $\Sigma^*$ ayant $a$ comme
+première lettre (c'est-à-dire, comme préfixe).\quad(a) Donner une
+expression rationnelle $r_1$ dénotant le langage $L_1$.\quad(b) Donner
+l'automate fini déterministe complet minimal $\mathscr{A}_1$
+reconnaissant $L_1$ (on pourra préalablement passer par d'autres
+sortes d'automates comme étapes intermédiaires ; pour obtenir la
+totalité des points, on passera impérativement par des constructions
+vues en cours, qu'on précisera).
+
+\emph{Information :} L'automate $\mathscr{A}_1$ correct a trois états.
+Il est fortement conseillé de vérifier soigneusement qu'on a bien
+obtenu un automate déterministe complet ayant le bon nombre états et
+qu'il se comporte comme attendu sur quelques mots courts (par exemple
+$\varepsilon$, $a$, $b$, $aa$, $ab$, $ba$ et $bb$).
+
+\medskip
+
+(2) Soit $L_2$ le langage formé des mots de $\Sigma^*$ ayant $a$ comme
+dernière lettre (c'est-à-dire, comme suffixe).\quad(a) Donner une
+expression rationnelle $r_2$ dénotant le langage $L_2$.\quad(b) Donner
+l'automate fini déterministe complet minimal $\mathscr{A}_2$
+reconnaissant $L_2$ (mêmes remarques que ci-dessus).
+
+\emph{Information :} L'automate $\mathscr{A}_2$ correct a deux états.
+Même conseil que ci-dessus.
+
+\medskip
+
+(3) Soit $L_3 = L_2^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L_2\}$ le
+langage miroir de $L_2$, c'est-à-dire le langage formé des mots
+miroirs des mots de $L_2$ (on rappelle que le mot « moir »
+$w^{\mathsf{R}}$ d'un mot $w$ s'obtient en inversant l'ordre de ses
+lettres).\quad(a) Déduire de $\mathscr{A}_2$ un automate fini
+$\mathscr{A}_3$ reconnaissant $L_3$.\quad(b) Quel est le rapport entre
+les langages $L_1$ et $L_3$ ?\quad(c) Faire un commentaire quant au
+rapport entre $\mathscr{A}_1$ et $\mathscr{A}_3$ ; notamment, on
+expliquera en quoi l'existence de $\mathscr{A}_3$ ne contredit pas la
+minimalité de $\mathscr{A}_1$.
+
+\medskip
+
+(4) Soit $L_4 = L_1\cap L_2$.\quad(a) Déduire des automates
+$\mathscr{A}_1$ et $\mathscr{A}_2$ un automate fini
+$\mathscr{A}_{4\mathrm{a}}$ ayant six états
+reconnaissant $L_4$.\quad(b) Donner l'automate fini déterministe
+complet minimal $\mathscr{A}_{4\mathrm{b}}$ reconnaissant $L_4$.
+
+\emph{Information :} L'automate $\mathscr{A}_4$ correct a quatre
+états.  Même conseil que pour la question (1).
+
+\medskip
+
+(5) En appliquant l'algorithme d'élimination des états, déduire
+de $\mathscr{A}_{4\mathrm{b}}$ une expression rationnelle $r_5$
+dénotant le langage $L_4$.
+
+\medskip
+
+(6) Sans raisonner sur les automates, proposer une expression
+rationnelle $r_6$ différente de celle trouvée en $r_5$ et qui dénote
+aussi le langage $L_4$ (dont on donnera au préalable une description
+en français).
+
+%
+%
+%
+\end{document}