summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2021-04-21 15:22:27 +0200
committerDavid A. Madore <david+git@madore.org>2021-04-21 15:22:27 +0200
commitbe908cad24cb79279f96ca613b7d1caed9070b24 (patch)
treefa5a5205e0ef7ad78249258f7388e0ebda892ceb /notes-inf105.tex
parenta36b94055d0c1b5c61a4bdaf6689ad16adece645 (diff)
downloadinf105-be908cad24cb79279f96ca613b7d1caed9070b24.tar.gz
inf105-be908cad24cb79279f96ca613b7d1caed9070b24.tar.bz2
inf105-be908cad24cb79279f96ca613b7d1caed9070b24.zip
Fix definition of Glushkov automaton for concatenation (when initial state is final in second automaton).
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex11
1 files changed, 6 insertions, 5 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 5ecd95d..0979013 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2852,11 +2852,12 @@ et
De façon plus formelle, considérons un nouvel ensemble d'états $Q' =
(Q_1 \uplus Q_2) \setminus \{q_2\}$ où $\uplus$ désigne la réunion
disjointe. On définit alors l'automate $A'$ dont l'ensemble d'états
-est $Q'$, l'état initial est $q_1$, les états finaux $F' = F_2$, et la
-relation de transition $\delta$ est la réunion de $\delta_1$, de
-l'ensemble des triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$,
-et enfin de l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q')
-\in \delta_2$ et que $q\in F_1$.
+est $Q'$, l'état initial est $q_1$, l'ensemble $F'$ des états finaux
+est $F_2$ si $q_2$ n'était pas final dans $A_2$ et $F_1 \cup F_2$ si
+$q_2$ était final dans $A_2$, la relation de transition $\delta'$
+est la réunion de $\delta_1$, de l'ensemble des triplets $(q,x,q') \in
+\delta_2$ tels que $q\neq q_2$, et enfin de l'ensemble des triplets
+$(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