diff options
Diffstat (limited to 'controle-20190205.tex')
| -rw-r--r-- | controle-20190205.tex | 372 |
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} |