From a06f5fa43d0fc4b7e7663bc7fa370796209627cd Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 30 Jan 2017 17:25:07 +0100 Subject: Re-read exercises. --- exercices3.tex | 85 +++++++++++++++++++++++++++++++++------------------------- 1 file changed, 48 insertions(+), 37 deletions(-) diff --git a/exercices3.tex b/exercices3.tex index c2f41cb..7ebae19 100644 --- a/exercices3.tex +++ b/exercices3.tex @@ -106,9 +106,9 @@ $a{*}(baa{*}){*}$. Cet automate est-il déterministe ? (2) En éliminer les transitions spontanées. -(3) Déterminiser l'automate obtenu. +(3) Déterminiser l'automate obtenu (on demande un automate complet). -(4) Minimiser l'automate obtenu. +(4) Minimiser l'automate obtenu (on demande un automate complet). (5) Vérifier le résultat en décrivant en français le langage dénoté par l'expression rationnelle initiale et reconnu par l'automate @@ -179,16 +179,17 @@ les ε-fermetures $C(q)$ de ces états sont les suivantes : $q$&ε-fermeture $C(q)$\\ \hline $0$&$\{0,1,3,4,5,13\}$\\ -$2$&$\{2,3,4,5,13\}$\\ +$2$&$\{1,2,3,4,5,13\}$\\ $6$&$\{6,7\}$\\ $8$&$\{5,8,9,10,12,13\}$\\ $11$&$\{5,10,11,12,13\}$\\ \end{tabular} \end{center} -En remplaçant chaque transition $q^\sharp \to q'$ étiquetée par $x$ -dans l'automate par une transition $q\to q'$ pour chaque état $q$ tel -que $q^\sharp \in C(q)$, on obtient le NFA suivant : +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 le NFA +suivant : \begin{center} %%% begin ex3p1b %%% @@ -307,10 +308,10 @@ l'alphabet $\Sigma = \{a,b\}$ : %%% end ex3p2 %%% \end{center} (On pourra considérer les ordres suivants d'élimination des états : -d'abord $2,1,0$, ensuite $1,2,0$ et enfin $0,2,1$.) +(A) $2,1,0$, ensuite (B) $1,2,0$ et enfin (C) $0,2,1$.) \begin{corrige} -Si on commence par éliminer l'état $2$ (en considérant l'automate +(A) Si on commence par éliminer l'état $2$ (en considérant l'automate comme un automate à transitions étiquetées par des expressions rationnelles), l'état $1$ reçoit une transition vers lui-même étiquetée $ab{*}a$. Si on élimine l'état $1$, l'état $0$ reçoit à la @@ -325,7 +326,9 @@ obtient finalement l'expression rationnelle (a|b(ab{*}a){*}b){*} \] -Si on commence par éliminer l'état $1$, il apparaît une transition +\smallbreak + +(B) Si on commence par éliminer l'état $1$, il apparaît une transition $0\to 2$ étiquetée $ba$ et une $2\to 0$ étiquetée $ab$ (si on veut appliquer l'algorithme de façon puremnet mécanique, l'état $1$ n'a pas de transition vers lui-même, c'est-à-dire qu'on pourrait l'étiqueter @@ -345,7 +348,9 @@ une seule étiquetée par $a|b(a(b|aa){*}a){*}b$. On obtient finalement (en particulier, cette expression est équivalente à celle obtenue précédemment). -Si on préfère commencer par éliminer l'état $0$, il faut au préalable +\smallbreak + +(C) Si on préfère commencer par éliminer l'état $0$, il faut au préalable ajouter un nouvel état initial $I$ (conduisant à $0$ par une transition spontanée) et un nouvel état final $F$ (vers lequel $0$ conduit par une transition spontanée). L'élimination de l'état $0$ @@ -392,7 +397,7 @@ auv$. \in L$ alors on a $wz \not\in L$ pour tout $z \in \Sigma^+$ (c'est-à-dire $z \in \Sigma^*$ et $z \neq \varepsilon$). Autrement dit : en ajoutant des lettres à la fin d'un mot de $L$ on obtient un -mot qui n'appartient jamais à $L$. (Indication : lorsque $auvz = +mot qui n'appartient jamais à $L$. (Indication : si on a $auvz = au'v'$ on pourra considérer les cas (i) $|u'|>|u|$, (ii) $|u'|<|u|$ et (iii) $|u'|=|u|$.) @@ -406,10 +411,11 @@ sur $|w|$). (5) En s'inspirant des questions précédentes, décrire un algorithme simple (en une seule fonction récursive) qui, donné un mot -$w\in\Sigma^*$, décide si $w\in L$ (c'est-à-dire répond vrai ou faux -selon que $w\in L$ ou $w\not\in L$) ou plus généralement, donné -$w\in\Sigma^*$, renvoie la longueur du préfixe de $w$ appartenant -à $L$ s'il existe (il est alors unique d'après la question (2)). +$w\in\Sigma^*$ renvoie la longueur du préfixe de $w$ appartenant à $L$ +s'il existe (il est alors unique d'après la question (2)) ou bien +« échec » s'il n'existe pas ; expliquer comment s'en servir pour +décider si $w\in L$ (i.e., écrire une fonction qui répond vrai ou faux +selon que $w\in L$ ou $w\not\in L$). \begin{corrige} (0) Quelques exemples de mots dans $L$ sont $b$, $abb$, $aabbb$, @@ -417,17 +423,17 @@ $w\in\Sigma^*$, renvoie la longueur du préfixe de $w$ appartenant (1) Si $w \in L$, considérons un arbre d'analyse $\mathscr{W}$ de $w$ pour $G$ : sa racine, étiquetée $S$, doit avoir des fils étiquetés - selon l'une des deux règles de la grammaire, $S\rightarrow b$ ou - bien $S\rightarrow aSS$, autrement dit, soit elle a un unique fils - étiqueté $b$, soit elle a trois fils étiquetés respectivement + selon l'une des deux règles de la grammaire, soit $S\rightarrow b$ + ou bien $S\rightarrow aSS$, autrement dit, soit elle a un unique + fils étiqueté $b$, soit elle a trois fils étiquetés respectivement $a,S,S$. Dans le premier cas, le mot $w$ est simplement $b$ ; dans le second, les sous-arbres $\mathscr{U}, \mathscr{V}$ ayant pour racine les deux fils étiquetés $S$ sont encore des arbres d'analyse pour $G$, et si on appelle $u$ et $v$ les mots dont ils sont des arbres d'analyse (c'est-à-dire, ceux obtenus en lisant les feuilles de $\mathscr{U}$ et $\mathscr{V}$ respectivement par ordre de - profondeur), alors on a $w = auv$ et $u,v\in L$ puisqu'ils ont des - arbres d'analyse pour $G$. + profondeur), alors on a $w = auv$ et $u,v\in L$ (puisqu'ils ont des + arbres d'analyse pour $G$). La réciproque est analogue : le mot $b$ appartient trivialement à $L$, et si $u,v\in L$, ils ont des arbres d'analyse $\mathscr{U}, @@ -490,8 +496,9 @@ deux cas sont évidemment incompatibles : il reste donc simplement à expliquer que dans le dernier, $\mathscr{U}$ et $\mathscr{V}$ sont uniquement déterminés. Or la question (3) assure que $u,v$ (tels que $w=auv$) sont uniquement déterminés, et l'hypothèse de récurrence -permet de conclure que les arbres d'analyse $\mathscr{U}$ et -$\mathscr{V}$ sont uniquement déterminés, comme on le voulait. +permet de conclure (comme $|u|<|w|$ et $|v|<|w|$) que les arbres +d'analyse $\mathscr{U}$ et $\mathscr{V}$ de $u$ et $v$ sont uniquement +déterminés, comme on le voulait. \smallbreak @@ -507,8 +514,8 @@ appartenant à $L$, ou bien « échec » si ce préfixe n'existe pas : \item appeler la fonction elle-même (rechercher préfixe dans $L$) sur $x$ : \item si elle échoue, renvoyer échec, -\item si elle retourne $k$, soit $u$ le préfixe de $y$ de longueur - $k$, et $z$ le suffixe correspondant (c'est-à-dire $y = ux$, ou si +\item si elle retourne $k$, soit $u$ le préfixe de $x$ de longueur + $k$, et $y$ le suffixe correspondant (c'est-à-dire $x = uy$, ou si on préfère, $y$ enlève les $k$ premières lettres de $x$), \item appeler la fonction elle-même (rechercher préfixe dans $L$) sur $y$ : @@ -529,7 +536,7 @@ dernier cas, $u$ et $v$ sont uniquement déterminés (c'est ce qu'affirme la non-ambiguïté de la grammaire). (Il s'agit ici du cas le plus simple d'un analyseur LL, et -l'algorithme présenté ci-dessus est essentiellement un analyseur LL +l'algorithme présenté ci-dessus est essentiellement un analyseur LL(1) camouflé sous forme d'analyseur par descente récursive.) \end{corrige} @@ -658,7 +665,7 @@ de l'arrêt.) allant de $2$ à $|w|$ et qui divise $|w|$, considérer les $k$ facteurs successifs de $w$ de longueur $|w|/k$ (c'est-à-dire, pour $0\leq i