summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-02-05 12:11:50 +0100
committerDavid A. Madore <david+git@madore.org>2017-02-05 12:38:44 +0100
commit6ce6940ea7e1c9d570f325f382f5deb6d47d2c51 (patch)
treea1a8339dd23818b5f8ccde89e87a6acee7cf382f
parente13d529b4268ed5e8f2b9776662aae507b440205 (diff)
downloadinf105-6ce6940ea7e1c9d570f325f382f5deb6d47d2c51.tar.gz
inf105-6ce6940ea7e1c9d570f325f382f5deb6d47d2c51.tar.bz2
inf105-6ce6940ea7e1c9d570f325f382f5deb6d47d2c51.zip
Fix mistake in elimination of states (thanks, Mathis Chagneux).
-rw-r--r--exercices3.tex12
1 files changed, 7 insertions, 5 deletions
diff --git a/exercices3.tex b/exercices3.tex
index 7ebae19..feff25d 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -338,12 +338,14 @@ vide, et l'expression rationnelle $\bot{*}$ est équivalente
lui aussi une transition vers lui-même (en passant par $1$) étiquetée
$aa$, qu'on peut fusionner avec la transition vers lui-même déjà
existante étiquetée par $b$ pour obtenir une transition étiquetée
-$b|aa$. L'élimination de l'état $2$ fait alors apparaître une
-transition de $0$ vers lui-même étiquetée $ba(b|aa){*}ab$, qu'on peut
-fusionner avec la transition vers lui-même déjà étiquetée par $a$ pour
-une seule étiquetée par $a|b(a(b|aa){*}a){*}b$. On obtient finalement
+$b|aa$ ; de même, l'état $0$ reçoit une transition étiquetée $bb$,
+qu'on peut fusionner avec celle existante pour obtenir $a|bb$.
+L'élimination de l'état $2$ fait alors apparaître une transition de
+$0$ vers lui-même étiquetée $ba(b|aa){*}ab$, qu'on peut fusionner avec
+la transition vers lui-même déjà étiquetée par $a|bb$ pour une seule
+étiquetée par $a|bb|ba(b|aa){*}ab$. On obtient finalement
\[
-(a|b(a(b|aa){*}a){*}b){*}
+(a|bb|ba(b|aa){*}ab){*}
\]
(en particulier, cette expression est équivalente à celle obtenue
précédemment).