Chapter 7: Pushdown Automata ~ 229
and 8 is given by
8(qo, a, Zo) = {(qo, aZD)}, 8(ql, b, a) = {(qj, A)}
8(qo, a, a) = {(qo, aa)}, D(q1' A, Zo) = {(q1, A)}
S(qo, b, a) = {(% A)}
Remarks 1. Seq, a, Z) is a finite subset of Q x i*. The elements of
8(q, a. Z) are of the form (q', a), where q' E Q. a E i*. 8(q, a, Z) may
be the empty set.
2. At any time the pda is in some state q and the PDS has some symbols
from r. The pda reads an input symbol a and the topmost symbol Z in PDS.
Using the transition function 8, the pda makes a transition to a state q' and
writes a string a after removing Z. The elements in PDS which were below
Z initially are not disturbed. Here (q', a) is one of the elements of the finite
set 8(q, a, Z). When a = A. the topmost symbol, Z. is erased.
3. The behaviour of a pda is nondeterministic as the transition is given
by any element of 8(q. a, Z).
4. As 8 is defined on Q x (I U {A}) x 1, the pda may make transition
without reading any input symbol (when 8(q, A, Z) is defined as a nonempty
set for q E Q and Z E l). Such transitions are called A-moves.
S. The pda cannot take a transition when PDS is empty (We can apply
8 only when the pda reads an input symbol and the topmost pushdown symbol
in PDS). In this case the pda halts.
6. When we write a =ZlZ: ... Zm in PDS, ZI is the topmost element,
Z2 is below ZI' etc. and Zm is belm\' Zm-l'
In the case of finite automaton, it is enough to specify the current state at
any time and the remaining input string to be processed. But as we have the
additional structure, namely the PDS in pda, we have to specify the current
state, the remaining input string to be processed, and the symbols in the PDS.
This leads us to the next definition.
Dermition 7.2 Let A = (Q, I, i, 8, qo. Zo, F) be a pda. An instantaneous
description (ill) is (q, x, a), where q E Q, x E I* and a E i"'.
For example, (q, ala: ... all' ZlZ2 ... Z/I,) is an ill. This describes the
pda when the current state is q, the input string to be processed is a1a2
an'
The pda will process ala: ... an in that order. The PDS has ZI- Z2'
, Zm
with Z1 at the top. Z: is the second element from the top. etc. and Z,n is the
lowest element in PDS.
Dermi~;,on 7.3 An initial ill is (qo, x. Zo). This means that initially the pda
is in the initial state qo. the input string to be processed is x. and the PDS has
only one symbol. namely Zoo
Note: In an ill (q. x, a). x may be A. In this case the pda makes a A-move.
and 8 is given by
8(qo, a, Zo) = {(qo, aZD)}, 8(ql, b, a) = {(qj, A)}
8(qo, a, a) = {(qo, aa)}, D(q1' A, Zo) = {(q1, A)}
S(qo, b, a) = {(% A)}
Remarks 1. Seq, a, Z) is a finite subset of Q x i*. The elements of
8(q, a. Z) are of the form (q', a), where q' E Q. a E i*. 8(q, a, Z) may
be the empty set.
2. At any time the pda is in some state q and the PDS has some symbols
from r. The pda reads an input symbol a and the topmost symbol Z in PDS.
Using the transition function 8, the pda makes a transition to a state q' and
writes a string a after removing Z. The elements in PDS which were below
Z initially are not disturbed. Here (q', a) is one of the elements of the finite
set 8(q, a, Z). When a = A. the topmost symbol, Z. is erased.
3. The behaviour of a pda is nondeterministic as the transition is given
by any element of 8(q. a, Z).
4. As 8 is defined on Q x (I U {A}) x 1, the pda may make transition
without reading any input symbol (when 8(q, A, Z) is defined as a nonempty
set for q E Q and Z E l). Such transitions are called A-moves.
S. The pda cannot take a transition when PDS is empty (We can apply
8 only when the pda reads an input symbol and the topmost pushdown symbol
in PDS). In this case the pda halts.
6. When we write a =ZlZ: ... Zm in PDS, ZI is the topmost element,
Z2 is below ZI' etc. and Zm is belm\' Zm-l'
In the case of finite automaton, it is enough to specify the current state at
any time and the remaining input string to be processed. But as we have the
additional structure, namely the PDS in pda, we have to specify the current
state, the remaining input string to be processed, and the symbols in the PDS.
This leads us to the next definition.
Dermition 7.2 Let A = (Q, I, i, 8, qo. Zo, F) be a pda. An instantaneous
description (ill) is (q, x, a), where q E Q, x E I* and a E i"'.
For example, (q, ala: ... all' ZlZ2 ... Z/I,) is an ill. This describes the
pda when the current state is q, the input string to be processed is a1a2
an'
The pda will process ala: ... an in that order. The PDS has ZI- Z2'
, Zm
with Z1 at the top. Z: is the second element from the top. etc. and Z,n is the
lowest element in PDS.
Dermi~;,on 7.3 An initial ill is (qo, x. Zo). This means that initially the pda
is in the initial state qo. the input string to be processed is x. and the PDS has
only one symbol. namely Zoo
Note: In an ill (q. x, a). x may be A. In this case the pda makes a A-move.