Answer Happy

Computer Theory. Need help with this outline.
1. Let G be the grammar. $85 (3) e L(G) is the language BP of all strings of balanced parentheses, that is, those strings that could appear in a well-formed arithmetic expression. We want to prove that L(G) - BP, which requires two inductive proofs: 1. If w is in L(G), then w is in BP. 2. If w is in BP, then w is in L(G). We shall bere prove only the first. You will see below a sequence of steps in the proof, each with a reason left out. The proof is an induction on the number of steps in the derivation of w. You must give a reason for each step. IN YOUR OWN CONCISE AND RELEVANT WORDS - as long as you write so, the reason at each step need not be more than one grammatically-correct sentence, or between one and three short grammatically-correct clauses. None of the reasons require elaborate explanations or the use of examples. As such. reasons that go on for many lines may be out of hand. NOTE: This problem appeared in the homework, where you were only required to classify the general reason. You must now write in the precise reason yourself. IF YOU DID THIS ON YOUR SCRAP WORK. I MAY ONLY HAVE COMMENTED ON THOSE STEPS THAT RELATED TO THE CHOICES PRESENTED. so do not take any lack of comments as indication that your work was correct. Basis: Oue step. (1) The only 1-step derivation of a terminal string is Se because (2) is in BP because Induction: An n-step derivation for some n>1. (3) The derivation Shw is either of the form (a) S (b) 8 because SS-n-1 w or of the form (S)-n-1 w Case (a): (4) w-xy, for some strings x and y such that S->Px and S->y, where p<u and q<a because (5) x is in BP because (6) y is in BP because (7) w is in BP because Case (b): (8) w-(z) for some string z such thar S-n-1 z because (9) z is in BP because (10) w is in BP because 2. La Ghet