Problem 3 Convert the following grammar to Chomsky Normal Form (CNF), using the process described by Sipser. Show at least the following: (1) the grammar after you have fixed the start symbol and eliminated E-rules, (2) the grammar after you have also eliminated unit rules, and (3) the final CNF grammar. S aSA AB aB A abb B + bbA AA Problem 4 Consider the language F in Exercise 1.54 (page 91). First, argue that F is not regular. Second, find a winning strategy for R in the regular pumping game for F. (Remark: this shows the converse of Pumping Claim 1 is false.) 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 we S*. (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 Q XQ2, so that L(P') = L(N) L(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 3 Convert the following grammar to Chomsky Normal Form (CNF), using the process described by Sipser. Show at least the following: (1) the grammar after you have fixed the start symbol and eliminated E-rules, (2) the grammar after you have also eliminated unit rules, and (3) the final CNF grammar. S aSA AB aB A abb B + bbA AA Problem 4 Consider the language F in Exercise 1.54 (page 91). First, argue that F is not regular. Second, find a winning strategy for R in the regular pumping game for F. (Remark: this shows the converse of Pumping Claim 1 is false.) 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 we S*. (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 Q XQ2, so that L(P') = L(N) L(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.)