The language Balanced over = {(,)} is dened recursively as follows 1. Balanced. 2. x,y Balanced, both xy and (x) are elements of Balanced. A prex of a string x is a substring of x that occurs at the beginning of x. Prove by induction that a string x belongs to this language if and only if (iff) the statement B(x) is true. B(x): x contains equal numbers of left and right parentheses, and no prex of x contains more right than left. Reminder for this and all following assignments: if you need to prove the iff statement, i.e., X Y , you need to prove both directions, namely, given X, prove that Y follows from X (X = Y ), and given Y , prove that X follows from Y (X = Y ).