where Q = Finite set of inter nal states of the con trol unit
Σ = input alpha bet
Γ = Finite set of sym bols called ‘stack alpha bet’.
δ
λ
:
(
{ })
Q × ∪
× →
Σ
Γ Finite sub sets of Q × Γ
* is the tran si tion func tion.
q 0 = Ini tial state of the con trol unit ∈Q
Z = Stack start sym bol
F Q
⊆ →Set of Final states.
3. What is the data structure used in a Push Down Automaton?
Stack is the data structure used in a PDA.
4. What is the general form of a transition function of an NPDA?
δ
λ
:
(
{ })
Q × ∪
× →
Σ
Γ
Finite subsets of Q × Γ
* . where δ has now
three arguments:
(a) the state
(b) either λ, or a symbol from the input alphabet.
(c) symbol on the top of the stack.
5. State the requirements for execution of an NPDA.
(a) The state of the DFA is in
(b) What the remaining input is.
6. Given an instantaneous description of a PDA.
The instantaneous description of a PDA is a triplet (q, w, u), where
q = cur rent state of the autom a ton
w = unreal part of the input string
u = stack con tents (writ ten as a string, with the leftmost
sym bol at the top of the stack).
7. What are the types of moves that are made while accepting strings with
an NPDA?
(a) λ-transition.
(b) Non-empty transition.
8. What do you mean by a λ-transition in PDA?
If you are in a state q 1 , x is the top (leftmost) symbol in the stack, and
δ
λ
( ; , ) {( , ), }
q
x
q w
1
2
2
=
K
then you can replace the symbol x with the string w 2 and move to q 2 .
9. What are non-empty transitions in an NPDA?
If you are in the state q 1 , ‘a’ is the next unconsumed input symbol, x
is the top (leftmost) symbol in the stack, and
δ( , , ) {( , ), }
q a x
q w
1
2
2
=
K
then you can remove the ‘a’ from the input string, replace the
symbol x with the string w 2 , and move to the state q 2 .
Pushdown Automata
183