diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 9 |
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} |