Mathematical Foundation of Computer Science

(Chris Devlin) #1
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
Free download pdf