A string w of left and right parentheses is balanced if w o

A string, w, of left and right parentheses is balanced, if w = or if there is some left parenthesis that can be matched to a right parenthesis on its immediate right, the two matching parentheses can then be removed to form w and then w is again balanced. If this removal process can be repeated until the string w is transformed into the empty string, then w is balanced. Show that if a string of parentheses is balanced then it is generated by the following grammar:

B BB| (B) |.

Solution

B->BB|(B)|epsilon

Input stringe\"((()))\" balanced

===>((B)) removing innermost parentheses
===>((epsilon))balanced
===>(B)
===>(epsilon)balanced
===>B
===>epsilon
Thus for every pair it is balanced

Derivation of input string\"((()))\"
B-->B
-->(B)
-->((B))
-->(((B)))
-->(((epsilon)))
-->((()))