summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-10-27 23:48:10 +0200
committerDavid A. Madore <david+git@madore.org>2017-10-27 23:48:10 +0200
commit185bae82bcf3ddd5f782edabd8a15f5c310e2257 (patch)
tree5fa1766f11ec86cad0f75aad050516b84bebb731
parent79e653484b265344c00af7e708c1b7c521e719d8 (diff)
downloadinf105-185bae82bcf3ddd5f782edabd8a15f5c310e2257.tar.gz
inf105-185bae82bcf3ddd5f782edabd8a15f5c310e2257.tar.bz2
inf105-185bae82bcf3ddd5f782edabd8a15f5c310e2257.zip
More remarks on Glushkov automata.
-rw-r--r--notes-inf105.tex23
1 files changed, 20 insertions, 3 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 6312c88..78191a4 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2618,7 +2618,7 @@ si l'automate accepte le mot.
\thingy 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 décrits
+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,
@@ -2628,12 +2628,29 @@ suivantes :
\item c'est un NFA reconnaissant le langage $L_r$ dénoté par
l'expression rationnelle $r$ dont on est parti,
\item il est standard au sens de \ref{standard-automaton-lemma},
- c'est-à-dire qu'il possède un unique état initial qui n'est la cible
- d'aucune transition,
+ c'est-à-dire qu'il possède un unique état initial auquel n'aboutit
+ aucune transition,
+\item les transitions aboutissant à n'importe quel état donné sont
+ toutes étiquetées par la même lettre,
\item son nombre d'états est égal à $1$ plus le nombre de lettres (à
l'exclusion des métacaractères) contenues dans l'expression $r$.
\end{itemize}
+Les deux dernières propriétés se vérifient inductivement, c'est-à-dire
+qu'on observe qu'elles sont satisfaites sur les automates de base
+décrits en \ref{trivial-standard-automata} qu'elles sont préservées
+par les constructions de \ref{nfa-union}, \ref{nfa-concatenation}
+et \ref{nfa-star}. En fait, on peut être un peu plus précis : chaque
+état, autre que l'état initial, de l'automate de Glushkov associé à
+l'expression rationnelle $r$ correspond à une lettre $x$ (à
+l'exclusion des métacaractères) de $r$, l'état en question provient de
+l'état $q_1$ de l'automate décrit en \ref{trivial-standard-automata}
+pour le langage $\{x\}$, et toutes les transitions menant à cet état
+sont étiquetées par $x$.
+
+Ces observations sont utiles pour détecter des erreurs lors de la
+construction de l'automate.
+
\textcolor{red}{TODO: Développer, et donner des exemples.}