Please do this and double check that your answer is correct.

4. ( 30pts,10pts each) Using the Grammar in Equation 1 SFF+SFAAFAab(S) (a) Show the left-most derivation for the expression b(a+b)+ab. (b) Show the parse tree for the expression b(a+b)+ab. (c) Give a NPDA which accepts the language described by this grammar. Hint: Modify the grammar, adding non-terminals where necessary, into a "pseudo normal form" such that every production is of one of the forms X,X, or X, for some X,, and . For example, the rule SF+S can be split into the two rules SFPP+S Then use this modified form of the grammar as a reference to construct your machine. 5. (10 pts) Give the formal 2 definition of the NPDA shown in Figure 2 Figure 2: A PDA accepting Strings of the form anbn where n0