diff options
| -rw-r--r-- | notes-inf105.tex | 22 |
1 files changed, 11 insertions, 11 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 3c5b549..158db95 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2329,7 +2329,7 @@ démonstration de cette proposition, et en supprimant tous les états non-initiaux de $A^\S$ auxquels n'aboutissent dans $A$ que des ε-transitions (ces états sont devenus inaccessibles dans $A^\S$). Algorithmiquement, il s'agit donc, pour chaque état $q\in Q$ et chaque -$q^\sharp$ dans la ε-femerture $C(q)$ de $q$, de créer une transition +$q^\sharp$ dans la ε-fermeture $C(q)$ de $q$, de créer une transition $q\to q'$ étiquetée par $x$ dans $A^\S$ pour chaque transition $q^\sharp\to q'$ étiquetée par $x$ dans $A$. @@ -2535,7 +2535,7 @@ et finaux). L'automate ainsi construit en inversant toutes les flèches d'un automate $A$ (la définition précise est donnée dans la démonstration qui suit) et qui reconnaît le langage miroir de celui reconnu par $A$ -peut s'appeller automate \defin[transposé (automate)]{transposé} +peut s'appeler automate \defin[transposé (automate)]{transposé} $A^{\mathsf{R}}$ de $A$. \begin{proof} @@ -2990,7 +2990,7 @@ commence par transformer cette expression rationnelle en NFA comme on vient de l'expliquer (c'est-à-dire construire un NFA $A(r)$ reconnaissant le langage $L(r)$ dénoté par $r$), puis on déterminise cet automate (cf. \ref{determinization-of-nfa}), après quoi il est -facile de tester si le DFA résultant de la déterministaion accepte le +facile de tester si le DFA résultant de la déterminisation accepte le mot $w$ considéré (il suffit de suivre l'unique chemin dans l'automate partant de l'état initial et étiqueté par $w$, et de voir si l'état auquel il aboutit est final). @@ -3060,7 +3060,7 @@ Ces observations sont utiles pour détecter des erreurs lors de la construction de l'automate. \thingy À titre d'exemple pour illustrer la construction de Glushkov, -construsions l'automate qu'elle associe à l'expression rationnelle +construisons l'automate qu'elle associe à l'expression rationnelle $((a{*}|b)c){*}$ sur l'alphabet $\Sigma = \{a,b,c\}$. On doit obtenir un automate ayant $4$ états. @@ -3171,7 +3171,7 @@ celles aboutissant à $3$ sont étiquetées $c$. \thingy La construction de Glushkov (exposée en \ref{glushkov-construction}) d'un automate reconnaissant le langage dénoté par expression rationnelle $r$ fabrique un NFA. Cette -constrution produit un automate raisonnablement compact (en nombre +construction produit un automate raisonnablement compact (en nombre d'états), mais il peut être intéressant de disposer d'une autre construction, plus transparente mais moins efficace : la \defin[Thompson (construction d'automate de)]{construction de @@ -3661,7 +3661,7 @@ n'existait pas au départ, lorsqu'on peut arriver de l'un vers l'autre en passant par $q$. Et il faut se souvenir que le cas $q_2=q_1$ est à traiter aussi. -En général, l'élimination des états conduit à un expression +En général, l'élimination des états conduit à une expression extrêmement compliquée (exponentielle dans le nombre d'états de l'automate, au moins dans le pire cas, mais aussi dans beaucoup de cas « typiques »). @@ -3786,7 +3786,7 @@ $(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente. Il s'agit d'un automate « compteur limité », qui ne sait compter que de $0$ à $4$, incrémentant son compteur quand il reçoit un $a$ et le -décrementant quand il reçoit un $b$ (et cessant de fonctionner si le +décrémentant quand il reçoit un $b$ (et cessant de fonctionner si le compteur passe au-dessus du maximum ou en-dessous du minimum), et qui accepte finalement les mots dont le nombre de $b$ égale le nombre de $a$ sans qu'il y ait jamais eu plus de $b$ que de $a$ ni plus de @@ -4208,7 +4208,7 @@ de \ref{myhill-nerode} on vérifie qu'elle préserve l'état initial, les l'automate minimal en fusionnant chaque classe d'équivalence pour $\equiv$. -Montrons maintenant comment on peut construre $\equiv$ +Montrons maintenant comment on peut construire $\equiv$ algorithmiquement. Pour cela, on va définir des relations d'équivalence $\equiv_i$ pour $i\in\mathbb{N}$ par \[ @@ -4814,7 +4814,7 @@ $(q_{i-1},t_i,q_i) \in \delta$ pour $1\leq i\leq n$, suivie lorsque $q_n \in F$. Manifestement, les dérivations de la sorte (terminant sur un mot sur $\Sigma$) sont en bijection avec les chemins $q_0 \to \cdots \to q_n$ dans $A$ où $q_n \in F$, et le mot $t_1\cdots -t_n$ dérivé est précisément le mot formé en concacténant les +t_n$ dérivé est précisément le mot formé en concaténant les étiquettes du chemin. On a donc bien $L(G) = L(A)$. \end{proof} @@ -5523,7 +5523,7 @@ On a vu en §\ref{subsection-pumping-lemma} une condition nécessaire que doivent vérifier les langages rationnels, et qui est souvent utile pour montrer qu'un langage \emph{n'est pas} rationnel. Un lemme tout à fait analogue existe pour les langages algébriques, est qui s'avère -utile dans des circonstance semblables, même si son emploi est plus +utile dans des circonstances semblables, même si son emploi est plus difficile ; on prendra garde au fait que, dans l'énoncé suivant, $x$ et $y$ désignent des mots et non des lettres comme d'habitude : @@ -6580,7 +6580,7 @@ numéro $e$ en entrée, i.e., si $\varphi_e(e)\downarrow$, (2º) si oui, effectuer une boucle infinie, et si non, terminer, en renvoyant, disons, $42$. L'algorithme qui vient d'être décrit aurait un certain numéro, disons, $p$, et la description de l'algorithme fait que, -quelque soit $e$, la valeur $\varphi_p(e)$ est indéfinie si +quel que soit $e$, la valeur $\varphi_p(e)$ est indéfinie si $\varphi_e(e)$ est définie tandis que $\varphi_p(e)$ est définie (de valeur $42$) si $\varphi_e(e)$ est indéfinie. En particulier, en prenant $e=p$, on voit que $\varphi_p(p)$ devrait être défini si et |