xample and IIa MUI U is in the M I Usystem 594 Parenthesis S

xample and II(a), MUI U is in the M I U-system. 5.9.4 Parenthesis Structures Certain configurations of parentheses in algebraic expressions are \"legal\" such asto00 others are not such as)0) ando)(u. re is a recursive definition to generate the set P of legal configurations of parentheses. I. BASE: 0 is in P II. RECURSION: a. If E is in P, so is (E). b. If E and F are in P, so is EF. III. RESTRICTION: No configurations of parentheses are in P other than those derived from I and II above. Derive the fact that (O) is in P. Solution (1) By I, o is in P. (2) By (1) and II(a), (O) is in P. (3) By (2), (1), and II (b), (o) is in P .Douglas Hofstadter, Godel, Escher Bach (New York: Basic Books), pp. 33-35.

Solution

a) ()(())

Using I, i.e. Base case belongs to P, hence we can say that () belongs to P

Since base case belongs to P, then (base case) will also belong to P, which will be (()), using I and II

Since E and F belongs to P, that means EF means must also belong to P

Hence using the second E = () and F = (())

Therefore, EF or ()(()) belongs to P

b) (())(())

Using I, i.e. Base case belongs to P, hence we can say that () belongs to P

Since base case belongs to P, then (base case) will also belong to P, which will be (()), using I and II

Since E and F belongs to P, that means EF means must also belong to P

Hence using the second E = (()) and F = (())

EF will belong to P which will be (())(())