Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 325

Induction Hypothesis
Assume that fact is true for all ranks ≤ r – 1. Then examine, for node rank (A) = r. Since A
derived B and C so rank (B) or rank (C) ≤ r – 1. (Fig. 11.33).
From the derivation tree and by using the fact of CFL the length of the largest string
derived from B or C is ≤ 2 r–1.
A

r r

BC

£ 2 r–1 £ 2 r–1

Fig. 11.33

Thus, A derived a string of length = 2r – 1 + 2r – 1 or ≤ 2r. So we reach the fact hence it

is true for all ranks.

Since node rank (A) is finite and reachable (terminates to terminal string) so from starting

symbol S, rank (S) = r′ is a finite and the length of the largest string is no greater than 2r′ is

also finite.

DP2–Emptiness Problem

Given a CFG G, then emptiness problem says: Is L (G) = ∅ (empty)?

There is an inefficient way to examine the emptiness of the CFG G for the language

L(G). As we studied earlier under the topic of simplification of the grammar that, if the gram-

mar G has at least a nonterminal which is active and reachable, then it certainly derived a

terminal string and because it is reachable so the start symbol S generates the terminal string.

Then L(G) is non empty, i.e. L(G) ≠ ∅.

Conversely, L(G) is empty only if S generates no string of terminals. Or, G has none of

its nonterminals are active and reachable.

Even if ∈ is in L(G) then L(G) ≠ ∅.

DP3–Membership Problem

Let G be a CFG and x be any terminal string then: Does string x ∈ L(G)? or Is string x is the

member of L(G)?

There is an efficient way to solve membership problem through CYK algorithm that is

based on dynamic programming. The algorithm operated over CNF grammar G for the lan-

guage L(G).

There are few terms used in the algorithm such as,

xi,j = a substring of x starting from ith position in x and of length j.

Vi,j = (set of nonterminals) or {A ∈ VN | A ⇒N xi,j}

For example, let string x = abba and the grammar G is,

S → aB | bA

A → a | aS | bAA

B → b | bS | aBB