diff options
| -rw-r--r-- | controle-20170330.tex | 288 | ||||
| -rw-r--r-- | figs/cn2p1.dot | 33 | ||||
| -rw-r--r-- | figs/cn2p1b.dot | 17 | ||||
| -rw-r--r-- | figs/cn2p1c.dot | 7 |
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"]; +} |