diff options
| -rw-r--r-- | notes-inf105.tex | 14 |
1 files changed, 12 insertions, 2 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index ae1f0e1..1c9646f 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1403,8 +1403,8 @@ langage accepté $L_A$ et l'équivalence de deux automates sont définis de façon analogue aux DFA (cf. \ref{definition-recognizable-language}). -\thingy Voici un exemple de εNFA particulièrement simple sur $\Sigma = -\{a,b,c\}$: +\thingy\label{discussion-example5} Voici un exemple de εNFA +particulièrement simple sur $\Sigma = \{a,b,c\}$: \begin{center} %%% begin example5 %%% @@ -1432,6 +1432,16 @@ nombre quelconque de $b$ suivi d'un nombre quelconque de $c$, ou, si on préfère, le langage désigné par l'expression rationnelle $a{*}b{*}c{*}$. +\thingy Si $q$ est un état d'un εNFA, on appelle +\textbf{$\varepsilon$-fermeture} de $q$ l'ensemble des états $q'$ (y +compris $q$ lui-même) accessibles depuis $q$ par une succession +quelconque de ε-transitions, c'est-à-dire, si on veut, $\{q'\in Q +:\penalty0 (q,\varepsilon,q') \in\delta^*\}$. On notera +temporairement $C(q)$ cet ensemble. (Par exemple, dans +l'exemple \ref{discussion-example5} ci-dessus, on a $C(0) = \{0,1,2\}$ +et $C(1) = \{1,2\}$ et $C(2) = \{2\}$. Dans tout NFA sans +ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.) + % % % |