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 as 0)0 and0001, whereas others are not [such as)0) ando)((l. re is a recursive definition to generate the set P of legal configurations of parentheses I. BASE: O 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)0 is in P. Solution (1) By I, o is in P. (2) By and II(a), (0) is in P. (3) By (2), (1), and II(b), (0) is in P. .Douglas Hofstadter, Godel Escher Bach (New York: Basic Books), pp. 33-35.

Solution

13)

a) () (())

1) () is in P by I

2) (()) is in P by II) a

by 1 , 2 and II b

() (()) is in p

b) (()) (())

(()) is in p by I and II a

(()) (()) is in p by II b

I am not sure about 16

() is in by