Subject: Physics

1. Let G = (V, E, R, S) be a formal grammar such that all its rules are of the form a - B, where a E (VUE)+, BE (VUE )*. Construct a G as specified above such that L(G) = (a"b" c" | n 2 0}. Prove that L(G) = L(II), where II is a k-PDA, for k > 2. PART 2 1. Write a 6-page paper on "On Mapping Reducibility and Oracle Turing Machine," and