summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-03-17 16:19:37 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-03-17 16:19:37 (GMT)
commit166e82b6033703f922d08911ff8e0da09ffd18fd (patch)
tree6d34b880427aa8e293089bcd192f2d38170a39c7
parentfd3971899dbc94325b09162e18e933568f4da719 (diff)
downloadinf105-166e82b6033703f922d08911ff8e0da09ffd18fd.zip
inf105-166e82b6033703f922d08911ff8e0da09ffd18fd.tar.gz
inf105-166e82b6033703f922d08911ff8e0da09ffd18fd.tar.bz2
Recovery exam: an exercise on finite automata.
-rw-r--r--controle-20170330.tex288
-rw-r--r--figs/cn2p1.dot33
-rw-r--r--figs/cn2p1b.dot17
-rw-r--r--figs/cn2p1c.dot7
4 files changed, 345 insertions, 0 deletions
diff --git a/controle-20170330.tex b/controle-20170330.tex
new file mode 100644
index 0000000..7532dee
--- /dev/null
+++ b/controle-20170330.tex
@@ -0,0 +1,288 @@
+%% 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}
diff --git a/figs/cn2p1.dot b/figs/cn2p1.dot
new file mode 100644
index 0000000..fd3c57e
--- /dev/null
+++ b/figs/cn2p1.dot
@@ -0,0 +1,33 @@
+digraph cn2p1 {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial",label="0"];
+ q1 [style="state",label="1"];
+ q2 [style="state",label="2"];
+ q3 [style="state",label="3"];
+ q4 [style="state",label="4"];
+ q5 [style="state",label="5"];
+ q6 [style="state",label="6"];
+ q7 [style="state",label="7"];
+ q8 [style="state",label="8"];
+ q9 [style="state",label="9"];
+ q10 [style="state",label="10"];
+ q11 [style="state,final",label="11"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q1 [label="e",texlbl="{}"];
+ q1 -> q2 [label="a"];
+ q2 -> q3 [label="e",texlbl="{}"];
+ q2 -> q1 [label="e",texlbl="{}"];
+ q0 -> q3 [label="e",texlbl="{}"];
+ q3 -> q4 [label="e",texlbl="{}"];
+ q4 -> q5 [label="e",texlbl="{}"];
+ q5 -> q6 [label="b"];
+ q6 -> q7 [label="e",texlbl="{}"];
+ q7 -> q8 [label="e",texlbl="{}"];
+ q8 -> q9 [label="a"];
+ q9 -> q10 [label="e",texlbl="{}"];
+ q10 -> q11 [label="e",texlbl="{}"];
+ q7 -> q10 [label="e",texlbl="{}"];
+ q10 -> q5 [label="e",texlbl="{}"];
+ q4 -> q11 [label="e",texlbl="{}"];
+}
diff --git a/figs/cn2p1b.dot b/figs/cn2p1b.dot
new file mode 100644
index 0000000..6600dfb
--- /dev/null
+++ b/figs/cn2p1b.dot
@@ -0,0 +1,17 @@
+digraph cn2p1b {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial,final,accepting below",label="0"];
+ q2 [style="state,final,accepting below",label="2"];
+ q6 [style="state,final,accepting below",label="6"];
+ q9 [style="state,final",label="9"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q2 [label="a"];
+ q2 -> q6 [label="b"];
+ q2 -> q2 [label="a",topath="loop above"];
+ q0 -> q6 [label="b"];
+ q6 -> q9 [label="a"];
+ q6 -> q6 [label="b",topath="loop above"];
+ q9 -> q6 [label="b"];
+ q9 -> q9 [label="a",topath="loop above"];
+}
diff --git a/figs/cn2p1c.dot b/figs/cn2p1c.dot
new file mode 100644
index 0000000..5e5a3e4
--- /dev/null
+++ b/figs/cn2p1c.dot
@@ -0,0 +1,7 @@
+digraph cn2p1c {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial,final",label="\top"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q0 [label="a,b",topath="loop above"];
+}