Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 317

u vw xy

z

S

X

Y

A

A

Fig. 11.26
String w is the yield of sub tree rooted at lower A. v and x are the left and right sub
strings of w in the yield of the sub tree rooted at higher A and finally u and y are its left most
and right most substrings.

Since, A ⇒N w and A is reachable.

Hence, from Starting symbol S (active and reachable) we reach to A, or S* ⇒ α A β
where α and β are any arbitrary symbols.

Since, S ⇒N u A y where u and y are terminal strings (Fig. 11.27(a))

And A ⇒N v A x (Fig. 11.27(c)) and A ⇒N w (Fig. 11.27(b))

Then,

either S ⇒N u A y ⇒N u w y ∈ L (case for i = 0 shown in Fig. 11.27(d))

or S ⇒N u A y ⇒N u v A x y

⇒N u v v A x y

⇒N u vi w xi y is also in L (Fig. 11.27(e))

S

A

uywvx

A

A

A

(a)(b)(c)

Fig. 11.27