summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2021-04-21 15:36:52 +0200
committerDavid A. Madore <david+git@madore.org>2021-04-21 15:36:52 +0200
commitd8e4b3111009e9415b70fc48ae30a506ce6287c4 (patch)
treef0ad5b3ca34f2cf11614a4918f77848617a31adb /notes-inf105.tex
parent3202b591afd18dde07c391941f2f13ad38e83f03 (diff)
downloadinf105-d8e4b3111009e9415b70fc48ae30a506ce6287c4.tar.gz
inf105-d8e4b3111009e9415b70fc48ae30a506ce6287c4.tar.bz2
inf105-d8e4b3111009e9415b70fc48ae30a506ce6287c4.zip
Clarification of clarification.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex23
1 files changed, 12 insertions, 11 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 2131cb3..67a0a9b 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2757,11 +2757,11 @@ $(\varphi_2(q),x,q')$ où $(q,x,q') \in \delta_2$.
(\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en
ajoutant d'abord un unique état initial $q'_0$ à la réunion disjointe
-de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$,
-puis en éliminant les ε-transitions qu'on vient d'ajouter
-(cf. \ref{removal-of-epsilon-transitions}) ainsi que les états $q_1$
-et $q_2$ devenus inutiles. Cela donne le même résultat que ce qui
-vient d'être dit.)
+de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$
+(qui cessent d'être initiaux), puis en éliminant les ε-transitions
+qu'on vient d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi
+que les états $q_1$ et $q_2$ devenus inutiles. Cela donne le même
+résultat que ce qui vient d'être dit.)
Il est alors clair qu'un chemin de l'état initial à un état final dans
cet automate $A'$ consiste soit en un chemin d'un état initial à un
@@ -2788,7 +2788,8 @@ L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant
que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant
chaque transition sortant de $q_2$ par une transition identiquement
étiquetée, et de même cible, partant de \emph{chaque} état final
-de $A_1$. Graphiquement :
+de $A_1$ (ces derniers seront marqués finaux si $q_2$ était final
+dans $A_2$). Graphiquement :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
@@ -2861,11 +2862,11 @@ $(q,x,q')$ tels que $(q_2,x,q') \in \delta_2$ et que $q\in F_1$.
(\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en
ajoutant d'abord à la réunion disjointe de $A_1$ et $A_2$ une
-ε-transition de chaque état final de $A_1$ vers $q_2$, puis en
-éliminant les ε-transitions qu'on vient d'ajouter
-(cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état $q_2$
-devenu inutile. Cela donne le même résultat que ce qui vient d'être
-dit.)
+ε-transition de chaque état final de $A_1$ vers $q_2$ (qui cesse
+d'être initial), puis en éliminant les ε-transitions qu'on vient
+d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état
+$q_2$ devenu inutile. Cela donne le même résultat que ce qui vient
+d'être dit.)
Il est alors clair qu'un chemin de l'état initial $q_1$ à un état
final dans cet automate $A'$ consiste en un chemin de $q_1$ à un état