results is a multitude of grammar rules, one for each pair of states q x and q y in
the NPDA.
3.2.5 Deter min is tic Pushdown Autom ata
A Non-deterministic finite acceptor differs from a deterministic finite acceptor
in two ways:
(i) The transition function δ is single-valued for a DFA, but
multi-valued for an NFA.
(ii) An NFA may have λ-transitions.
A non-deterministic pushdown automaton differs from a pushdown
automaton in the following ways:
(i) The transition function δ is at most single-valued for a DPDA,
multi-valued for an NPDA.
Formally: | ( , , )|
,
δ q a b
1
0 1
= or for every q Q a
∈
∈ ∪
,
{ }
Σ
λ , and
b ∈Γ.
(ii) 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 ∈ Σ.
A deterministic CFL is a language that can be recognized by a DPDA. The
deterministic context-free languages are a proper subset of the context-free
languages.
3.3 PROPERTIES OF CONTEXT FREE LANGUAGES
3.3.1 Pumping Lemma for CFG
A “Pumping Lemma” is a theorem used to show that, if certain strings belong
to a language, then certain other strings must also belong to the language.
Let us discuss a Pumping Lemma for CFL.
We will show that , if L is a context-free language, then strings of L that are
at least ‘m’ symbols long can be “pumped” to produce additional strings in L.
The value of ‘m’ depends on the particular language.
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 wx y L
i
i
∈ .
for all non-negative values of i.
170
Theory of Automata, Formal Languages and Computation