From be908cad24cb79279f96ca613b7d1caed9070b24 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 21 Apr 2021 15:22:27 +0200 Subject: Fix definition of Glushkov automaton for concatenation (when initial state is final in second automaton). --- notes-inf105.tex | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'notes-inf105.tex') 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 -- cgit v1.2.3