Consider M on input (( ) ( )):
( , [ , (( ) ( ))], [ , ] |– ( , [ , (( ) ( ))], [ , ( ] )
|– (
q
q
q
M
M
0
0
0
1
1
2
1
λ
, [ , (( ) ( ))], [ , (( ] )
|– ( , [ , (( ) ( ))], [ , ( ] )
|– ( ,
3
1
4
1
0
0
M
M
q
q [ , (( ) ( ))], [ , ( ] )
|– ( , [ , (( ) ( ))], [ , (])
|– ( , [
5
1
6
1
7
0
0
M
M
q
q
, (( ) ( ))], [ , ])
|– ( , [ , (( ) ( ))], [ , ])
1
7
1
1
λ
λ
M
q
Therefore,
( [ , ( ( ) ( ) ], [ , ]) |– ( , [ , ( ( ) ( )], [ , ])
*
q
q
M
0
1
1
1
7
1
λ
λ
and since q 1 is an accepting state, all input has been read, and the stack is
empty, we have ( ( ) ( ) ) ( ).
∈L M
Let us consider M on the input string ( ) ). We get the following
computations.
( , [ , ( )], [ , ] |– ( , [ , ( ))], [ , ( ])
|– ( , [ , ( ))
q
q
q
M
M
0
0
0
1
1
2
1
3
λ
], [ , ] )
|– ( , [ , ( ))], [ , ] )
1
3
1
2
λ
λ
M
q
No further transitions of M can be applied, q 2 is not an accepting state, and
so ( ))
.
( )
∉ L
GLOSSARY
NDPDA: Non-deterministic Pushdown automata
PDA: Pushdown automata
Transition Function of NPDA: Are of the form
δ
λ
= × ∪
×
Q (
{ })
Σ
Γ
These are finite subsets of Q × Γ
∗ .
Pushdown Automata
179