Information Technology Reference
In-Depth Information
that we assume big operators to have lower precedence than small ones, thus
a
b
=
(
a
b
).
Visibly Push-Down Automata.
A (non-deterministic)
push-down automaton
is a
tuple
=(
Q,Σ,Γ,δ,Q
0
,F
)where
-
Σ,Γ
are the finite
input
and
stack alphabet
, respectively, and
Γ
#
:=
Γ
˙
F
∪{
#
}
the stack alphabet enriched by a new bottom symbol #
∈
Γ
,
-
Q
is a finite set of control
states
,
-
Q
0
⊆
Q
is the set of
initial states
,
-
F
⊆
Q
is the set of
accepting states
and
2
Q×Γ
≤
#
is the non-deterministic,
transition function
.
-
δ
:
Q
×
Γ
#
×
Σ
→
(
Γ
∗
{
) comprising the current
control state and a stack assignment ending with #. A
run
of
A
configuration
of
F
is a tuple (
q,s
)
∈
Q
×
#
}
F
on a
finite
Σ
∗
is a sequence
c
0
c
1
...c
n
+1
of configurations
input word
w
=
w
0
w
1
...w
n
∈
(
Γ
∗
{
c
i
∈
Q
×
#
}
) s.t.
-
c
0
∈
and
-
if
c
i
+1
=(
q
,γ
γ
s
)then
c
i
=(
q,γs
)with(
q
,γ
γ
)
Q
0
×{
#
}
∈
δ
(
q,γ,w
i
),
where
q
∈
Q
,
γ
∈
Γ
#
.Arun(
q
0
,s
0
)(
q
1
,s
1
)
...
(
q
n
+1
,s
n
+1
) is accepting if
q
n
+1
∈
F
.
P
reading
infinite
words a
push-down
ω
-
We call a push-down automaton
Σ
ω
is an infinite
sequence of configurations
c
0
c
1
...
defined as above. A run (
q
0
,s
0
)(
q
1
,s
1
)
...
is
accepting if the sequence of states
q
0
q
1
...
satisfies a Buchi condition, i.e. there
is some
q
P
on an infinite word
u
=
u
0
u
1
...
∈
automaton
.Arunof
F
that occurs infinitely often in the sequence.
A push-down (
ω
-)automaton accepts a word
w
∈
Σ
∞
if there is an accepting
∈
Σ
ω
and
Σ
∗
we denote the set of words accepted
run on
w
.By
L
(
P
)
⊆
L
(
F
)
⊆
by
P
and
F
, respectively.
are called a
visibly push-down automaton
(Vpa)anda
visibly push-
down
ω
-automaton
(
ω
-Vpa), respectively, if the input alphabet
Σ
is the union
of three disjoint alphabets
Σ
c
,
Σ
r
,
Σ
int
and for (
q
,u
)
F
and
P
∈
δ
(
q,γ,a
)
-
u
=
iff
a
∈
Σ
r
and
γ
=#,
-
u
=#iff
a
∈
Σ
r
and
γ
=#,
-
u
=
γ
iff
a
∈
Σ
int
and
-
u
∈
(
Γ
{
γ
}
)iff
a
∈
Σ
c
.
Emptiness of Push-Down Automata.
Let
=(
Q,Σ,Γ,δ
P
,Q
0
,F
) be a push-
down
ω
-automaton. Following [19], we can represent the set configurations of
P
,
from which all inputs are rejected (empty configurations), by means of a
multi
automaton
P
=(
S
˙
Q,Γ,δ,Q,A
).
S
˙
A
∪
∪
Q
is the
state space
where
S
is a finite set
and disjoint from the states
Q
of
P
, which are the
initial
states of
A
.Thestack
alphabet
Γ
of
P
is the
input alphabet
of
A
and
A
⊆
S
are the
accepting states
.
2
S ∪Q
is the
transition function
. The multi-automaton
δ
:
S
˙
∪
Q
×
Γ
→
A
accepts
configurations (
q,s
#) of
by behaving like a finite automaton with initial state
q
and reading the stack configuration
s
P
Γ
∗
as input.
∈
Note, that in [19] the state space of
A
and
P
are disjoint but each initial state
s
of
A
corresponds (bijectively) to some
q
∈
Q
. We therefore identify those.
