. Let G = (V, Sigma, P, S) be a grammar that generates the set Bof all balanced

ID: 3617015 • Letter: #

Question

. Let G = (V, Sigma, P, S) be a grammar that generates the set Bof all balanced parenthesis nests using production rules of thefollowing form:

1) S --> (S)

2) S --> SS

3) S --> Lambda

Prove by induction on the lengthof a derivation that L(G) = B.

Hint: First you need to definewhat is meant by a balanced parenthesis nest. Here is one possibledefinition:

1) For all w = xy in B, thenumber of ( in x is always greater or equal to the number of ) inx

2) The number of ( in w equalsthe number of ) in w.

I know how to prove things with induction, but i've never seenanything worded like this and I have no idea what it means...

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.