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.

Automata

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

• that all of the solution automata may be (will be, in the straightforward solutions) nondeterministic.

• that the answers I'm looking for have mathematical formulations, but there are also intuitive, handwavy ways to state the main idea. Think about the intuition behind the constructions and make sure that you state that in English.

• that it might help to think about how you would answer the question if I let you run the two machines. Be sure to tell me how you'd do this as it is the English -- hand-wavy -- answer to the question. Then see if you can build a machine that simulates running the two machines in the mode you just described.

• that the key to these problems is to figure out a rule that explains how you go from the transitions on each of the individual machines -- F₁ and F₂, e.g. -- to transitions on the new machine. Of course, you also have to figure out what the states of the new machine are.

• that the fourth problem -- the proof of non-context-free-ness -- is actually independent of the preceding ones. You should assume that #3 holds and try to answer #4 even if you can't make #3 work out. ("Using the previous proof" means using its result, not its construction.)

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

2. [warmup] For regular languages L₁ and L₂, explain how to construct a finite state automaton that recognizes L₁ intersection L₂, i.e., the language that includes all strings that are in both L₁ and in L₂. 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 aⁿbⁿcⁿ.

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.

• Traditional truth tables are written with the variables across the top and all possible combinations of truth assignments down the columns. A Karnaugh map is written using a different notation. A 2-variable Karnaugh map is written as a 2x2 table with one variable running across the top and the other down the side. The two truth values for the first variable are the columns; for the second, the rows; and the truth value of the function at that truth is written in the corresponding box. For example, the typical layout is:

  • 		q0
    		0	1
    q1	0
    	1

  and the Karnaugh maps for and, or, and Xor are: For AND:

  • q0 AND q1
    		q0
    		0	1
    q1	0	0	0
    	1	0	1

  For OR:

  • q0 OR q1
    		q0
    		0	1
    q1	0	0	1
    	1	1	1

  And for exclusive or (XOR):

  • q0 XOR q1
    		q0
    		0	1
    q1	0	0	1
    	1	1	0

  This idea can be generalized to three and four variables by arranging the pairs along the top and side in a nonstandard way:

  • 		q0q1
    		00	01	11	10
    q2q3	00
    	01
    	11
    	10

  Here, the first "bit" of each row or column corresponds to the first variable along that dimension -- q0 or q2 -- and the second to the second variable.

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!