diff options
| -rw-r--r-- | notes-inf105.tex | 23 |
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.} |