5. Let L be the language of all strings of a's and b's such that no prefix (proper or not) has more b's than a's. Let G be the grammar with productions To prove that L L(G), we need to show two things 1. If S> 2.If w is in L, then S=>* w w, then w is in L We shall consider only the proof of (1) here. The proof is an induction on n the number of steps in the derivation Sw. Here is an outline of the proof with reasons omitted. You need to supply the reasons Basis: If n-1, then w is e because w is in L because 1) 2) Induction: 3) Either (a) S-as n-1 w or (b) S-aSbS w because In case (a), w - ax, and S x because_. In case (a), x is in L because In case (a), w is in L because In case (b), w can be written w aybz, where Sy and S 5a) 6a) 4b) z for 5b) 6b) 7b) some p and q less than n because In case (b), y is in L because In case (b), z is in L because In case (b). w is in L because- . For which of the steps above the appropriate reason is contained in the following argument "The following two statements are true (i) if string x has no prefix with more b's than a's, then neither does string ax, (ii) if strings y and z are such that no prefix has more b's than a's, then neither does string aybz." b) 1 d) 4b