= = 12. Strings are formed using only the characters ( (left bracket) and ] (right bracket). The empty string is represented as l. If s and t represent strings, then st is the string formed by simple concatenation. For example, if s = = [l) and t =][ then st = [0][. Note, for all strings s, Is = sl = s. We say that s is an initial substring of S if there is a string t such that S = st. For example, the initial substrings of S =][[] are 1, ], ][, [[, III) and S itself. Recursively define the set B of "balanced bracketings as follows: (I) LE B. (IIa) If s E B, then [s] B. (IIb) If s,t in B, then st E B. (Strings in B can be generated only by use of these rules.) a) Show that [[|] E B. b) Write down two strings of 6 brackets that belong to B, different from the one in part a). c) Give an inductive proof (using whatever form of induction you wish) for the following: If b e B, then b contains an equal number of left and right brackets, and no initial substring of b contains more right brackets than left brackets. (If you're looking for something fun to do over the holiday break, try to prove the converse.) = = 12. Strings are formed using only the characters ( (left bracket) and ] (right bracket). The empty string is represented as l. If s and t represent strings, then st is the string formed by simple concatenation. For example, if s = = [l) and t =][ then st = [0][. Note, for all strings s, Is = sl = s. We say that s is an initial substring of S if there is a string t such that S = st. For example, the initial substrings of S =][[] are 1, ], ][, [[, III) and S itself. Recursively define the set B of "balanced bracketings as follows: (I) LE B. (IIa) If s E B, then [s] B. (IIb) If s,t in B, then st E B. (Strings in B can be generated only by use of these rules.) a) Show that [[|] E B. b) Write down two strings of 6 brackets that belong to B, different from the one in part a). c) Give an inductive proof (using whatever form of induction you wish) for the following: If b e B, then b contains an equal number of left and right brackets, and no initial substring of b contains more right brackets than left brackets. (If you're looking for something fun to do over the holiday break, try to prove the converse.)