summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-28 09:40:57 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-11-28 09:40:57 (GMT)
commit10559224d661e323fb4fe10957583339a76ed98a (patch)
tree2e466f64db94ea23ed295350aad5b93c78cc4d7b
parent452c9e6d0d24325ed59658dd01820bf15365427d (diff)
downloadinf105-10559224d661e323fb4fe10957583339a76ed98a.zip
inf105-10559224d661e323fb4fe10957583339a76ed98a.tar.gz
inf105-10559224d661e323fb4fe10957583339a76ed98a.tar.bz2
Fix proof of standardization of automata.
The case where the added state should have been final was missing. Thanks to Antoine for pointing this out.
-rw-r--r--notes-inf105.tex9
1 files changed, 6 insertions, 3 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 68feda3..852c98a 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2606,13 +2606,16 @@ initial de $A$, on ajoute dans $A'$ une transition identiquement
étiquetée, et de même cible, partant de $q_0$.
Formellement : soit $A = (Q,I,F,\delta)$. On définit alors $A' =
-(Q',\{q_0\},F,\delta')$ de la manière suivante : $Q' = Q \uplus
+(Q',\{q_0\},F',\delta')$ de la manière suivante : $Q' = Q \uplus
\{q_0\}$ (où $\uplus$ désigne une réunion
disjointe\footnote{C'est-à-dire qu'on exige que $q_0$ n'appartienne
- pas à $Q$ (c'est un nouvel état).}), et $\delta'$ est la réunion de
+ pas à $Q$ (c'est un nouvel état).}), $\delta'$ est la réunion de
l'ensemble des transitions $(q,x,q')$ qui étaient déjà dans $\delta$
et de l'ensemble des $(q_0,x,q')$ telles qu'il existe une transition
-$(q,x,q') \in \delta$ avec $q\in I$.
+$(q,x,q') \in \delta$ avec $q\in I$, et enfin $F' = F$ ou $F' =
+F\cup\{q_0\}$ selon que $I\cap F = \varnothing$ ou $I\cap F \neq
+\varnothing$ respectivement (i.e., $q_0$ est final lorsqu'il existait
+déjà un état à la fois initial et final).
La figure suivante illustre la transformation en question :
\begin{center}