Problem 5 Suppose G is a context-free grammar, is its set of terminals, and A is a variable in G. (a) Describe an algorithm that determines whether A** w for some w E *. (b) Argue that your algorithm is correct. Problem 6 Suppose you are given an NFA N with state set Q1 and a PDA P with state set Q2, describe how to construct a PDA P' with state set Q1 XQ2, so that L(P') = L(N)nL(P). Furthermore, give a non-trivial example of your construction. (Remarks: I'm not asking for an argument of correctness, just the construction. For full credit, you need to say something about how you allow one machine makes an e-transition while the other machine does nothing.) Problem 5 Suppose G is a context-free grammar, is its set of terminals, and A is a variable in G. (a) Describe an algorithm that determines whether A** w for some w E *. (b) Argue that your algorithm is correct. Problem 6 Suppose you are given an NFA N with state set Q1 and a PDA P with state set Q2, describe how to construct a PDA P' with state set Q1 XQ2, so that L(P') = L(N)nL(P). Furthermore, give a non-trivial example of your construction. (Remarks: I'm not asking for an argument of correctness, just the construction. For full credit, you need to say something about how you allow one machine makes an e-transition while the other machine does nothing.)