Changes from the posted model solutions, for people who
took the conflict exam

Please see us if you can't figure out the grading of your
exam, from the normal model solution plus these notes.

================================================================
Problem 1
1 True
2 False
3 True
4. True
5. False
6. Broken due to typo, everyone got point
7. Broken due to typo, everyone got point
8. False
9. False

================================================================
Problem 2

(a) 
Let G_1= (V1, T1, S_1, P1)
Define G= (V1 union {S}, T1, S, P2)
where P2 is P1 union{S --> S S_1, S --> S_1}

Strings in L(G) are every possible sequence of strings in 
L(G_1), glued together, which basically shows that L(G)=L(G_1)^*.

(b) Each string in L(G) consists of some balanced parenthesized
strings of b (all b's inside at least one pair of parentheses), 
interleaved with some number of a's (all a's live outside the
parens).


(c) == problem (b) on regular exam


================================================================
Problem 3

Your solution will be very similar to that on the regular exam.

================================================================
Problem 4

Again, very similar to the regular exam.   However, the roles of
the two strings are reversed.   So your PDA needs to
non-deterministically throw out characters from y rather than
throwing out characters from x.   Or, alternatively, guess
extra characters for x rather than for y.

================================================================
Problem 5

The division between the two copies of w is marked by an a.   So
w should be a string of all b's when you create your string w_p.
E.g.
    w_p = b^pab^pa

================================================================
Problem 6

Your Turing machine stopped on the second character of the tape
(not on the first character as in the main exam).  Also, it
replaced non-initial a's by @ characters (the main exam version
used $ characters).

================================================================
Problem 7

Identical to the main exam.

Margaret