Consider the following rewriting process: you are given two strings (s, t) of the same length, say 000000 and 001001. You also have three rewriting rules: 000 → 111 (Rule 1) 01 → 10 (Rule 2) 101 → 000 (Rule 3) Can you transform s to t given these rules? In this case, the answer is yes, it can be done in seven steps: s = 000000 (Rule 1) 000111 (Rule 2) 001011 (Rule 3) 000001 (Rule 1) 011101 (Rule 2) 101101 (Rule 3) 000101 (Rule 2) t = 001001 You want to show that given strings s and t as input, the question whether s can be transformed into t using the three given rules can be solved in PSPACE. a) Show how the problem can be solved in NPSPACE, that is, by a non- deterministic machine. Sketch a high-level algorithm. b) Argue that the problem can be solved in PSPACE. Hint: use a) and name the appropriate result you use. c) What is the smallest k for which the problem lies in SPACE (nk)? Note: that's deterministic, not non-deterministic space.