diff options
| -rw-r--r-- | notes-inf105.tex | 141 |
1 files changed, 106 insertions, 35 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index a946e4a..4491278 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1347,7 +1347,8 @@ eux. \thingy\label{definition-dfai} Un \textbf{automate fini déterministe à spécification incomplète} ou \textbf{...partielle}, ou simplement -\defin{automate fini déterministe incomplet}\footnote{Le mot +\defin{automate fini déterministe + incomplet}\footnote{\label{footnote-on-word-incomplete}Le mot « incomplet » signifie en fait « non nécessairement complet », i.e., l'automate a le droit de manquer certaines transitions, il peut très bien être complet.}, en abrégé \index{DFAI|see{automate fini @@ -1561,7 +1562,11 @@ DFAI en ne conservant que ses états utiles : ainsi, tout DFAI est \thingy Il faut prendre garde au fait que certains auteurs définissent les « automates finis déterministes » (sans précision supplémentaire) comme étant complets par défaut, d'autres comme étant incomplets par -défaut. +défaut. Le plus prudent est de préciser systématiquement « complet » +ou « incomplet » (en se rappelant qu'« incomplet » signifie « non +nécessairement complet », cf. la +note \ref{footnote-on-word-incomplete} sous \ref{definition-dfai}) dès +qu'il est important de ne pas confondre. \subsection{Automates finis non-déterministes (=NFA)} @@ -1844,6 +1849,20 @@ $\{0,1,2\}$ mémorise « les deux dernières lettres étaient des $a$ », et l'état $\{0,2\}$ mémorise « la dernière lettre était un $b$, mais la précédente était un $a$ ». +\thingy On vient donc de voir que les NFA sont équivalents aux DFA en +ce sens qu'ils permettent de définir les mêmes langages. Il est +néanmoins intéressant de les définir et de les étudier pour plusieurs +raisons : d'une part, l'équivalence qu'on vient de voir, c'est-à-dire +la déterminisation d'un NFA en DFA, a un coût algorithmique important +(exponentiel en nombre d'états dans le pire cas), d'autre part, +certaines opérations sur les automates se définissent plus +naturellement sur les NFA que sur les DFA, et certaines constructions +conduisent naturellement à un NFA. On verra en particulier +en \ref{subsection-recognizable-languages-under-rational-operations} +que pour transformer une expression rationnelle en automate, on +passera naturellement par un NFA, même si on peut souhaiter le +déterminiser ensuite. + \subsection{Automates finis non-déterministes à transitions spontanées (=εNFA)} @@ -2011,7 +2030,8 @@ $q^\sharp$ dans la ε-femerture $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$. -\thingy À titre d'exemple, éliminons les ε-transitions du εNFA $A$ +\thingy\label{removal-of-epsilon-transitions-from-example5} +À 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) = @@ -2082,6 +2102,22 @@ choix. \par} +\thingy L'intérêt des εNFA, même s'ils sont finalement équivalents aux +NFA, est que certaines constructions sur les automates sont plus +simples ou plus transparentes lorsqu'on s'autorise à fabriquer des +εNFA (à titre d'exemple, l'automate présenté +en \ref{discussion-example5} est beaucoup plus transparent à lire que +le NFA équivalent donné +en \ref{removal-of-epsilon-transitions-from-example5}). On verra +notamment en \ref{subsection-thompson-construction} qu'il est facile +(quoique inefficace) de construire un εNFA reconnaissant le langage +dénoté par une expression rationnelle quelconque ; et +en \ref{subsection-recognizable-languages-under-rational-operations} +que, même si on fabrique directement un NFA, il peut être utile +d'introduire temporairement des transitions spontanées dans la +construction de ce NFA, quitte à les éliminer immédiatement (cela +simplifie la description). + \section{Langages reconnaissables et langages rationnels}\label{section-recognizable-languages} @@ -2095,8 +2131,11 @@ on peut remplacer « DFA » dans cette définition par « DFAI », « NFA ou « εNFA » sans changer la définition. Nous allons maintenant montrer que les langages reconnaissables sont -stables par différentes opérations : complémentaire, union, -intersection, concaténation et étoile de Kleene. +stables par différentes opérations. Dans cette section, nous traitons +le cas des opérations booléennes (complémentaire, union, intersection) +et l'opération « miroir » ; la +section \ref{subsection-recognizable-languages-under-rational-operations} +traite des opérations booléennes. \begin{prop}\label{dfa-complement} Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors @@ -2164,7 +2203,7 @@ sous-ensemble de $Q'' = Q_1\times Q_2$ formé des couples dont \emph{l'une au moins} des deux composantes est finale. \end{proof} -\thingy La construction $A'$ ci-dessus est parfois appelée +\thingy La construction $A'$ ci-dessus est parfois appelée automate \index{produit (d'automates)}\emph{produit} des DFA $A_1$ et $A_2$. La construction de l'automate produit pour fabriquer le langage @@ -2192,7 +2231,7 @@ peut s'appeller automate \defin[transposé (automate)]{transposé} $A^{\mathsf{R}}$ de $A$. \begin{proof} -Par hypothèse, il existe un εNFA ou un NFA $A = (Q,I,F,\delta)$ tel +Par hypothèse, il existe un NFA ou un εNFA $A = (Q,I,F,\delta)$ tel que $L = L_A$. Considérons l'automate $A^{\mathsf{R}}$ de même type défini par l'ensemble d'états $Q^{\mathsf{R}} = Q$ et inversant toutes les flèches de $A$, c'est-à-dire $I^{\mathsf{R}} = F$ et @@ -2215,7 +2254,7 @@ chaque état $q$ et chaque lettre $x$, il existe une unique arête aboutissant à $q$ et étiquetée par $x$ — sont parfois dits « co-déterministes ».) -\subsection{Stabilité des langages reconnaissables par opérations rationnelles, automates standards, construction de Glushkov} +\subsection{Stabilité des langages reconnaissables par opérations rationnelles, automates standards, construction de Glushkov}\label{subsection-recognizable-languages-under-rational-operations} \thingy Nous allons maintenant montrer que la classe des langages reconnaissables est stable par les opérations rationnelles (union, @@ -2224,12 +2263,16 @@ cf. \ref{stable-under-rational-operations} ; on l'a déjà vu sur les DFA en \ref{dfa-union-and-intersection} pour la réunion, mais on va en donner une nouvelle démonstration, cette fois basée sur les NFA, qui a un contenu algorithmique utile dans des circonstances différentes). +Cela permettra de conclure que les langages rationnels sont +reconnaissables (la réciproque faisant l'objet de la +section \ref{subsection-rnfa-and-kleenes-algorithm}). Pour établir ces stabilités, on va travailler sur les NFA et utiliser la construction parfois appelée « de Glushkov » ou « automate -standard ». Celle-ci travaille, en fait, sur des NFA vérifiant une -propriété supplémentaire facile à assurer, et on va commencer par un -lemme dans ce sens : +standard » ; ceci fournira un « automate de Glushkov » pour chaque +expression rationnelle $r$. Cette construction travaille, en fait, +sur des NFA vérifiant une propriété supplémentaire facile à assurer, +et on va commencer par un lemme dans ce sens : \begin{lem}\label{standard-automaton-lemma} Soit $A$ un NFA. Alors il existe un NFA $A'$ (sur le même @@ -2283,8 +2326,8 @@ La figure suivante illustre la transformation en question : (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord un unique état initial $q_0$ et des ε-transitions de -$q_0$ vers chacun des états initiaux de $A$, puis en éliminant les -ε-transitions qu'on vient d'ajouter +$q_0$ vers chacun des états qui étaient initiaux dans $A$, puis en +éliminant les ε-transitions qu'on vient d'ajouter (cf. \ref{removal-of-epsilon-transitions}). Cela donne le même résultat que ce qui vient d'être dit.) \end{proof} @@ -2311,8 +2354,9 @@ des NFA standards tels que $L_1 = L_{A_1}$ et $L_2 = L_{A_2}$. L'automate $A'$ s'obtient réunissant $A_1$ et $A_2$ mais en « fusionnant » les états initiaux $q_1$ et $q_2$ de $A_1$ et $A_2$ en -un unique état initial $q'_0$, d'où partent les mêmes transitions que -de l'un ou de l'autre : +un unique état initial $q'_0$, d'où partent les mêmes transitions +(avec les mêmes étiquettes) que depuis l'un ou de l'autre de +$q_1$ ou $q_2$. Graphiquement : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] @@ -2415,7 +2459,8 @@ des NFA standards tels que $L_1 = L_{A_1}$ et $L_2 = L_{A_2}$. 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 partant de chaque état final de $A_1$ : +étiquetée partant de \emph{chaque} état final de $A_1$. +Graphiquement : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] @@ -2577,7 +2622,9 @@ dans $A$. On a donc bien $L_{A'} = L^*$. également des NFA (« standards » au sens de \ref{standard-automaton-lemma}) reconnaissant les langages de base triviaux $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour -chaque $x\in\Sigma$). On prendra les suivants : +chaque $x\in\Sigma$), c'est-à-dire ceux dénotés par les expressions +rationnelles $\bot$, $\underline{\varepsilon}$ et $x$ respectivement. +On prendra les suivants : \begin{center} \begin{tabular}{ll} @@ -2612,24 +2659,48 @@ langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour chaque $x\in\Sigma$) sont reconnaissables par automates finis (cf. \ref{trivial-standard-automata}), et grâce aux propositions \ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}. +(Cf. \ref{glushkov-construction} ci-dessous pour une description +algorithmique plus précise.) Pour décider si un mot vérifie une expression rationnelle, on peut commencer par transformer cette expression rationnelle en NFA standard (i.e., construire un NFA standard reconnaissant le langage qu'elle -dénote) comme on vient de l'expliquer, et transformer ensuite cet -automate en DFA quitte déterminiser -(cf. \ref{determinization-of-nfa}), après quoi il est facile de tester -si l'automate accepte le mot. +dénote) comme on vient de l'expliquer, et déterminiser ensuite 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 mot +considéré. \end{proof} -\thingy\label{glushkov-construction} Les constructions que nous avons décrites dans cette section -associent naturellement un NFA standard à chaque expression -rationnelle : il s'obtient en partant des automates de base décrits -en \ref{trivial-standard-automata} et en appliquant les constructions -décrites dans les démonstrations de \ref{nfa-union}, -\ref{nfa-concatenation} et \ref{nfa-star}. Cette automate standard, -appelé \defin[Glushkov (construction d'automate de)]{automate de - Glushkov}, possède les propriétés suivantes : +\thingy\label{glushkov-construction} Les constructions que nous avons +décrites dans cette section associent naturellement un NFA standard à +chaque expression rationnelle : il s'obtient en partant des automates +de base décrits en \ref{trivial-standard-automata} et en appliquant +les constructions décrites dans les démonstrations de \ref{nfa-union}, +\ref{nfa-concatenation} et \ref{nfa-star}. + +Plus exactement, on associe à chaque expression rationnelle $r$ (sur +un alphabet $\Sigma$ fixé) un automate $A_r$ standard, appelé +\defin[Glushkov (construction d'automate de)]{automate de Glushkov}, +qui reconnaît le langage $L_r$ dénoté par $r$, de la manière suivante +(par induction sur la complexité de l'expression rationnelle telle que +définie en \ref{regular-expressions}) : +\begin{itemize} +\item les automates de Glushkov de $\bot$, $\underline{\varnothing}$ + et $x$ (pour $x\in\Sigma$) sont définis comme ceux décrits et + illustrés en \ref{trivial-standard-automata}, +\item connaissant les automates de Glushkov $A_1$ et $A_2$ de $r_1$ et + $r_2$ respectivement, celui de $(r_1|r_2)$ est celui décrit et + illustré dans la démonstration de \ref{nfa-union}, +\item connaissant les automates de Glushkov $A_1$ et $A_2$ de $r_1$ et + $r_2$ respectivement, celui de $r_1 r_2$ est celui décrit et + illustré dans la + démonstration de \ref{nfa-concatenation}, +\item connaissant l'automate de Glushkov $A$ de $r$, celui de $(r){*}$ + est celui décrit et illustré dans la démonstration + de \ref{nfa-star}. +\end{itemize} + +Cette automate de Glushkov $A_r$ possède les propriétés suivantes : \begin{itemize} \item c'est un NFA reconnaissant le langage $L_r$ dénoté par l'expression rationnelle $r$ dont on est parti, @@ -2764,7 +2835,7 @@ toutes celles aboutissant à l'état $2$ sont étiquetées $b$, et toutes celles aboutissant à $3$ sont étiquetées $c$. -\subsection{L'automate de Thompson (alternative à l'automate de Glushkov)} +\subsection{L'automate de Thompson (alternative à l'automate de Glushkov)}\label{subsection-thompson-construction} \thingy La construction de Glushkov (exposée en \ref{glushkov-construction}) d'un automate reconnaissant le langage @@ -2800,8 +2871,8 @@ automate de Thompson $A$ quelconque : \end{center} \thingy\label{trivial-thompson-automata} Les automates de Thompson des -langages de base triviaux $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ -(pour chaque $x\in\Sigma$) seront les suivants : +expressions rationnelles $\bot$, $\underline{\varepsilon}$ et $x$ +(pour $x\in\Sigma$) seront les suivants : \begin{center} \begin{tabular}{ll} @@ -2828,7 +2899,7 @@ rationnelle $\underline{\varepsilon}$), et\\ \thingy\label{thompson-union} Si $A_1$ et $A_2$ sont les automates de Thompson pour les expressions rationnelles $r_1$ et $r_2$, celui de -$r_1|r_2$ sera construit de la manière suivante : +$(r_1|r_2)$ sera construit de la manière suivante : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] \node (A) at (30bp,0bp) [draw,dotted,circle,minimum size=50bp] {$A_1$}; @@ -2884,7 +2955,7 @@ et \end{center} \thingy\label{thompson-star} Si $A$ est l'automate de Thompson pour -l'expression rationnelle $r$, celui de $r{*}$ sera construit de la +l'expression rationnelle $r$, celui de $(r){*}$ sera construit de la manière suivante : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] @@ -2999,7 +3070,7 @@ rationnelle conduit à l'automate de Glushkov de cette même expression. -\subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)} +\subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)}\label{subsection-rnfa-and-kleenes-algorithm} \thingy\label{definition-rnfa} Un \defin[automate fini à transitions étiquetées par des expressions rationnelles]{automate fini |