diff options
| -rw-r--r-- | controle-20230615.tex | 459 |
1 files changed, 422 insertions, 37 deletions
diff --git a/controle-20230615.tex b/controle-20230615.tex index 358cab2..cc97f35 100644 --- a/controle-20230615.tex +++ b/controle-20230615.tex @@ -282,55 +282,440 @@ $A_{\mathrm{z}}$\rule[-2ex]{0pt}{0pt}& \end{tabular} \end{center} -On définit aussi les dix langages suivants où $w_0$ désigne le +On définit aussi les douze langages suivants, où $w_0$ désigne le mot $ababb$ : \begin{itemize} -\item $L_0$: le langage vide. -\item $L_1$: le langage constitué du seul mot $w_0$. -\item $L_2$: le langage constitué des mots qui sont un sous-mot de +\item $L_0 = \varnothing$ : le langage vide. +\item $L_1 = \{w_0\}$ : le langage constitué du seul mot $w_0$. +\item $L_2$ : le langage constitué des mots qui sont un sous-mot de $w_0$. -\item $L_3$: le langage constitué des mots qui ont $w_0$ comme +\item $L_3$ : le langage constitué des mots qui ont $w_0$ comme sous-mot. -\item $L_4$: le langage constitué des mots qui sont un facteur de +\item $L_4$ : le langage constitué des mots qui sont un facteur de $w_0$. -\item $L_5$: le langage constitué des mots qui ont $w_0$ comme +\item $L_5$ : le langage constitué des mots qui ont $w_0$ comme facteur. -\item $L_6$: le langage constitué des mots qui sont un préfixe de +\item $L_6$ : le langage constitué des mots qui sont un préfixe de $w_0$. -\item $L_7$: le langage constitué des mots qui ont $w_0$ comme +\item $L_7$ : le langage constitué des mots qui ont $w_0$ comme préfixe. -\item $L_8$: le langage constitué des mots qui sont un suffixe de +\item $L_8$ : le langage constitué des mots qui sont un suffixe de $w_0$. -\item $L_9$: le langage constitué des mots qui ont $w_0$ comme +\item $L_9$ : le langage constitué des mots qui ont $w_0$ comme suffixe. +\item $L_{10} = \{w_0^i : i\in\mathbb{N}\}$ : le langage constitué des + mots qui sont une répétition d'un nombre quelconque ($i$) de copies + de $w_0$ (par exemple, $ababbababb$). +\item $L_{11} = \{b^i w_0 a^i : i\in\mathbb{N}\}$ : le langage + constitué des mots obtenus en précédant $w_0$ d'un nombre + quelconque ($i$) de copies de la lettre $b$ et en le suivant du même + nombre de copies de la lettre $a$ (par exemple, $bbababbaa$). \end{itemize} -Pour chacun des huit automates $A \in -\{A_{\mathrm{s}},A_{\mathrm{t}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{w}},A_{\mathrm{x}},A_{\mathrm{y}},A_{\mathrm{z}}\}$, -on pose les questions suivantes : - -\textbf{(a)} Parmi les dix langages $L_0,\ldots,L_9$, lequel est le -langage $L$ reconnu par l'automate $A$ ? On ne demande pas de -justifier la réponse. - -\textbf{(b)} Donner une expression rationnelle reconnaissant le -langage $L$ en question. On ne demande pas de justifier la réponse, -et il n'est pas obligatoire d'appliquer un algorithme vu en cours ; -par ailleurs, cette question-ci n'est pas posée pour -l'automate $A_{\mathrm{z}}$. - -\textbf{(c)} De quel type d'automate vu en cours (DFA complet, DFA à -spécification incomplète, NFA ou bien NFA à transitions spontanées) -l'automate $A$ est-il ? On donnera à chaque fois le type le plus -particulier applicable. - -\textbf{(d)} Donner un DFA complet sans état inaccessible équivalent -à $A$ (c'est-à-dire, reconnaissant le langage $L$). On ne traitera -que les cinq automates suivants : -$A_{\mathrm{s}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{x}},A_{\mathrm{z}}$ -(c'est-à-dire que cette question-ci n'est pas posée pour -$A_{\mathrm{t}},A_{\mathrm{w}},A_{\mathrm{y}}$) ; on appliquera les -algorithmes vus en cours en les nommant. +\textbf{(a)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire lequel ou +lesquels parmi les douze langages $L_0,\ldots,L_{11}$ est celui +reconnu par l'automate $A$. On ne demande pas de justifier la +réponse. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ reconnaît le langage $L_1 = \{w_0\}$. + +L'automate $A_{\mathrm{t}}$ reconnaît le langage $L_9$ des mots ayant +$w_0$ comme suffixe (car un chemin dans $A_{\mathrm{t}}$ finit par un +chemin consommant $w_0$). + +L'automate $A_{\mathrm{u}}$ reconnaît le langage $L_7$ des mots ayant +$w_0$ comme préfixe (car un chemin dans $A_{\mathrm{u}}$ commence +par un chemin consommant $w_0$). + +L'automate $A_{\mathrm{v}}$ reconnaît le langage $L_5$ des mots ayant +$w_0$ comme facteur (car un chemin dans $A_{\mathrm{u}}$ passe par un +chemin consommant $w_0$). + +L'automate $A_{\mathrm{w}}$ reconnaît le langage $L_3$ des mots ayant +$w_0$ comme sous-mot (car un chemin dans $A_{\mathrm{u}}$ consomme les +lettres $a,b,a,b,b$ dans cet ordre, intercalées par un nombre +quelconque de lettres quelconques). + +L'automate $A_{\mathrm{x}}$ reconnaît le langage $L_6$ des préfixes +de $w_0$ (car un chemin dans $A_{\mathrm{x}}$ consomme le début +de $w_0$). + +L'automate $A_{\mathrm{y}}$ reconnaît le langage $L_8$ des suffixes +de $w_0$ (car un chemin dans $A_{\mathrm{y}}$ consomme la fin +de $w_0$). + +L'automate $A_{\mathrm{z}}$ reconnaît le langage $L_4$ des facteurs +de $w_0$ (car un chemin dans $A_{\mathrm{z}}$ consomme un intervalle +de lettres consécutives de $w_0$). + +(Les justifications entre parenthèses n'étaient pas demandées.) +\end{corrige} + +\textbf{(b)} Pour chacun des sept automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}\}$ (cette question-ci n'est pas posée +pour $A_{\mathrm{z}}$), donner une expression rationnelle dénotant le +langage $L$ reconnu par $A$. On ne demande pas de justifier la +réponse, et il n'est pas obligatoire d'appliquer un algorithme vu en +cours. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ reconnaît le langage dénoté par $ababb$. + +L'automate $A_{\mathrm{t}}$ reconnaît le langage dénoté +par $(a|b){*}ababb$. + +L'automate $A_{\mathrm{u}}$ reconnaît le langage dénoté +par $ababb(a|b){*}$. + +L'automate $A_{\mathrm{v}}$ reconnaît le langage dénoté +par $(a|b){*}ababb(a|b){*}$. + +L'automate $A_{\mathrm{w}}$ reconnaît le langage dénoté +par $(a|b){*}a(a|b){*}b(a|b){*}a(a|b){*}b(a|b){*}b(a|b){*}$. + +L'automate $A_{\mathrm{x}}$ reconnaît le langage dénoté +par $\underline{\varepsilon}|a|ab|aba|abab|ababb$ (simple énumération +de tous les préfixes de $w_0$) ou, si on préfère, par +$\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|b))))$ +(obtenue en éliminant les états de $A_{\mathrm{x}}$ dans +l'ordre $5,4,3,2,1,0$). + +L'automate $A_{\mathrm{y}}$ reconnaît le langage dénoté +par $\underline{\varepsilon}|b|bb|abb|babb|ababb$ (simple énumération +de tous les suffixes de $w_0$) ou, si on préfère, par +$\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|a)b)a)b)b$ +(obtenue en éliminant les états de $A_{\mathrm{y}}$ dans +l'ordre $0,1,2,3,4,5$). +\end{corrige} + +\textbf{(c)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}}, +A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire de quel type +d'automate vu en cours (DFA complet, DFA à spécification incomplète, +NFA ou bien NFA à transitions spontanées) est l'automate $A$. On +donnera à chaque fois le type le plus particulier applicable. + +\begin{corrige} +L'automate $A_{\mathrm{s}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{t}}$ est un NFA (à cause de la double +transition étiquetée $a$ depuis l'état $0$). + +L'automate $A_{\mathrm{u}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{v}}$ est un NFA. + +L'automate $A_{\mathrm{w}}$ est un NFA. + +L'automate $A_{\mathrm{x}}$ est un DFA à spécification incomplète (ou +DFAi). + +L'automate $A_{\mathrm{y}}$ est un NFA (à cause des multiples états +initiaux). + +L'automate $A_{\mathrm{z}}$ est un NFA. +\end{corrige} + +\textbf{(d)} Pour chacun des cinq automates $A \in \{A_{\mathrm{s}}, +A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{x}}, A_{\mathrm{z}}\}$ +(cette question-ci n'est pas posée pour $A_{\mathrm{t}}, +A_{\mathrm{w}}, A_{\mathrm{y}}$), donner un DFA complet sans état +inaccessible qui soit équivalent à $A$ (c'est-à-dire, reconnaissant le +langage $L$). On appliquera un algorithme vu en cours en le nommant. + +{\footnotesize Conseil sur la présentation graphique : pour s'éviter + des maux de tête dans le placement des états (et en éviter aussi au + correcteur), il est conseillé de commencer par placer + horizontalement de gauche à droite les états successifs rencontrés + lors de la consommation du mot $w_0 = ababb$ par l'automate + construit, et d'ajouter ensuite les autres états éventuellement + nécessaires.\par} + +\begin{corrige} +S'agissant de $A_{\mathrm{s}}$, comme c'est un DFAi, il s'agit +simplement de lui ajouter un état « puits », noté $\bot$ ci-dessous, +où aboutissent toutes les transitions manquantes : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax +La construction est analogue pour $A_{\mathrm{u}}$ : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax S'agissant de $A_{\mathrm{v}}$, on a affaire à +un « vrai » non-déterminisme et on applique donc l'algorithme de +déterminisation vu en cours, qui donne (en omettant les accolades dans +le nommage des états) : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {\small $0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {\small $0,1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {\small $0,2$}; +\node (q3) at (180bp,0bp) [draw,circle,state] {\small $0,1,3$}; +\node (q4) at (240bp,0bp) [draw,circle,state] {\small $0,2,4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,final] {\small $0,5$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[loop below] node[auto]{$b$} (q0); +\draw[->] (q1) to[loop below] node[auto]{$a$} (q1); +\draw[->] (q2) to[out=120,in=60] node[auto,swap]{$b$} (q0); +\draw[->] (q3) to[out=120,in=60] node[auto,swap]{$a$} (q1); +\draw[->] (q4) to[out=120,in=60] node[auto,swap]{$a$} (q3); +\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax +La construction pour $A_{\mathrm{x}}$ est exactement comme pour +$A_{\mathrm{s}}$ sauf que les états $0$ à $5$ sont tous marqués +finaux : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$}; +\draw[->] (q0) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot); +\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot); +\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot); +\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip0ptplus20ex\relax +S'agissant de $A_{\mathrm{z}}$, on a de nouveau affaire à un « vrai » +non-déterminisme et on applique donc l'algorithme de déterminisation +vu en cours, qui donne (en omettant les accolades dans le nommage des +états) : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)] +\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2,4$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (q245) at (120bp,-120bp) [draw,circle,state,accepting below] {\small $2,4,5$}; +\node (qbot) at (300bp,-90bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (qI) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (qI) to[out=270,in=150] node[auto,swap]{$b$} (q245); +\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot); +\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5); +\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto,near start]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (q245) to[out=60,in=240] node[auto]{$a$} (q3); +\draw[->] (q245) to[out=30,in=240] node[auto,swap,very near end]{$b$} (q5); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +où on a noté $I$ au lieu de $\{0,1,2,3,4,5\}$. +\end{corrige} + +\textbf{(e)} Pour $A = A_{\mathrm{z}}$ (et seulement celui-ci), +minimiser le DFA trouvé à la question (d). + +\begin{corrige} +On a affaire à un DFA complet sans état inaccessible : on va le +minimiser avec l'algorithme de Moore. + +Dans une première étape, on fait deux classes d'état : celle des états +finaux, c'est-à-dire $I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ +et celle des états non-finaux, c'est-à-dire le seul +état $\varnothing$. + +Séparons maintenant les états selon la cible de la transition +étiquetée par $a$ : la classe formée de +$I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ se scinde en deux : +$I,\{2,4\},\{2,4,5\}$ d'une part, où elle mène à un état final, et +$\{1,3\},\{3\},\{4\},\{5\}$ d'autre part, où elle mène à un état +non-final. La cible de la transition étiquetée par $b$, pour sa part, +sépare $\{5\}$ de tous les autres états (le seul où elle mène à un +état non-final). À ce stade, on a quatre classes : la classe formée +de $I,\{2,4\},\{2,4,5\}$, celle de $\{1,3\},\{3\},\{4\}$, et deux +classes singleton, $\{5\}$ et $\varnothing$. + +À l'étape suivante, la cible de la transition étiquetée par $a$ ne +sépare rien (les états de la première classe mènent à la seconde et +les états de la seconde mènent au puits). La cible de la transition +étiquetée par $b$, en revanche, sépare la classe formée de +$I,\{2,4\},\{2,4,5\}$ en $I$ d'une part (qui mène à cette même classe) +et $\{2,4\},\{2,4,5\}$ de l'autre (qui mène à $\{5\}$) ; et elle +sépare la classe formée de $\{1,3\},\{3\},\{4\}$ en trois (puisque les +cibles sont dans trois classes distinctes). À ce stade, les seuls +états qui n'ont pas été séparés sont $\{2,4\}$ et $\{2,4,5\}$. Or +comme ils ont exactement les mêmes cibles de transitions étiquetées +par $a$ et $b$, ils ne sont pas séparés, donc l'algorithme s'applique +ici : il fusionne exactement deux états, à savoir +$\{2,4\}$ et $\{2,4,5\}$, en un seul, que nous noterons $B$ : +\begin{center} +\scalebox{0.85}{% +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)] +\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$}; +\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$}; +\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$B$}; +\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$}; +\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$}; +\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$}; +\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\varnothing$}; +\draw[->] (qI) -- node[auto]{$a$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$b$} (q4); +\draw[->] (q4) -- node[auto]{$b$} (q5); +\draw[->] (qI) to[out=60,in=120] node[auto]{$b$} (q2); +\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot); +\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5); +\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot); +\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot); +\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot); +\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot); +\end{tikzpicture} +} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +\textbf{(f)} Parmi les douze langages $L_0,\ldots,L_{11}$, lesquels +sont rationnels ? Lesquels sont algébriques ? Lesquels sont +décidables ? Lesquels sont semi-décidables ? On justifiera la +réponse à chaque fois (par exemple en donnant une expression +rationnelle, un automate, une grammaire hors-contexte, un algorithme, +ou n'importe quel autre type d'argument applicable permettant de +justifier la conclusion). + +\begin{corrige} +Les langages $L_1,L_3,L_4,L_5,L_6,L_7,L_8,L_9$ sont rationnels car ils +sont reconnaissables : on a vu que les automates $A_{\mathrm{s}}, +A_{\mathrm{w}}, A_{\mathrm{z}}, A_{\mathrm{v}}, A_{\mathrm{x}}, +A_{\mathrm{u}}, A_{\mathrm{y}}, A_{\mathrm{t}}$ respectivement les +reconnaissent. Il reste donc à traiter le cas de +$L_0,L_2,L_{10},L_{11}$. + +Les langages $L_0$ et $L_2$ sont rationnels car ils sont finis (on +peut donner des expressions rationnelles pour les deux, à savoir +$\bot$ pour $L_0$ et, en énumérant systématiquement tous les +sous-mots, $\varepsilon | b | bb | a | ab | abb | bbb | ba | bab | +babb | aa | aab | aabb | abbb | aba | abab | ababb$ pour $L_2$, mais +ce n'est pas très intéressant et ce n'était pas demandé). + +Le langage $L_{10} = \{w_0^i : i\in\mathbb{N}\} = L_1^*$ est rationnel +car il est l'étoile de Kleene d'un langage rationnel (si on préfère, +il est dénoté par l'expression rationnelle $(ababb){*}$). + +Tous les langages $L_0$ à $L_{10}$ sont donc rationnels, et, en +particulier, algébriques, décidables et semi-décidables. + +Reste à évoquer le cas du langage $L_{11} = \{b^i w_0 a^i : +i\in\mathbb{N}\}$. Montrons qu'il n'est pas rationnel, et montrons +qu'il est algébrique. + +Il n'est pas rationnel par le lemme de pompage. En effet, supposons +par l'absurde que $\{b^i w_0 a^i : i\in\mathbb{N}\}$ soit rationnel, +et soit $k$ tel que donné par le lemme de pompage. Considérons le mot +$t := b^k ababb a^k \in L_{11}$. D'après la propriété de $k$, il +existe une factorisation $t = uvw$ vérifiant les propriétés garanties +par le lemme de pompage. Le fait que $|uv|\leq k$, comme le préfixe +de longueur $k$ de $t$ est formé uniquement de la lettre $b$, assure +que $u = b^{\ell_1}$ et $v = b^{\ell_2}$ pour certains $\ell_1,\ell_2$ +avec, de plus, $\ell_2 > 0$ (car $v\neq\varepsilon$) et +$\ell_1+\ell_2\leq k$. On a alors $w = b^{k-\ell_1-\ell_2} ababb +a^k$, et $uv^iw = b^{k+(i-1)\ell_2} ababb a^k$. Comme les mots de +$L_{11}$ ont la propriété nécessaire que leur nombre initial de $b$ +(i.e., la longueur de leur plus long préfixe formé uniquement de la +lettre $b$) est égale à leur nombre final de $a$ (i.e., la longueur de +leur plus long suffixe formé uniquement de la lettre $a$), on devrait +avoir $k+(i-1)\ell_2 = k$, ce qui est une contradiction dès que $i\neq +1$. + +En revanche, le langage $L_{11}$ est algébrique, car il est engendré +par la grammaire suivante d'axiome $S$ : +\[ +S \rightarrow ababb \;|\; bSa +\] +Étant algébrique, le langage $L_{11}$ est décidable et semi-décidable. +(Au demeurant, il est facile de donner un algorithme qui décide si un +mot appartient à $L_{11}$ : on vérifie que son nombre initial de $b$ +est égal à son nombre final de $a$ et, une fois ce fait vérifié, on +vérifie qu'une fois retiré le préfixe et le suffixe en question il +reste exactement le mot $ababb$.) + +Pour résumer, tous les langages dont on a parlé sont algébriques, +décidables et semi-décidables, et tous sauf $L_{11}$ sont rationnels. +\end{corrige} |