From f3be62b7d38da0fd991723ead8fb5fe31c2dcb85 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Wed, 8 Nov 2017 15:06:56 +0100
Subject: Change notation A_r to A(r) for consistency's sake.

---
 notes-inf105.tex | 37 ++++++++++++++++++++-----------------
 1 file changed, 20 insertions(+), 17 deletions(-)

(limited to 'notes-inf105.tex')

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
-- 
cgit v1.2.3

