Mathematical Foundation of Computer Science

DHARM

324 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

(∵ X 1 ⇒ X 2 B is the defined prodn. Here α 2 is A and β 2 is B so | a 2 b 2 | is 2)

and | αiβi | = i and so on.]

Hence, there exists a derivation sequence

X 0 ⇒α 1 X 1 β 1 ⇒α 2 X 1 β 2 ⇒ ......... ⇒αnXnβn ⇒αn+1X 0 βn+1

Or, X 0 ⇒N αn+1X 0 βn+1 and since each non terminal of CNF is active so it must generate

terminal string.

Let’s assume,

αn+1 (^) ⇒N v and βn+1 ⇒N x where v and x ∈ VT* and so the length | v. x | = (n +1)
Thus,

X 0 ⇒N v. X 0. x and also X 0 ⇒N w ∈ VT*

Since X 0 is useful so it is reachable from start state that is,

S ⇒N αX 0 β, we can find the terminal strings u and y s.t.

S ⇒N u. X 0. y

Then,

S ⇒N u. X 0. y ⇒N u. v. X 0. x. y

⇒N u. v. v. X 0. x. x. y

(for any number i ≥ 0) ⇒N u. vi. X 0. xi. y

Therefore, it has infinite many strings.

Case II

Suppose graph has no cycle. Define a new term rank of a node in the graph that is the length

of the longest path starting from node A.

Consider, A → BC and rank of B or rank (B) = r then,

rank (A) ≥ r + 1

Because, A derived B (and C) and length from A is one more than length from B

B

C

A

1

r

r+1

Fig. 11.32
From the Fig. 11.32 we will see that if graph has no cycle then rank of each node is
finite.
FACT
If rank of a node is r, then length of the largest string derived from this node will have length ≤
2 r.
Proof. Let us assume rank (r) of any node is 0. So, there is no possible path away from this
node. It means the production derived from this node is of the type A → a (assume grammar is
in CNF). Where, the derived string is of length 1. (Fact is true for base case).