diff options
| -rw-r--r-- | notes-inf105.tex | 60 |
1 files changed, 52 insertions, 8 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 356afd6..57a9267 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1659,7 +1659,7 @@ $q_n \in C(q_{j_m}) \cap F$). Le mot $w$ supposé accepté par $A$ est donc accepté par $A^\S$. La réciproque est analogue. \end{proof} -\thingy On dit que le NFA $A^\S$ est obtenu en \textbf{supprimant les +\thingy On dit que le NFA $A^\S$ est obtenu en \textbf{éliminant les ε-transitions} dans le εNFA $A$ lorsqu'il est obtenu par la procédure décrite dans la démonstration de cette proposition, et en supprimant tous les états non-initiaux de $A^\S$ auxquels @@ -1670,7 +1670,7 @@ 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$. -\thingy À titre d'exemple, supprimons les ε-transitions du εNFA $A$ +\thingy À titre d'exemple, éliminons les ε-transitions du εNFA $A$ présenté en \ref{discussion-example5} : comme $C(0) = \{0,1,2\}$, on fait partir de $0$ toutes les transitions partant d'un des états $0,1,2$ et étiquetées par une lettre, et de même, comme $C(1) = @@ -1986,11 +1986,12 @@ initial de $A$ en question et suivi d'une ε-transition de l'état final de $A$ en question vers $q_0$. On a donc bien $L_{A'} = L^*$. \end{proof} -\begin{prop}\label{rational-languages-are-recognizable} +\begin{cor}\label{rational-languages-are-recognizable} Tout langage rationnel est reconnaissable ; de plus, un εNFA le reconnaissant se déduit algorithmiquement d'une expression rationnelle -le dénotant. -\end{prop} +le dénotant. (Et en particulier, il est possible de décider +algorithmiquement si un mot vérifie une expression rationnelle.) +\end{cor} \begin{proof} Cela résulte de façon évidente de la définition des langages rationnels (cf. §\ref{subsection-rational-languages}), du fait que les @@ -1998,6 +1999,15 @@ langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour chaque $x\in\Sigma$) sont reconnaissables par automates finis, et des propositions \ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}. + +Pour décider si un mot vérifie une expression rationnelle, on peut +commencer par transformer cette expression rationnelle en εNFA (i.e., +construire un εNFA reconnaissant le langage qu'elle dénote) comme on +vient de l'expliquer, et transformer ensuite cet automate en DFA +quitte à éliminer les ε-transitions +(cf. \ref{removal-of-epsilon-transitions}) et à déterminiser +(cf. \ref{determinization-of-nfa}), après quoi il est facile de tester +si l'automate accepte le mot. \end{proof} \textcolor{red}{TODO: Standardiser la construction des automates. Par @@ -2165,7 +2175,7 @@ pas l'état final) et $q_2$ peut être l'état final (mais pas l'état initial). On a vu en \ref{give-rnfa-single-transitions} qu'on pouvait supposer qu'il existait une unique transition $(q_1,r_{12},q_2)$ et de même $(q_1,r_1,q)$ et $(q,r_2,q_2)$ et $(q,s,q)$ (transition de $q$ -vers lui-même). En même temps qu'on supprime $q$, on met dans $A'$ la +vers lui-même). En même temps qu'on élimine $q$, on met dans $A'$ la transition $(r_{12}|r_1(s){*}r_2)$ entre $q_1$ et $q_2$. Symboliquement : @@ -2193,13 +2203,13 @@ $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 supprimant simplement les $q$ (si on considère +chemin dans $A'$ en effaçant simplement les $q$ (si on considère $q_1$ et $q_2$ les états avant un bloc de 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 supprimant (dans n'importe quel ordre) tous les états autres que +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 l'expression rationnelle $r$. @@ -2789,6 +2799,40 @@ En revanche, si on change l'automate pour rendre l'état $4$ non-final aboutit sur la partition triviale en six états, c'est-à-dire que l'automate est, en fait, déjà minimal. +\begin{cor} +On peut décider algorithmiquement si deux automates finis (de +n'importe quelle sorte), ou deux expressions rationnelles, ou un +automate et une expression rationnelle, sont équivalents (au sens de +dénoter le même langage). +\end{cor} +\begin{proof} +D'après ce qu'on a déjà vu, et quitte à transformer une expression +rationnelle en εNFA (cf. \ref{rational-languages-are-recognizable}), +et quitte à éliminer les ε-transitions +(cf. \ref{removal-of-epsilon-transitions}) et à déterminiser +(cf. \ref{determinization-of-nfa}), on peut construire +algorithmiquement un DFA reconnaissant le même langage que chacune des +deux données. La question devient donc de savoir si deux DFA +reconnaissent le même langage. Or d'après \ref{dfa-minimization}, on +sait transformer un DFA en DFA minimal reconnaissant le même langage, +et d'après \ref{myhill-nerode} on sait que ce DFA est unique à +renumérotation près des états. On est donc ramené au problème +suivant : donnés deux DFA $A$ et $A'$ (complets et sans états +inaccessibles), trouver s'ils sont le même à renumérotation près +(i.e., s'ils sont isomorphes). + +La correspondance entre états de $A$ et de $A'$ peut se construire +état par état : on fait correspondre l'état initial de $A$ à celui +de $A'$, puis pour chaque état $q$ de $A$ mis en correspondance avec +un état $q'$ de $A'$, on fait correspondre chacun des états +$\delta(q,x)$ avec chacun des états $\delta'(q',x)$ où $x$ parcourt +les lettres de l'alphabet. Si on aboutit ainsi à une contradiction +(deux états de l'un des automates veulent être mis en correspondance +avec le même état de l'autre), on renvoie un échec ; sinon, tous les +états de $A$ et ceux de $A'$ seront mis en correspondance bijective, +et les langages reconnus sont les mêmes. +\end{proof} + % |