Reminder:  Assignments are due  by 11:59 p .m.  on the due date .

Please make sure to consult the guidelines for homework submissions posted here before you start writing up your homework. In addition, make sure to read the part of the syllabus that discusses the requirements of homework submissions to understand the factors that will impact on the grading. Remember that communicating your approach to the solution of a problem—e.g.  the key ideas underlying a proof or a construction—is as important as laying out the details, and sometimes may be more important. For this reason, you should typically begin your answer to each problem with a brief discussion of these key ideas before you go into the specific details. This is not a hard-and-fast rule—sometimes the essential idea may be so apparent as to not need any further explanation—but it is a yardstick for you to consider when writing your solutions.  Remember that this is a math

course and in assessing math work we must look at precision as well as clarity of thought. Problem 1 (8 + 8 points)

1.  Give an informal English description for a pushdown automaton that will accept the following language:

{w e {a, b}*  l w has twice as many bs as as}.

2.  Translate the informal English description into an actual pushdown automaton. In presenting this automaton, use a state diagram like that in Figure 2.15 in the textbook. In other words, do not try to write down a mathematical description in the form of a 6-tuple, this could be quite tedious and unnecessary for communication between humans.  However, make sure to follow the informal English description you have provided in the first part of this problem; how faithfully you have followed that description will be a criterion in grading.

Problem 2 (6 points)

Do Exercise 2.12 from the book.  Use the graphical state diagram notation discussed in the book and the class to present its transition function.  However, do not use the shorthand introduced in the proof of Lemma 2.21 for transitions. More specifically, limit the transitions you show to be of a form that writes at most one symbol onto the stack.

Problem 3 (6 +  6 points)

Suppose that L is a context-free language and that R is a regular language. Show then that

1.  L - R must be context free.  Note that  “minus” between sets represents set difference, i.e. L - R is the set of all strings in L that are not in R. In doing this part, assume the result in Problem 2.18 part (a) in the textbook.