diff options
| -rw-r--r-- | notes-inf105.tex | 37 |
1 files changed, 20 insertions, 17 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 21d4d82..dccd60d 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2974,7 +2974,7 @@ algorithmique plus précise. Pour décider si un mot $w$ vérifie une expression rationnelle $r$, on commence par transformer cette expression rationnelle en NFA comme on -vient de l'expliquer (c'est-à-dire à construire un NFA $A_r$ +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 @@ -2993,10 +2993,11 @@ les constructions décrites dans les démonstrations de \ref{nfa-union}, \medskip 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 +un alphabet $\Sigma$ fixé) un automate $A(r)$ (ou +$A_{\textrm{Glushkov}}(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}$ @@ -3016,7 +3017,8 @@ définie en \ref{regular-expressions}) : \smallskip -Cette automate de Glushkov $A_r$ possède les propriétés suivantes : +Cette automate de Glushkov $A_{\textrm{Glushkov}}(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, @@ -3161,8 +3163,9 @@ 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 Thompson} fournit un autre moyen d'associer à une expression -rationnelle $r$ un automate reconnaissant le langage qu'elle dénote. -Elle possède pour sa part les propriétés suivantes : +rationnelle $r$ un automate $A_{\textrm{Thompson}}(r)$ reconnaissant +le langage qu'elle dénote. Elle possède pour sa part 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, @@ -3503,10 +3506,10 @@ algorithmiquement de $A$. \begin{proof} On a vu en \ref{rational-languages-are-recognizable} que pour chaque expression rationnelle $r$ on peut trouver (algorithmiquement) un εNFA -$A_r$ (par exemple l'automate de Glushkov ou l'automate de Thompson) +$A(r)$ (par exemple l'automate de Glushkov ou l'automate de Thompson) qui reconnaît le langage dénoté par $r$. On peut donc construire $A'$ en remplaçant chaque transition $(q,r,q')$ de $A$ par une copie de -l'automate $A_r$ placée entre les états $q$ et $q'$. Symboliquement : +l'automate $A(r)$ placée entre les états $q$ et $q'$. Symboliquement : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)] @@ -3518,7 +3521,7 @@ l'automate $A_r$ placée entre les états $q$ et $q'$. Symboliquement : \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q1.base)] \node (q1) at (0bp,0bp) [draw,circle,state] {$q$}; \node (q2) at (100bp,0bp) [draw,circle,state] {$q'$}; -\node (A) at (50bp,0bp) [draw,dotted,circle] {$A_r$}; +\node (A) at (50bp,0bp) [draw,dotted,circle] {$A(r)$}; \draw [->] (q1) to node[auto] {$\varepsilon$} (A); \draw [->] (A) to node[auto] {$\varepsilon$} (q2); \end{tikzpicture} @@ -3527,21 +3530,21 @@ l'automate $A_r$ placée entre les états $q$ et $q'$. Symboliquement : Plus précisément, si $\{(q_j,r_j,q'_j) : 1\leq j\leq M\}$ est une énumération de $\delta$, on construit $A'$ en lui donnant pour ensemble d'états $Q \uplus \biguplus_{j=1}^M Q_{r_j}$ où $Q_{r_j}$ est -l'ensemble d'états de l'automate $A_{r_j}$ construit pour +l'ensemble d'états de l'automate $A(r_j)$ construit pour reconnaître $r_j$, les ensembles d'états initiaux et finaux sont $I'=I$ et $F'=F$ comme dans $A$, et la relation de transition $\delta'$ est la réunion de chacune $\delta_{r_j}$ de celle des -εNFA $A_{r_j}$ à quoi on ajoute encore des transitions spontanées +εNFA $A(r_j)$ à quoi on ajoute encore des transitions spontanées $(q_j,\varepsilon,q^\sharp)$ pour tout état initial $q^\sharp \in -I_{r_j}$ de $A_{r_j}$ et des transitions spontanées +I_{r_j}$ de $A(r_j)$ et des transitions spontanées $(q^\flat,\varepsilon,q'_j)$ pour tout état final $q^\flat \in -F_{r_j}$ de $A_{r_j}$. Il est clair que faire un chemin dans $A'$ +F_{r_j}$ de $A(r_j)$. Il est clair que faire un chemin dans $A'$ revient à un faire un chemin dans $A$ où, à chaque fois qu'on fait la transition $q_j\to q'_j$ étiquetée par $r_j$, on la remplace par un chemin $q_j \to q^\sharp \to \cdots \to q^\flat \to q'_j$ formé d'une -transition spontanée vers un état initial de $A_{r_j}$ suivi d'un +transition spontanée vers un état initial de $A(r_j)$ suivi d'un chemin dans ce dernier, suivi d'une transition spontanée depuis un -état final de $A_{r_j}$. +état final de $A(r_j)$. \end{proof} \medskip |