3.1.7 Accepting Strings with NPDA (For mal Ver sion)
The nota tion “|–” is used to indi cate a sin gle move of an NPDA.
“|–
* ” is used to indicate a sequence of zero or more moves.
“|–
+ ” is used to indicate a sequence of one or more moves.
If M
Q
q
F
= ( , , , , , , )
Σ Γ
Ζ
δ 0
is an NPDA, then the language accepted by
M, L(M), is given by
L M
w
q w z
p u p F u
( ) {
: ( , , ) |– ( , , ),
,
}
*
*
*
= ∈
∈
∈
Σ
Γ
0
λ
.
Ì Exam ple 3.1.1: Construct a Push Down Automata (PDA) accepting
{
| ,
}
a b a m n
n m
n
≥1 by empty store.
Solu tion
The PDA which will accept
{
| ,
}
a b a m n
n m
n
≥1
is given below
PDA = ({ , }, { , }, { , }, , , , )
q q
a b a z
q z
0
1
0
0
0
δ
φ
where δ is given by
(1) δ ( , , )
{( ,
)}
q a z
q a z
0
0
0
0
=
(2) δ ( , , )
{( , )}
q a a
q aa
0
0
=
(3) δ ( , , )
{( , )}
q b a
q a
0
1
=
(4) δ ( , , )
{( , )}
q b a
q a
1
1
=
(5) δ
λ
( , , )
{( , )}
q a a
q
1
1
=
(6) δ
λ
λ
( , , )
{( , )}
q
z
q
1
0
1
=
Therefore we can see that we start storing a’s till b occurs ((1) and (2)). When
the current input symbol is b, the state changes, but no change in PDS occurs
((3)). Once all the b’s in the input string acts over ((4)), the remaining a’s are
erased ((5)).
Using (6), z 0 is erased.
Therefore we have
( ,
, ) | —— ( , , ) | —— ( , , )
*
q a b a z
q
z
q
n m
n
0
0
1
0
1
λ
λ λ
Therefore we see that a b a
N
n m
n
∈
(PDA).
Ì Exam ple 3.1.2: Construct a PDA accepting {
|
}
a b
n
n
n
2
1
≥ by empty
store.
164
Theory of Automata, Formal Languages and Computation