[FrontPage] [TitleIndex] [WordIndex

This assignment is due on paper (one copy this time, but PLEASE use a stapler!) to Lynn at the beginning of class on Friday, 22 October. An automatic extension is granted until 4pm on Friday provided that you take responsibility for delivering the pset to AC312 (the pset may be placed under the door or in the collection bin outside). /!\ Also, electronic turn-in in addition is strongly encouraged; the paper copy is mandatory.

Don't forget to tell me with whom you collaborated (or that you didn't).

/!\ Some clarifications have been made, especially to the Grammars question. Hopefully I remembered to mark them all with a /!\

Grammars and Interpreters

Although this problem has a lot of little parts, it's not as bad as it looks. It would look much less initimidating if numbered 1 a b c, 2 a b c, and 3, but I couldn't get the wiki to do my bidding. Sigh.

  1. In class, we discussed a lisp syntax for a subset of scheme. Write a grammar that corresponds to the following fragments of scheme:
    • non-negative integers
    • alphabetic names
    • operations + - * / and predicates > < = <= >=

    • if expressions (the most common form only), e.g. (if a b c))

    • lambda expressions, e.g. (lambda (x) x)

    • define expressions (unsugared form only), e.g., (define x 3)

    • applications (i.e., applying an appropriate thing to an appropriate set of arguments) /!\ this one was originally intended but not made explicit. It's necessary for question 2. Sorry!!

    /!\ By "grammar" I mean the CFG (ideally including the regular expressions for terminals), but not the rules of evaluation. I should be able to tell from your answer whether a particular piece of lisp-like text is grammatical in this subset of lisp. I need not have any idea of how to evaluate it. Also note that scheme expressions like (/ 6 0) and (square 3 4 5) are grammatically correct even if they might have no reasonable meaning. You're only responsible for syntax -- structure -- and not for meaning.

  2. Write a factorial program in your subset of lisp.
  3. Draw a parse tree for your lisp factorial program according to your grammar. Use a representation in which all terminal symbols appear in the leaves of the parse tree; each interior node should be labeled with the head of the production that it (and its children) represent.
  4. Consider a simplified block-structured programming language in which the following statement types exist:
    • conditionals of the form if expr then stmt else stmt

    • loops of the form while expr do stmt

    • blocks of the form begin stmt* end

    • assignments of the form var := expr

    Expressions should include the same operations and predicates as in scheme; names should be alphabetic only; numbers should be non-negative integers. Write a grammar for this language.

    /!\ In response to questions I've been asked:

    • while is meant to say stmt, not stmt*. (Making the wrong assumption here is OK, but it's easier this way.)

    • I'd imagined operators to be infix, but any reasonable assumption is fine.

    • I'd imagined line breaks as separators, but again any reasonable assumption is fine.

  5. Write a factorial program in this language. Because this language does not include the definition of procedures, functions, or subroutines, you may assume that there is a variable n that contains the number to be factorial'd and that your result should wind up in a variable named ans.

  6. Draw a parse tree for your factorial program according to your grammar. Use a representation in which all terminal symbols appear in the leaves of the parse tree; each interior node should be labeled with the head of the production that it (and its children) represent.
  7. Observing the parse trees for your two programs, try to explain why lisp is generally viewed as an easier language for which to write an interpreter.


The first two problems in this section are optional but are intended as warmups for the third and fourth problems, which are required. If you are struggling at all with the later two, please do the first two first.

/!\ I will grade whatever is turned in; in particular, if you can do the warmups but not the later problems, PLEASE turn those in as they will certainly count for at least partial credit on the problem! Also note

  1. [warmup] Consider two regular languages, L1 and L2, each with a corresponding finite state automaton (F1 and F2, respectively). Explain how to construct a finite state state automaton that recognizes L1 union L2, i.e., the language that includes all strings that are either in L1 or in L2. Demonstrate this for the languages 0*1* and (01)*.

  2. [warmup] For regular languages L1 and L2, explain how to construct a finite state automaton that recognizes L1 intersection L2, i.e., the language that includes all strings that are in both L1 and in L2. Demonstrate this for the languages 0*1* and ((0U1)(0U1))*.

  3. Let C be a context free language and R be a regular language. Prove that the language C intersect R is context free (Sipser). Hint: Show how to construct a PDA that recognizes this language.

  4. Using the previous proof, show that the language A = { w | w in {a, b, c}* and contains an equal number of a's, b's, and c's} is not context free. (Sipser) Note that this language is not anbncn.

Karnaugh Maps

This question explores Karnaugh maps, an alternate representation for propositional formulae used in (old-fashioned) hardware design. It is supposed to be self-contained, but may not be enough for those with no prior exposure. Additional information may be found on the wikipedia page on Karnaugh maps, in the Computer Architecture textbook, or at any number of other web resources. If you use these resources, you must of course credit them in your solution.

Now the fun starts....

  1. Draw the Karnaugh maps for the following functions:
    1. Parity, i.e., the function (on four inputs) that is true if the number of true inputs is even
    2. (q0 v q1) ^ (q2 v q3)
    3. q0 -> ((q1 ^ q2) v q3)

  2. Populate a four-variable Karnaugh map with the formula made true by the truth assignment corresponding to that square. For example, if q0 is false, q1 is true, q2 is true, and q3 is false, the truth assignment might be written as as not(q0), q1, q2, not(q3) (but that renders extremely poorly on the wiki; you can use the overbar notation that makes it prettier!).
  3. There is an important observation to be made about the formulae in adjacent squares. What simple property can be stated about every pair of adjacent squares (two squares sharing a top, bottom, or side) in a Karnaugh map?
  4. (Hopefully) observe that this property holds for some non-adjacent squares as well. However, these squares can be made adjacent by wrapping the right edge of the Karnaugh map around to meet its left edge and, simultaneously, wrapping the top to meet the bottom. Explain.
  5. One can use a Karnaugh map to read off formulae for boolean operations in disjunctive normal form. For example, OR can be expressed as not(q0)q1 v q0 not(q1) v q0 q1 simply by reading the formulae corresponding to the squares with 1s. Using this simple-minded method, how many booleans would appear in the formula corresponding to a k variable Karnaugh map with n 1s? (Hint: for the 2-variable function OR, with 3 1s, the answer is 6.)

    /!\ Thanks, Kathy, for correction to this question (and the next one)!

  6. Fortunately, the formula for OR can be simplified by combining terms. (Shockingly enough, it reduces to q0 v q1) In a traditional Karnaugh map -- such as AND, OR, or XOR, above, but including the larger variants -- suppose that an m x n rectangular region contains exclusively 1s. (For example, in the Karnaugh map for OR, the second column is a 2x1 region of 1s and the second row is a 1x2 region of 1s.) What does this tell you about the formula corresponding to this Karnaugh map? In particular, if you have a k-variable Karnaugh map with an m x n rectangular region of 1s, how many variables would that region require to represent in disjunctive normal form under the naive method of the previous question? How many does it in fact require?

Logic fun

Because this assignment may be running long, I'm withholding the additional logic question. Don't worry....There will be plenty of opportunity to have fun with logic in class and over the next few weeks!

2013-07-17 10:43