Information Technology Reference
In-Depth Information
3.2 Starting Point
We begin with
Safe
(
a
) with
a ∈ Σ
, for which we recall the definition.
:(
q,σ
)
ha
Γ
∗
|∀
Safe
(
a
)=
{C ⊆
Q
×
h
∈
H
Σ
,
∃
q
f
∈
Q
f
,
∃
(
q,σ
)
∈C
−→
(
q
f
,
)
}
(1)
3.3 Reading a Letter
a ∈ Σ
Suppose that we are reading an
a ∈ Σ
andwehavetocompute
Safe
(
ua
). Two
cases occur : either
ua
=[
t
0
], or
ua
=[
t
0
]. Let us study these two cases and
show how to manage them from an algorithmic point of view.
If
ua
=[
t
0
], we can retrieve safe sets configurations from prior computed
such sets:
Safe
(
ua
)=
Safe
(
u
)where
u
=
is the unique prefix of
u
such
that
u
=
u
a
[
h
], with
h
H
Σ
. Indeed as shown by Lemma 1 below, we have
Safe
(
u
a
[
h
]
a
)=
Safe
(
u
). Hence, from an algorithmic point of view, we just have
to use a stack
∈
to store these safe sets of configurations. When opening
a
,we
put
Safe
(
u
)onthestack,andwhenclosing
a
,wepopit.As
h
is a hedge, the
stack before reading
a
is exactly the stack after reading
a
.
S
Lemma 1.
If
h
∈
H
Σ
, then Safe
(
u
[
h
]) =
Safe
(
u
)
and LSafe
(
u
[
h
]) =
LSafe
(
u
)
.
If
ua
=[
t
0
], the previous argument is no longer correct since
u
=
and
Safe
(
u
) is not defined for the empty word. Nevertheless, by definition
Safe
(
ua
)=
{C ⊆
Γ
∗
|∃
Q
×
(
q,
)
∈ C
with
q
∈
Q
f
}
. Therefore we can again use stack
S
as
described before if it is initialized with the set
Γ
∗
|∃
Init
=
{C ⊆
Q
×
(
q
,
)
∈ C
with
q
∈
Q
f
}
.
(2)
3.4 Reading a Letter
a ∈ Σ
Let us now consider the much more involved case of sets
Safe
(
ua
) with
a
∈
Σ
.
When reading an
a
Σ
, two successive steps are performed, with leaf-safe sets
of configurations as intermediate object:
∈
Step 1
−−−−→
Step 2
−−−−→
Safe
(
u
)
LSafe
(
ua
)
Safe
(
ua
)
C
be two
For this purpose, we introduce the notion of
predecessor
.Let
C
,
sets of configurations, let
a
∈
Σ
and
h
∈
H
Σ
.
,
(
q,σ
)
a
C
if
(
q
,σ
)
∈ C
,
(
q
,σ
).
-
C
is an
a
-predecessor of
∀
∃
(
q,σ
)
∈ C
→
,
(
q,σ
)
[
h
]
C
if
(
q
,σ
)
∈ C
,
(
q
,σ
).
-
C
is a
h
-predecessor of
∀
∃
(
q,σ
)
∈ C
−−→
C
)=
C
}
C
)=
Let
Pred
a
(
{C | C
is an
a
-predecessor of
and
Pred
h
(
{C |
C
}
C
.
The next proposition can be used to perform Step 1 and Step 2. It states
that safe sets of configurations are only among predecessors of prior safe sets of
configurations.
is a
h
-predecessor of
