Start writing exam: exercise on finite automata.

1 files changed, 372 insertions, 0 deletions

diff --git a/controle-20190205.tex b/controle-20190205.tex
new file mode 100644
index 0000000..8accd7f
--- /dev/null
+++ b/controle-20190205.tex
@@ -0,0 +1,372 @@
+%% 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{5 février 2019}
+\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} : \textcolor{red}{à remplir}.
+
+\ifcorrige
+Ce corrigé comporte \textcolor{red}{à remplir} (page de garde incluse)
+\else
+Cet énoncé comporte \textcolor{red}{à remplir} (page de garde incluse)
+\fi
+
+\pagebreak
+
+
+%
+%
+%
+
+\exercice
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.
+
+On considère l'expression rationnelle $r$ suivante : $(ab|ba){*}$ (sur
+l'alphabet $\Sigma$).  On appelle $L := L(r)$ le langage qu'elle
+dénote.
+
+(0) Donner quatre exemples de mots de $L$ et quatre exemples de mots
+n'appartenant pas à $L$.
+
+\begin{corrige}
+Par exemple, les mots $\varepsilon$, $ab$, $ba$ et $abba$
+appartiennent à $L$.  Les mots $a$, $b$, $aa$ et $aba$ n'appartiennent
+pas à $L$.
+\end{corrige}
+
+(Il est vivement recommander d'utiliser, dans toute la suite de cet
+exercice, les huit mots en question pour tester les réponses qu'on
+proposera.  Les erreurs qui auraient dû être détectées de cette
+manière 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 de ce dernier : on appellera $\mathscr{A}_1$
+l'automate ainsi obtenu.
+
+(Dans les deux cas, on obtient le même automate $\mathscr{A}_1$, ayant
+$5$ états.  La suite de l'exercice dépendant de cette question, on
+conseille vérifier très soigneusement que $\mathscr{A}_1$ est correct.
+À défaut de donner l'automate de Glushkov ou de Thompson, donner un
+NFA reconnaissant $L$ apportera une partie des points.)
+
+\begin{corrige}
+L'automate $\mathscr{A}_1$ obtenu est le suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (S3) at (150bp,35bp) [draw,circle,state,final] {$3$};
+\node (S4) at (150bp,-35bp) [draw,circle,state,final] {$4$};
+\draw [->] (S0) -- node[auto,near end] {$a$} (S1);
+\draw [->] (S0) -- node[auto,below] {$b$} (S2);
+\draw [->] (S1) -- node[auto,below] {$b$} (S3);
+\draw [->] (S2) -- node[auto] {$a$} (S4);
+\draw [->] (S3) -- node[auto,above,very near end] {$b$} (S2);
+\draw [->] (S4) -- node[auto,very near end] {$a$} (S1);
+\draw [->] (S3) to[out=135,in=45] node[auto,above] {$a$} (S1);
+\draw [->] (S4) to[out=225,in=315] node[auto] {$b$} (S2);
+\end{tikzpicture}
+\end{center}
+C'est l'automate de Glushkov.  Si on commence par construire
+l'automate de Thompson, on obtient le suivant (à $12$ états) :
+\begin{center}
+\scalebox{0.70}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial] {};
+\node (S0u) at (60bp,0bp) [draw,circle,state] {};
+\node (S0a) at (120bp,40bp) [draw,circle,state] {};
+\node (S1) at (180bp,40bp) [draw,circle,state] {};
+\node (S1u) at (240bp,40bp) [draw,circle,state] {};
+\node (S3) at (300bp,40bp) [draw,circle,state] {};
+\node (S0b) at (120bp,-40bp) [draw,circle,state] {};
+\node (S2) at (180bp,-40bp) [draw,circle,state] {};
+\node (S2u) at (240bp,-40bp) [draw,circle,state] {};
+\node (S4) at (300bp,-40bp) [draw,circle,state] {};
+\node (SF) at (360bp,0bp) [draw,circle,state] {};
+\node (SFu) at (420bp,0bp) [draw,circle,state,final] {};
+\draw [->] (S0) -- (S0u);
+\draw [->] (S0u) -- (S0a);
+\draw [->] (S0a) -- node[auto] {$a$} (S1);  \draw [->] (S1) -- (S1u);
+\draw [->] (S1u) -- node[auto] {$b$} (S3);  \draw [->] (S3) -- (SF);
+\draw [->] (S0u) -- (S0b);
+\draw [->] (S0b) -- node[auto] {$b$} (S2);  \draw [->] (S2) -- (S2u);
+\draw [->] (S2u) -- node[auto] {$a$} (S4);  \draw [->] (S4) -- (SF);
+\draw [->] (SF) -- (SFu);
+\draw [->] (SF) to[out=90,in=0] (210bp,70bp) to[out=180,in=90] (S0u);
+\draw [->] (S0) to[out=270,in=180] (120bp,-70bp) -- (300bp,-70bp) to[out=0,in=270] (SFu);
+\end{tikzpicture}
+}
+\end{center}
+(où toutes les flèches non étiquetées sont des transitions spontanées,
+c'est-à-dire qu'il faut les imaginer étiquetées par $\varepsilon$) qui
+par élimination des transitions spontanées donne celui $\mathscr{A}_1$
+qu'on a tracé au-dessus (les seuls états qui subsistent après
+élimination des transitions spontanées sont l'état initial et les
+quatre états auxquels aboutissent une transition non spontanée).
+\end{corrige}
+
+(2) Déterminiser l'automate $\mathscr{A}_1$ obtenu en (1).  On demande
+un automate fini déterministe \emph{complet}.  On appellera
+$\mathscr{A}_2$ l'automate déterministe en question.
+
+\begin{corrige}
+L'automate $\mathscr{A}_1$ est déterministe incomplet : il s'agit donc
+simplement de lui ajouter un état « puits » pour le rendre complet, ce
+qui donne l'automate $\mathscr{A}_2$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (S3) at (150bp,35bp) [draw,circle,state,final] {$3$};
+\node (S4) at (150bp,-35bp) [draw,circle,state,final] {$4$};
+\node (Sink) at (220bp,0bp) [draw,circle,state] {$\bot$};
+\draw [->] (S0) -- node[auto,near end] {$a$} (S1);
+\draw [->] (S0) -- node[auto,below] {$b$} (S2);
+\draw [->] (S1) -- node[auto] {$b$} (S3);
+\draw [->] (S2) -- node[auto,below] {$a$} (S4);
+\draw [->] (S3) -- node[auto,above,very near end] {$b$} (S2);
+\draw [->] (S4) -- node[auto,very near end] {$a$} (S1);
+\draw [->] (S3) to[out=135,in=45] node[auto,above] {$a$} (S1);
+\draw [->] (S4) to[out=225,in=315] node[auto] {$b$} (S2);
+\draw [->] (S1) -- node[auto,very near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,very near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop right] node[auto] {$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
+$\mathscr{A}_3$ l'automate canonique ainsi obtenu.
+
+(On obtient un automate ayant $4$ états.)
+
+\begin{corrige}
+L'algorithme de minimisation identifie les trois états finaux
+($0,3,4$) de l'automate $\mathscr{A}_2$, ce qui donne
+l'automate $\mathscr{A}_3$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (Sink) at (140bp,0bp) [draw,circle,state] {$\bot$};
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) -- node[auto,near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop right] node[auto] {$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M
+:= \Sigma^*\setminus L$ complémentaire de $L$.
+
+\begin{corrige}
+L'automate $\mathscr{A}_3$ étant un automate fini déterministe complet
+reconnaissant $L$, il suffit de marquer finaux les états non-finaux et
+vice versa pour obtenir l'automate $\mathscr{A}_4$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state,final,accepting above] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state,final,accepting below] {$2$};
+\node (Sink) at (140bp,0bp) [draw,circle,state,final,accepting below] {$\bot$};
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) -- node[auto,near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop right] node[auto] {$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(5) En appliquant à $\mathscr{A}_4$ la méthode d'élimination des
+états, déterminer une expression rationnelle dénotant le langage $M$.
+
+\begin{corrige}
+Pour appliquer la méthode d'élimination des états, on commence par
+modifier l'automate pour avoir un unique état initial $I$, qui ne soit
+pas final, et qui n'ait aucune transition qui y aboutisse, et un
+unique état final $F$, qui ne soit pas initial, et sans aucune
+transition qui en part :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (SI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (S0) at (0bp,0bp) [draw,circle,state] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (Sink) at (140bp,0bp) [draw,circle,state] {$\bot$};
+\node (SF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (SI) -- node[auto] {$\varepsilon$} (S0);
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) -- node[auto,near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop above] node[auto] {$a|b$} (Sink);
+\draw [->] (S1) to[out=15,in=135] node[auto,near end] {$\varepsilon$} (SF);
+\draw [->] (S2) to[out=345,in=225] node[auto,near end] {$\varepsilon$} (SF);
+\draw [->] (Sink) -- node[auto] {$\varepsilon$} (SF);
+\end{tikzpicture}
+\end{center}
+On élimine ensuite l'état $\bot$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (SI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (S0) at (0bp,0bp) [draw,circle,state] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (SF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (SI) -- node[auto] {$\varepsilon$} (S0);
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) to[out=15,in=135] node[auto,near end] {$\varepsilon|a(a|b){*}$} (SF);
+\draw [->] (S2) to[out=345,in=225] node[auto,near end] {$\varepsilon|b(a|b){*}$} (SF);
+\end{tikzpicture}
+\end{center}
+Puis les états $1$ et $2$ peuvent être éliminés simultanément :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (SI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (S0) at (0bp,0bp) [draw,circle,state] {$0$};
+\node (SF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (SI) -- node[auto] {$\varepsilon$} (S0);
+\draw [->] (S0) -- node[auto] {$a(\varepsilon|a(a|b){*})|b(\varepsilon|b(a|b){*})$} (SF);
+\draw [->] (S0) to[loop above] node[auto] {$ab|ba$} (S0);
+\end{tikzpicture}
+\end{center}
+Et l'expression rationnelle finalement obtenue est la suivante :
+\[
+(ab|ba){*}(a(\varepsilon|a(a|b){*})|b(\varepsilon|b(a|b){*}))
+\]
+On pouvait aussi donner, entre autres choses :
+\[
+(ab|ba){*}(a|aa(a|b){*}|b|bb(a|b){*})
+\]
+(obtenue en éliminant les états $1$ et $2$ avant $\bot$).
+\end{corrige}
+
+%
+%
+%
+\end{document}