summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex37
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