CARLETON UNIVERSITY SCHOOL OF COMPUTER SCIENCE WINTER 2013 COMP. 3803 -DISCRETE STRUCTURES: II ASSIGNMENT IV DUE: APRIL 10, 2013 ___________________________________________________________________________________________________________________________________________________________________ Assignment Policy: Late assignments will not be accepted. You are expected to work on the assignments on your own. Past experience has shown conclusively that those who do not put adequate effort into the assignments do not learn the material and have a probability near 1 of doing poorly on the exams. Important note: When writing your solutions, you must follow the guidelines below. • Please write your name and student number clearly. Your last name must be in Upper Case. • The answers should be concise, clear and neat. Make sure that your TA can read your solutions. • Please submit the solutions in the order of the problems, the solution to Problem 1, then to Problem 2 and so on. • When presenting proofs, every step should be justified so as to get partial credit. • Assignments should be stapled (or in an unsealed envelope) with your name and student number. Substantial departures from the above guidelines will not be graded. 1. Prove, using the Pumping Lemma for CFL, that the following are not context free: • L = {aNb2NcMd2N | M,N = 0} • L = {a2NbNc3N | N = 0}. 2. Construct (deterministic or non-deterministic) pushdown automata that accept the following languages • L = { aMbN | M = N = 0}, where S = {a, b} • L = {aMb2NcN | M,N = 0}, where S = {a, b, c} • L = {wwR | w ? {0,1}*, and where wR is the reverse of w} In each case, please add some sentences explaining the rationale for the transitions. This will make the grading easier, in case your design is wrong. 3. Construct a one-tape Turing machine that accepts the language L = {a2NbN | N > 0 }. You have to give the informal description, describing the states you are going to use, their meaning, and what kind of transitions it…