(a) The transition function δ is at most single-valued for a DPDA,
multi-valued for an NPDA.
Formally: | ( , , )|
,
δ q a b
l
= 0 or
for every q Q a
∈
∈ ∪
,
{ },
Σ
λ and b ∈Γ.
(b) Both NPDA and DPDA may have λ-transitions, but a DPDA
may have a λ-transition only if no other transition is possible.
Formally: If δ λ
( , , )
q b ≠ ∅, then δ( , , )
q c b = ∅ for every c ∈ Σ.
19. State the Pumping Lemma for Context Free Grammars.
Let L be an infinite context-free language. Then there is some
positive integer ‘m’ such that, if S is a string of L of length at least ‘m’,
then
(i) S uvwxy
=
(for some u, v, w, x, y)
(ii) |
|
vwx m
≤
(iii) | |
vx ≥1
(iv) uv wiy L
i
∈ , for all non-negative values of i.
20. State one usage of a Pumping Lemma.
The Pumping Lemma can be used to show that certain languages are
not context free.
21. What is a decision algorithm?
The set of strings that is accepted by a finite automaton M which has
‘n’ state is
(a) non empty, if and only if M accepts some string of length less
than n.
(b) infinite, if and only if M accepts some string of length k where
n k
n
≤ ≤ 2 .
22. State the use of decision algorithm:
It is used to find out whether a finite automaton M accepts zero, a
finite number, or an infinite number of strings.
23. What are the ways to simplify a CFG to an NPDA?
(a) Empty Production Removal
(b) Unit Production Removal
(c) Left Recursion Removal.
24. How is a ‘move’ of an NPDA denoted?
|– denotes a move of NPDA.
Pushdown Automata
185