summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-23 18:13:12 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-11-23 18:13:12 (GMT)
commite6fbe5a42f043dccd603de0509bcd5391f1aecf7 (patch)
treee64c0bec54cf70e6d3ae35d2ab35e4728e265906 /notes-inf105.tex
parent36ba46eccdbe995358d11a0febaed52e6c035b17 (diff)
downloadinf105-e6fbe5a42f043dccd603de0509bcd5391f1aecf7.zip
inf105-e6fbe5a42f043dccd603de0509bcd5391f1aecf7.tar.gz
inf105-e6fbe5a42f043dccd603de0509bcd5391f1aecf7.tar.bz2
Define ε-closure.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex14
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$.)
+
%
%
%