Information Technology Reference
In-Depth Information
E
E
A
+
T
B
T
a
∗
+
a
F
∗
b
Figure 4.29
The parse tree for the string
a ∗ b
+
a
in the language
L
(
G
6
)
.
⎡
⎤
∅∅∅∅∅{
}
∅∅∅∅∅ ∅
∅∅∅∅∅ ∅
∅∅∅∅∅ ∅
∅∅∅∅∅ ∅
∅∅∅∅∅ ∅
E
⎣
⎦
B
(
5
)
=
4.12 CFL Acceptance with Pushdown Automata*
While it is now clear that an algorithm exists to parse every context-free language, it is useful
to show that there is a class of automata that accepts exactly the context-free languages. These
are the nondeterministic pushdown automata (PDA) described in Section
4.8
.
We now establish the principal results of this section, namely, that the context-free lan-
guages are accepted by PDAs and that the languages accepted by PDAs are context-free. We
begin with the first result.
THEOREM
4.12.1
For each context-free grammar
G
there is a PDA
M
that accepts
L
(
G
)
.That
is,
L
(
M
)=
L
(
G
)
.
Proof
Before beginning this proof, we extend the definition of a PDA to allow it to push
strings onto the stack instead of just symbols. That is, we extend the stack alphabet
Γ
to
include a small set of strings. When a string such as
abcd
is pushed,
a
is pushed before
b
,
b
before
c
, etc. This does not increase the power of the PDA, because for each string we can
add unique states that
M
enters after pushing each symbol except the last. With the pushing
of the last symbol
M
enters the successor state specified in the transition being executed.
Let
G
=(
N
,
T
,
R
,
S
)
be a context-free grammar. We construct a PDA
M
=(Σ
,
Γ
,
Q
,
Δ
,
s
,
F
)
,where
Σ=
T
,
Γ=
N∪T∪{
γ
}
(
γ
is the blank stack symbol),
Q
=
{
s
,
p
,
f
}
,
F
=
{
f
}
,and
Δ
consists of transitions of the types shown below. Here
∀
denotes “for all”
and
∀
(
A
→
w
)
∈R
means for all transitions in
R
.
Search WWH ::
Custom Search