path: root/controle-20170330.tex

%% 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 rattrapage — Corrigé\\{\normalsize Théorie des langages}}
\else
\title{INF105\\Contrôle de rattrapage\\{\normalsize Théorie des langages}}
\fi
\author{}
\date{30 mars 2017}
\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

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

\ifcorrige
%Ce corrigé comporte 10 pages (page de garde incluse)
\else
%Cet énoncé comporte 4 pages (page de garde incluse)
\fi

\pagebreak


%
%
%

\exercice

Soit $\Sigma = \{a,b\}$.

(1) Représenter l'automate de Thompson $A_1$ associé à l'expression
rationnelle $r$ suivante : $a{*}(ba{*}){*}$ (pour éviter toute erreur
de lecture, on rappelle que dans l'écriture des expressions
rationnelles, l'étoile de Kleene $*$ a une priorité plus grande que la
concaténation).

On demande l'automate \emph{exact} donné par la construction de
Thompson pour $r$ : aucune variation ne sera autorisée, même si elle
conduit à un automate équivalent.

Par ailleurs, pour simplifier le travail du correcteur, on demande
d'étiqueter les états de $A_1$ par les entiers naturels à partir
de $0$ (soit $0,1,2,3,\ldots$) dans l'ordre correspondant à la lecture
de l'expression rationnelle de la gauche vers la droite.

(2) Éliminer les transitions spontanées de l'automate $A_1$ obtenu
en (1), si nécessaire.  (On supprimera les états devenus inutiles.)
On appellera $A_2$ l'automate obtenu.

(3) Déterminiser l'automate $A_2$ obtenu en (2), si nécessaire.  (On
demande un automate déterministe complet.)  On appellera $A_3$
l'automate déterminisé.

(4) Minimiser l'automate $A_3$ obtenu en (3), si nécessaire
(justifier).

(5) Donner une autre expression rationnelle équivalente à $r$.

\begin{corrige}
(1) L'automate de Thompson de $r := a{*}(ba{*}){*}$ doit comporter
  $12$ états (numérotés de $0$ à $11$ selon la consigne) puisque cette
  expression rationnelle contient $6$ symboles parenthèses non
  comptées.  Il est l'automate $A_1$ suivant (où on a omis les
  $\varepsilon$ sur les transitions spontanées) :
