%% 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}