diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 94 |
1 files changed, 55 insertions, 39 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 6e8df9b..b56b958 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1167,7 +1167,7 @@ L'extension la plus fréquente est celle des \emph{références arrière} facteur du mot se retrouve aussi à un autre emplacement. Par exemple, pour beaucoup de moteurs (notamment \texttt{egrep}), l'expression régulière « \texttt{(a*)b\char"5C\relax 1} » désigne le langage -$\{a^nba^n : a\in\mathbb{N}\} = \{b,aba, aabaa,\ldots\}$ des mots +$\{a^nba^n : n\in\mathbb{N}\} = \{b,aba, aabaa,\ldots\}$ des mots formés d'un nombre quelconque de $a$ puis d'un $b$ puis de la \emph{même suite de $a$} (le « \texttt{\char"5C\relax 1} » désigne « une copie de la chaîne de caractères qui a été capturée par le @@ -1229,7 +1229,7 @@ servent à ancrer l'expression au début et à la fin de la chaîne respectivement : c'est-à-dire que rechercher « \texttt{a} » recherche un \texttt{a} quelconque à l'intérieur de la chaîne donnée, rechercher « \texttt{\char"5E\relax a} » demande que le \texttt{a} soit au début -de la chaîne donnée rechercher « \texttt{a\char"24} » demande que le +de la chaîne donnée, rechercher « \texttt{a\char"24} » demande que le \texttt{a} soit à la fin de la chaîne donnée, et rechercher « \texttt{\char"5E\relax a\char"24} » demande que la chaîne donnée soit exactement \texttt{a} (cet exemple n'est donc pas très utile, @@ -1547,7 +1547,7 @@ accepte exactement les mots contenant un $a$ suivi, pas forcément immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un sous-mot (cf. \ref{definition-subword}). Ce langage est donc reconnaissable. (Il est aussi rationnel puisque dénoté par -l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.) +l'expression rationnelle $(b|c){*}a(a|c){*}b(a|b|c){*}$.) \thingy\label{definition-dfa-accessible-state} Un état $q$ d'un DFA est dit \defin[accessible (état)]{accessible} lorsqu'il existe un mot @@ -2757,11 +2757,11 @@ $(\varphi_2(q),x,q')$ où $(q,x,q') \in \delta_2$. (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord un unique état initial $q'_0$ à la réunion disjointe -de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$, -puis en éliminant les ε-transitions qu'on vient d'ajouter -(cf. \ref{removal-of-epsilon-transitions}) ainsi que les états $q_1$ -et $q_2$ devenus inutiles. Cela donne le même résultat que ce qui -vient d'être dit.) +de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$ +(qui cessent d'être initiaux), puis en éliminant les ε-transitions +qu'on vient d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi +que les états $q_1$ et $q_2$ devenus inutiles. Cela donne le même +résultat que ce qui vient d'être dit.) Il est alors clair qu'un chemin de l'état initial à un état final dans cet automate $A'$ consiste soit en un chemin d'un état initial à un @@ -2788,7 +2788,8 @@ L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant chaque transition sortant de $q_2$ par une transition identiquement étiquetée, et de même cible, partant de \emph{chaque} état final -de $A_1$. Graphiquement : +de $A_1$ (ces derniers seront marqués finaux si $q_2$ était final +dans $A_2$). Graphiquement : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] @@ -2852,19 +2853,20 @@ et De façon plus formelle, considérons un nouvel ensemble d'états $Q' = (Q_1 \uplus Q_2) \setminus \{q_2\}$ où $\uplus$ désigne la réunion disjointe. On définit alors l'automate $A'$ dont l'ensemble d'états -est $Q'$, l'état initial est $q_1$, les états finaux $F' = F_2$, et la -relation de transition $\delta$ est la réunion de $\delta_1$, de -l'ensemble des triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$, -et enfin de l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q') -\in \delta_2$ et que $q\in F_1$. +est $Q'$, l'état initial est $q_1$, l'ensemble $F'$ des états finaux +est $F_2$ si $q_2$ n'était pas final dans $A_2$ et $F_1 \cup F_2$ si +$q_2$ était final dans $A_2$, la relation de transition $\delta'$ +est la réunion de $\delta_1$, de l'ensemble des triplets $(q,x,q') \in +\delta_2$ tels que $q\neq q_2$, et enfin de l'ensemble des triplets +$(q,x,q')$ tels que $(q_2,x,q') \in \delta_2$ et que $q\in F_1$. (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord à la réunion disjointe de $A_1$ et $A_2$ une -ε-transition de chaque état final de $A_1$ vers $q_2$, puis en -éliminant les ε-transitions qu'on vient d'ajouter -(cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état $q_2$ -devenu inutile. Cela donne le même résultat que ce qui vient d'être -dit.) +ε-transition de chaque état final de $A_1$ vers $q_2$ (qui cesse +d'être initial), puis en éliminant les ε-transitions qu'on vient +d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état +$q_2$ devenu inutile. Cela donne le même résultat que ce qui vient +d'être dit.) Il est alors clair qu'un chemin de l'état initial $q_1$ à un état final dans cet automate $A'$ consiste en un chemin de $q_1$ à un état @@ -3639,21 +3641,35 @@ Symboliquement : \end{tikzpicture} \end{center} -Cette transformation doit être effectuée \emph{simultanément pour - toute paire} $(q_1,q_2)$ d'états de $A$ pour laquelle -$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$ : pour chaque -telle paire, on remplace l'étiquette de la transition $r_{12}$ entre -eux par $(r_{12}|r_1(s){*}r_2)$. Ceci ne change pas le fonctionnement -de l'automate, car tout chemin dans $A$ peut être remplacé par un -chemin dans $A'$ en effaçant simplement les $q$ (si on considère -$q_1$ et $q_2$ les états avant un bloc de $q$ dans le chemin, on -voit que le chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se -transformer en $q_1 \to q_2$ en consommant un mot qui vérifie -l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$). - -En éliminant (dans n'importe quel ordre) tous les états autres que -$q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant une unique -transition $(q_0,r,q_\infty)$, qui est donc essentiellement +Pour éliminer l'état $q$, cette transformation doit être effectuée +\emph{simultanément pour toute paire} $(q_1,q_2)$ d'états de $A$ (avec +$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$) pour laquelle il +existe une transition de $q_1$ vers $q$ et une transition de +$q$ vers $q_2$, \emph{y compris} s'il n'y avait pas déjà une +transition de $q_1$ vers $q_2$, et \emph{y compris} si $q_1=q_2$ : +pour \emph{chaque} telle paire, on remplace l'étiquette de la +transition $r_{12}$ entre eux par $(r_{12}|r_1(s){*}r_2)$. (On +prendra garde aux cas particuliers suivants : si la transition de $q$ +vers lui-même n'existait pas, ce qui revient à prendre $s=\bot$, alors +on remplace la transition $r_{12}$ par $(r_{12}|r_1 r_2)$ en vertu du +fait que $(\bot){*}$ est équivalente à $\underline{\varepsilon}$ ; et +si la transition de $q_1$ vers $q_2$ n'existait pas, ce qui revient à +prendre $r_{12}=\bot$, alors on la crée avec l'étiquette +$r_1(s){*}r_2$ ; et bien sûr, en combinant ces deux cas particuliers, +s'il n'y avait ni transition de $q$ vers lui-même ni de +$q_1$ vers $q_2$, on crée cette dernière avec l'étiquette $r_1 r_2$.) + +La transformation qui vient d'être décrite ne change pas le +fonctionnement de l'automate, car tout chemin dans $A$ peut être +remplacé par un chemin dans $A'$ en effaçant simplement les $q$ (si on +considère $q_1$ et $q_2$ les états avant un bloc de $q$ dans le +chemin, on voit que le chemin $q_1 \to q \to q \to \cdots \to q \to +q_2$ peut se transformer en $q_1 \to q_2$ en consommant un mot qui +vérifie l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$). + +En éliminant (successivement dans n'importe quel ordre) tous les états +autres que $q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant +une unique transition $(q_0,r,q_\infty)$, qui est donc essentiellement l'expression rationnelle $r$. \end{proof} @@ -4271,7 +4287,7 @@ Voici comment on peut le mettre en œuvre de façon plus concrète : état inaccessible}} (si nécessaire, déterminiser l'automate s'il n'est pas déterministe, le compléter s'il est incomplet, et supprimer les états inaccessibles s'il y en a) ; -\item appeler $\Pi$ la partition des automates en deux classes : les +\item appeler $\Pi$ la partition des états en deux classes : les états finaux d'un côté, et les non-finaux de l'autre ; \item répéter l'opération suivante tant que la partition $\Pi$ change : pour chaque classe $C$ de $\Pi$ et chaque lettre $x \in @@ -5028,7 +5044,7 @@ langage $L(G)$ que la précédente (elle est donc faiblement équivalente l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire (d'axiome $S$) \[ \begin{aligned} -S &\rightarrow U \;|\; V \;|\; \varepsilon\\ +S &\rightarrow U \;|\; V\\ U &\rightarrow aUb \;|\; ab\\ V &\rightarrow aVbb \;|\; abb\\ \end{aligned} @@ -5154,8 +5170,8 @@ Un raisonnement analogue montre que la grammaire $G'$ donnée par \[ \begin{aligned} S &\rightarrow aUbS \;|\; bVaS \;|\; \varepsilon\\ -U &\rightarrow aUbU\\ -V &\rightarrow bVaV\\ +U &\rightarrow aUbU \;|\; \varepsilon\\ +V &\rightarrow bVaV \;|\; \varepsilon\\ \end{aligned} \] engendre le même langage $L = \{w \in\Sigma^* : |w|_a = |w|_b\}$ que @@ -9242,7 +9258,7 @@ termine en renvoyant vrai (sinon, bien sûr, on ne termine pas). Pour semi-décider $L_1\cap L_2$, en revanche, il n'y a pas de raison de procéder en parallèle : on lance d'abord $T_1$ sur le mot $w$ à -tester : si $T_1$ termine, on lance ensuite $T_1$ sur le même mot : si +tester : si $T_1$ termine, on lance ensuite $T_2$ sur le même mot : si $T_2$ termine et renvoie vrai, on renvoie vrai ; si l'un des deux algorithmes $T_i$ lancés séquentiellement ne termine pas, bien sûr, le calcul dans son ensemble ne terminera pas. |