\begin{center}
\scalebox{0.4}{%
%%% begin cn2p1 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (98bp,45bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
  \node (q3) at (258bp,18bp) [draw,circle,state] {$3$};
  \node (q2) at (178bp,45bp) [draw,circle,state] {$2$};
  \node (q5) at (418bp,48bp) [draw,circle,state] {$5$};
  \node (q4) at (338bp,18bp) [draw,circle,state] {$4$};
  \node (q7) at (578bp,86bp) [draw,circle,state] {$7$};
  \node (q6) at (498bp,86bp) [draw,circle,state] {$6$};
  \node (q9) at (738bp,124bp) [draw,circle,state] {$9$};
  \node (q8) at (658bp,124bp) [draw,circle,state] {$8$};
  \node (q11) at (904bp,25bp) [draw,circle,state,final] {$11$};
  \node (q10) at (820bp,63bp) [draw,circle,state] {$10$};
  \draw [->] (q0) ..controls (76.842bp,18bp) and (179.8bp,18bp)  .. node[auto] {{}} (q3);
  \draw [->] (q2) ..controls (205.62bp,35.785bp) and (219.46bp,30.994bp)  .. node[auto] {{}} (q3);
  \draw [->] (q10) ..controls (849.21bp,49.929bp) and (864.12bp,43.018bp)  .. node[auto] {{}} (q11);
  \draw [->] (q7) ..controls (605.31bp,98.816bp) and (620.14bp,106.04bp)  .. node[auto] {{}} (q8);
  \draw [->] (q8) ..controls (686.11bp,124bp) and (698.58bp,124bp)  .. node[auto] {$a$} (q9);
  \draw [->] (q2) ..controls (154.59bp,39.764bp) and (148.04bp,38.598bp)  .. (142bp,38bp) .. controls (136.68bp,37.473bp) and (131.02bp,37.771bp)  .. node[auto] {{}} (q1);
  \draw [->] (q6) ..controls (526.11bp,86bp) and (538.58bp,86bp)  .. node[auto] {{}} (q7);
  \draw [->] (q9) ..controls (761.45bp,107.48bp) and (772.39bp,99.343bp)  .. (782bp,92bp) .. controls (786.62bp,88.47bp) and (791.54bp,84.659bp)  .. node[auto] {{}} (q10);
  \draw [->] (q3) ..controls (286.11bp,18bp) and (298.58bp,18bp)  .. node[auto] {{}} (q4);
  \draw [->] (q7) ..controls (637.01bp,80.44bp) and (739.57bp,70.612bp)  .. node[auto] {{}} (q10);
  \draw [->] (q4) ..controls (370.88bp,8.0178bp) and (395.3bp,2bp)  .. (417bp,2bp) .. controls (417bp,2bp) and (417bp,2bp)  .. (821bp,2bp) .. controls (840.04bp,2bp) and (860.68bp,7.8211bp)  .. node[auto] {{}} (q11);
  \draw [->] (q5) ..controls (445.31bp,60.816bp) and (460.14bp,68.042bp)  .. node[auto] {$b$} (q6);
  \draw [->] (q10) ..controls (786bp,48.432bp) and (761.4bp,40bp)  .. (739bp,40bp) .. controls (497bp,40bp) and (497bp,40bp)  .. (497bp,40bp) .. controls (480.02bp,40bp) and (461.07bp,41.899bp)  .. node[auto] {{}} (q5);
  \draw [->] (q0) ..controls (45.62bp,27.215bp) and (59.462bp,32.006bp)  .. node[auto] {{}} (q1);
  \draw [->] (q1) ..controls (122.47bp,55.902bp) and (132.67bp,58.554bp)  .. (142bp,57bp) .. controls (145.13bp,56.478bp) and (148.36bp,55.711bp)  .. node[auto] {$a$} (q2);
  \draw [->] (q4) ..controls (365.62bp,28.238bp) and (379.46bp,33.562bp)  .. node[auto] {{}} (q5);
%
\end{tikzpicture}

%%% end cn2p1 %%%
}
\end{center}

\smallbreak

(2) Tous les états autres que $0$ (car il est initial) et $2,6,9$ (car
des transitions non spontanées y aboutissent) vont disparaître ; les
ε-fermetures (arrière) $C(q)$ de ces états sont les suivantes :

\begin{center}
\begin{tabular}{r|l}
$q$&ε-fermeture $C(q)$\\
\hline
$0$&$\{0,1,3,4,5,11\}$\\
$2$&$\{1,2,3,4,5,11\}$\\
$6$&$\{5,6,7,8,10,11\}$\\
$9$&$\{5,8,9,10,11\}$\\
\end{tabular}
\end{center}

En remplaçant chaque transition $q^\sharp \to q'$ étiquetée
d'un $x\in\Sigma$ dans l'automate par une transition $q\to q'$ pour
chaque état $q$ tel que $q^\sharp \in C(q)$, on obtient l'automate
$A_2$ suivant :
\begin{center}
%%% begin cn2p1b %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q9) at (258bp,20.306bp) [draw,circle,state,final] {$9$};
  \node (q0) at (18bp,20.306bp) [draw,circle,state,initial,final,accepting below] {$0$};
  \node (q2) at (98bp,50.306bp) [draw,circle,state,final,accepting below] {$2$};
  \node (q6) at (178bp,20.306bp) [draw,circle,state,final,accepting below] {$6$};
  \draw [->] (q0) ..controls (45.62bp,30.544bp) and (59.462bp,35.868bp)  .. node[auto] {$a$} (q2);
  \draw [->] (q2) to[loop above] node[auto] {$a$} (q2);
  \draw [->] (q6) to[loop above] node[auto] {$b$} (q6);
  \draw [->] (q9) to[loop above] node[auto] {$a$} (q9);
  \draw [->] (q9) ..controls (235.21bp,3.6347bp) and (224.28bp,-1.3057bp)  .. (214bp,1.3057bp) .. controls (210.04bp,2.3107bp) and (206.05bp,3.8633bp)  .. node[auto] {$b$} (q6);
  \draw [->] (q0) ..controls (47.887bp,13.272bp) and (64.853bp,9.7814bp)  .. (80bp,8.3057bp) .. controls (95.925bp,6.7542bp) and (100.08bp,6.7542bp)  .. (116bp,8.3057bp) .. controls (127.36bp,9.4124bp) and (139.74bp,11.652bp)  .. node[auto] {$b$} (q6);
  \draw [->] (q2) ..controls (125.62bp,40.067bp) and (139.46bp,34.744bp)  .. node[auto] {$b$} (q6);
  \draw [->] (q6) ..controls (206.11bp,20.306bp) and (218.58bp,20.306bp)  .. node[auto] {$a$} (q9);
%
\end{tikzpicture}

%%% end cn2p1b %%%
\end{center}

\smallbreak

(3) L'automate $A_2$ est déjà déterministe (il ne comporte plus de
transitions spontanées par construction, et il s'avère que chaque état
a exactement une transition sortante pour chacun des symboles $a$
et $b$).  On a donc $A_3 = A_2$.

\smallbreak

(4) Tous les états de $A_3$ sont finaux : l'algorithme de minimisation
termine donc immédiatement en produisant un automate $A_4$ à un seul
état ($0\equiv 2 \equiv 6 \equiv 9$), à la fois initial et final, avec
des transitions étiquetées $a$ et $b$ conduisant de cet état à
lui-même :
\begin{center}
%%% begin cn2p1c %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q0) at (22bp,22bp) [draw,circle,state,initial,final] {$\top$};
  \draw [->] (q0) to[loop above] node[auto] {$a,b$} (q0);
%
\end{tikzpicture}

%%% end cn2p1c %%%
\end{center}

\smallbreak

(5) L'automate $A_4$ reconnaît manifestement le langage $\Sigma^*$ de
tous les mots sur $\Sigma$.  On peut donc proposer l'expression
rationnelle $(a|b){*}$ (nous notons ici $|$ pour la disjonction, qu'on
peut aussi noter $+$).
\end{corrige}



%
%
%
\end{document}