diff options
| -rw-r--r-- | controle-20220616.tex | 456 |
1 files changed, 456 insertions, 0 deletions
diff --git a/controle-20220616.tex b/controle-20220616.tex new file mode 100644 index 0000000..cf36e07 --- /dev/null +++ b/controle-20220616.tex @@ -0,0 +1,456 @@ +%% 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{16 juin 2022} +\maketitle + +\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} pages (page de garde incluse). +\else +Cet énoncé comporte \textcolor{red}{à remplir} pages (page de garde incluse). +\fi + +\vfill + +{\tiny\noindent +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On considère +l'expression rationnelle $r := a{*}b{*}a{*}$, et soit $L := L(r)$ le +langage qu'elle dénote. + +(0) Pour chacun des mots suivants, dire si oui ou non il appartient +à $L$ (c'est-à-dire s'il vérifie $r$) : $\varepsilon$ (le mot vide), +$a$, $b$, $ab$, $ba$, $aa$, $aba$, $bab$, $abab$. On ne demande pas +de justifier les réponses. + +\begin{corrige} +Les mots $\varepsilon$, $a$, $b$, $ab$, $ba$, $aa$, $aba$ +appartiennent à $L$ ; les mots $bab$ et $baba$ n'appartiennent pas +à $L$. +\end{corrige} + +\emph{Il est fortement conseillé, dans toutes les questions suivantes, + d'utiliser les mots qui viennent d'être listés pour vérifier les + automates successifs qu'on calculera.} (Par exemple, pour un +automate censé reconnaître le langage $L$, on vérifiera qu'il accepte +bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux +qu'on a identifiés comme n'appartement pas à $L$.) Les fautes qui +auraient dû être détectées par cette vérification pourront être 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 (= $\varepsilon$-transitions) de ce dernier (on +retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$ +l'automate ainsi obtenu. + +(Dans les deux cas, on obtient le même automate fini $\mathscr{A}_1$, +et il a $4$ états. À défaut de donner l'automate de Glushkov ou de +Thompson, donner un NFA reconnaissant $L$ pourra apporter une partie +des points.) + +\begin{corrige} +L'automate $\mathscr{A}_1$ trouvé est le suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,final,accepting below] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,final] {$3$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q0) to[out=295,in=245] node[auto,below]{$b$} (q2); +\draw[->] (q1) to[out=295,in=245] node[auto,below]{$a$} (q3); +\draw[->] (q0) to[out=270,in=270] node[auto,below]{$a$} (q3); +\end{tikzpicture} +\end{center} +(on remarquera notamment que tous ses états sont finaux). +\end{corrige} + +(2) Déterminiser l'automate $\mathscr{A}_1$. On appellera +$\mathscr{A}_2$ l'automate en question. On rappelle qu'on attend ici +un automate fini \emph{déterministe complet} ; pour information, il a +$5$ états. + +\begin{corrige} +L'automate $\mathscr{A}_2$ trouvé est le suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$\scriptstyle\{0\}$}; +\node (q1) at (30bp,52bp) [draw,circle,state,final,accepting right] {$\scriptstyle\{1,3\}$}; +\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{2\}$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{3\}$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (q0) -- node[auto]{$b$} (q2); +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto,near end]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (qF); +\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF); +\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 minimal ainsi obtenu (automate canonique du +langage $L$). Pour information, cet automate a $4$ états : pour la +commodité du correcteur, on les appellera $1,2,3,\bot$ dans l'ordre +dans lequel ils sont parcourus lorsque l'automate consomme le +mot $bab$. + +\begin{corrige} +L'automate $\mathscr{A}_2$ est déterministe complet sans état +inaccessible. On commence l'algorithme de minimisation en séparant +les états finaux $\{0\},\{1,3\},\{2\},\{3\}$ et l'état +non-final $\varnothing$. On sépare ensuite les premiers selon que la +transition étiquetée $b$ conduit à un état non-final, ce qui +sépare $\{3\}$ du reste, et enfin selon que la transition +étiquetée $a$ conduit à cet état $\{3\}$, ce qui sépare $\{2\}$ du +reste. Finalement, on aboutit aux classes suivantes : $\{0\} \equiv +\{1,3\}$, $\{2\}$, $\{3\}$ et $\varnothing$ (qu'on rebaptise +$1,2,3,\bot$ respectivement), et à l'automate minimal $\mathscr{A}_3$ +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$}; +\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$}; +\draw[->] (q1) to[loop above] node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (qF); +\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(4) Donner de même l'automate minimal $\mathscr{A}_4$ du langage $L' +:= L(r')$ dénoté par l'expression rationnelle $r' := b{*}a{*}b{*}$. +Comme ce langage, et donc cet automate, est simplement obtenu en +échangeant $a$ et $b$ par rapport à ce qui précède, on donnera +directement l'automate sans passer par les questions intermédiaires. + +\begin{corrige} +L'automate minimal $\mathscr{A}_4$ de $L'$ s'obtient simplement en +échangeant $a$ et $b$ dans $\mathscr{A}_3$ : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$}; +\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$}; +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$a$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$a$} (q2); +\draw[->] (q2) -- node[auto]{$b$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$b$} (q3); +\draw[->] (q3) -- node[auto]{$a$} (qF); +\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(5) En utilisant une construction de type « automate produit », donner +un automate déterministe complet $\mathscr{A}_5$, ayant $4\times 4 = +16$ états, qui reconnaît le langage $M := L \cap L'$ (constitué des +mots vérifiant à la fois $r$ et $r'$). On prendra garde pour la +question suivante au fait que cet automate possède des états +inaccessibles. + +\begin{corrige} +En prenant le produit des automates +$\mathscr{A}_3$ et $\mathscr{A}_4$, on aboutit à l'automate suivant +(où on a noté $q,q'$ l'état correspondant au couple $(q,q')$ d'un état +$q$ de $\mathscr{A}_3$ et $q'$ de $\mathscr{A}_4$ ; par exemple, +$\delta((1,1),a) = (1,2)$ car $\delta_{\mathscr{A}_3}(1,a) = 1$ et +$\delta_{\mathscr{A}_4}(1,a) = 2$) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q11) at (0bp,0bp) [draw,circle,state,initial,accepting by double] {\footnotesize$1,1$}; +\node (q12) at (60bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,2$}; +\node (q13) at (120bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,3$}; +\node (q1F) at (180bp,0bp) [draw,circle,state] {\footnotesize$1,\bot$}; +\node (q21) at (0bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,1$}; +\node (q22) at (60bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,2$}; +\node (q23) at (120bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,3$}; +\node (q2F) at (180bp,-60bp) [draw,circle,state] {\footnotesize$2,\bot$}; +\node (q31) at (0bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,1$}; +\node (q32) at (60bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,2$}; +\node (q33) at (120bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,3$}; +\node (q3F) at (180bp,-120bp) [draw,circle,state] {\footnotesize$3,\bot$}; +\node (qF1) at (0bp,-180bp) [draw,circle,state] {\footnotesize$\bot,1$}; +\node (qF2) at (60bp,-180bp) [draw,circle,state] {\footnotesize$\bot,2$}; +\node (qF3) at (120bp,-180bp) [draw,circle,state] {\footnotesize$\bot,3$}; +\node (qFF) at (180bp,-180bp) [draw,circle,state] {\footnotesize$\bot,\bot$}; +\draw[->] (q11) -- node[auto]{$b$} (q21); +\draw[->] (q11) -- node[auto]{$a$} (q12); +\draw[->] (q12) -- node[auto]{$b$} (q23); +\draw[->] (q12) to[loop above] node[auto]{$a$} (q12); +\draw[->] (q13) -- node[auto]{$b$} (q23); +\draw[->] (q13) -- node[auto]{$a$} (q1F); +\draw[->] (q1F) -- node[auto]{$b$} (q2F); +\draw[->] (q1F) to[loop right] node[auto]{$a$} (q1F); +\draw[->] (q21) to[loop left] node[auto]{$b$} (q21); +\draw[->] (q21) -- node[auto]{$a$} (q32); +\draw[->] (q22) -- node[auto]{$b$} (q23); +\draw[->] (q22) -- node[auto]{$a$} (q32); +\draw[->] (q23) to[loop right] node[auto]{$b$} (q23); +\draw[->] (q23) -- node[auto]{$a$} (q3F); +\draw[->] (q2F) to[loop right] node[auto]{$b$} (q2F); +\draw[->] (q2F) -- node[auto]{$a$} (q3F); +\draw[->] (q31) -- node[auto]{$b$} (qF1); +\draw[->] (q31) -- node[auto]{$a$} (q32); +\draw[->] (q32) -- node[auto]{$b$} (qF3); +\draw[->] (q32) to[loop below] node[auto]{$a$} (q32); +\draw[->] (q33) -- node[auto]{$b$} (qF3); +\draw[->] (q33) -- node[auto]{$a$} (q3F); +\draw[->] (q3F) -- node[auto]{$b$} (qFF); +\draw[->] (q3F) to[loop right] node[auto]{$a$} (q3F); +\draw[->] (qF1) to[loop below] node[auto]{$b$} (qF1); +\draw[->] (qF1) -- node[auto]{$a$} (qF2); +\draw[->] (qF2) -- node[auto]{$b$} (qF3); +\draw[->] (qF2) to[loop below] node[auto]{$a$} (qF2); +\draw[->] (qF3) to[loop below] node[auto]{$b$} (qF3); +\draw[->] (qF3) -- node[auto]{$a$} (qFF); +\draw[->] (qFF) to[loop below] node[auto]{$a,b$} (qFF); +\end{tikzpicture} +\end{center} +Pour plus de lisibilité, on a ici noté les états finaux en les +entourant deux fois plutôt qu'avec une flèche sortante. +\end{corrige} + +(6) Minimiser l'automate $\mathscr{A}_5$. On appellera +$\mathscr{A}_6$ l'automate minimal ainsi obtenu (automate canonique du +langage $M = L \cap L'$). Pour information, cet automate a $6$ états. + +\begin{corrige} +On commence par ne conserver que les états accessibles depuis l'état +initial, c'est-à-dire ceux étiquetés $(1,1)$, $(1,2)$, $(2,1)$, +$(2,3)$, $(3,2)$, $(3,\bot)$, $(\bot,3)$ et $(\bot,\bot)$ dans la +représentation ci-dessus, pour avoir un automate déterministe complet +sans état inaccessible. On applique ensuite l'algorithme de +minimisation de manière semblable à la question (3) : les états +non-finaux vont toujours rester groupés, et les états finaux sont +séparés un par un. Finalement, on aboutit à l'automate +$\mathscr{A}_6$ suivant comme automate minimal du langage $M$ (on a +rebaptisé les états ainsi : $(1,1)\rightsquigarrow 1$, +$(2,1)\rightsquigarrow 2$, $(3,2)\rightsquigarrow 3$, +$(1,2)\rightsquigarrow 2'$, $(2,3)\rightsquigarrow 3'$, et +$(3,\bot)\equiv (\bot,3) \equiv (\bot,\bot) \rightsquigarrow \bot$) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$}; +\node (q2a) at (60bp,42bp) [draw,circle,state,final,accepting below] {$2'$}; +\node (q3a) at (120bp,42bp) [draw,circle,state,final,accepting below] {$3'$}; +\node (q2) at (60bp,-42bp) [draw,circle,state,final,accepting below] {$2$}; +\node (q3) at (120bp,-42bp) [draw,circle,state,final,accepting below] {$3$}; +\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$}; +\draw[->] (q1) -- node[auto]{$a$} (q2a); +\draw[->] (q1) -- node[auto,below]{$b$} (q2); +\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a); +\draw[->] (q2a) -- node[auto]{$b$} (q3a); +\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a); +\draw[->] (q3a) -- node[auto]{$a$} (qF); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto,below]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto,below]{$b$} (qF); +\draw[->] (qF) to[loop right] node[auto]{$a,b$} (qF); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(7) En appliquant l'algorithme d'élimination des états, déduire +de $\mathscr{A}_6$ une expression rationnelle $s$ dénotant le +langage $M$. Pour obtenir une expression raisonnablement simple, on +recommande d'éliminer les états en commençant par ceux qui sont à la +distance la plus éloignée de l'état initial. + +\begin{corrige} +On commence par effacer l'état puits (qui ne sert à rien) et par créer +un unique état final sans transition qui en parte : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$}; +\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$}; +\node (q3a) at (120bp,42bp) [draw,circle,state] {$3'$}; +\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$}; +\node (q3) at (120bp,-42bp) [draw,circle,state] {$3$}; +\node (qT) at (180bp,0bp) [draw,circle,state,final] {$\infty$}; +\draw[->] (q1) -- node[auto]{$a$} (q2a); +\draw[->] (q1) -- node[auto,below]{$b$} (q2); +\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a); +\draw[->] (q2a) -- node[auto]{$b$} (q3a); +\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a); +\draw[->] (q2a) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q3a) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q2) to[loop below] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto,below]{$a$} (q3); +\draw[->] (q3) to[loop below] node[auto]{$a$} (q3); +\draw[->] (q2) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q3) -- node[auto,below]{$\varepsilon$} (qT); +\end{tikzpicture} +\end{center} + +On peut alors éliminer les états $3$ et $3'$ (il n'y a pas +d'interaction entre eux) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$}; +\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$}; +\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$}; +\node (qT) at (120bp,0bp) [draw,circle,state,final] {$\infty$}; +\draw[->] (q1) -- node[auto]{$a$} (q2a); +\draw[->] (q1) -- node[auto,below]{$b$} (q2); +\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT); +\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a); +\draw[->] (q2a) -- node[auto]{$\varepsilon|bb{*}$} (qT); +\draw[->] (q2) to[loop below] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto,below,near end]{$\varepsilon|aa{*}$} (qT); +\end{tikzpicture} +\end{center} + +Et finalement, en éliminant les états $2$ et $2'$, on trouve +l'expression rationnelle suivante qui dénote le langage $M$ : +\[ +\varepsilon\,|\,aa{*}(\varepsilon|bb{*})\,|\,bb{*}(\varepsilon|aa{*}) +\] +(il y a bien sûr d'autres écritures possibles ; par exemple, si on +élimine d'abord $2$ et $2'$ puis $3$ et $3'$ on obtient : +$\varepsilon\,|\,aa{*}\,|\,bb{*}\,|\,aa{*}bb{*}\,|\,bb{*}aa{*}$ ; +l'expression rationnelle $\varepsilon\,|\,aa{*}b{*}\,|\,bb{*}a{*}$ est +encore équivalente, mais elle ne s'obtient pas par la procédure +d'élimination des états). +\end{corrige} + + +% +% +% +\end{document} |