CS154 Midterm Solutions

Question #1:

a) 0*11*222*


        0          1                     2
       /-\        /-\                   /-\
      |   |      |   |                 |   |
       \ /        \ /                   \ /
       +-+   1    +-+   2    +-+   2    +-+
-----> | | -----> | | -----> | | -----> |0|
       +-+        +-+        +-+        +-+
        |          |          |          |
        |          | 0        |          |
        | 2        |__        | 0,1      |
        |             |       |          | 0,1
        |             V       |          |
        |            +-+      |          |
        +----------> | | <----+          |
                     +-+ <---------------+
                     / \
                    |   | 0, 1, 2
                     \_/

c) There were many acceptable grammars. One is the following (e = epsilon)

   S -> A B C

   A -> 0A | e

   B -> 1B | 1

   C -> 2C | 22

Common errors with a included being careless with the regular expression (forgetting a 1, for example, and just having 01*222*). (1 or 2 points) The most common error for part b was not including the "dead" state at the bottom of the diagram. (2 points).

Question 2: Assume that the statement holds for n-1, and let w be of length n. There are two cases: w=xa or w=xb, where x represents the first n-1 positions of w. Consider first the case, that w=xa. If w has an even number of a's then x has an odd number of a's because (A) Thus, delta-hat(p,x)=q because (C). Therefore delta-hat(p,w)=p because (B). Now suppose w has an odd number of a's. Then x has an even number of a's, because (A). delta-hat(p,x)=p because (C). delta-hat(p,w)=q because (B). These statements complete the proof of the case w=xa.

Now consider the case w=xb. If w has an even number of a's then x has an even number of a's because (A) Thus, delta-hat(p,x)=p because (C). Therefore delta-hat(p,w)=p because (B). Now suppose w has an odd number of a's. Then x has an odd number of a's, because (A). delta-hat(p,x)=q because (C). delta-hat(p,w)=q because (B). These statements complete the proof of the case w=xb, and we are done with the inductive step.

Question 3: First, I should admit that the construction I had you go through is not the simplest one to prove that a\L is regular when L is. All you have to do is change the start state to delta(q_A,a). However, the requirements of the problem did force you to think about constructions, epsilon-transitions, and how automata work in general. I was pleased that so many people got the idea and essentially or completely got it right. However, there were a good number of people who failed to read carefully what the definition of a\L is, and interpreted it as something else, usually aL, i.e., as if L(B) were {aw | w is in L(A)}, rather than vice-versa.

(a) delta_B(q_B,epsilon) should be {delta_A(q_A,a)}; there are no other transitions out of q_B.

(b) delta_B(q,a) = {delta_A(q,a)} for all states q and input symbols a.

(d) Suppose ax is in L(A). Then B goes to delta_A(q_A,a) on epsilon and from there to whatever state delta-hat_A(q_A,ax) is on input x. That is, delta-hat_B(q_B,x)=delta-hat_A(q_A,ax). Thus, if A accepts ax, then B accepts x. Conversly, suppose B accepts x. Then it must be that B goes to q_A on epsilon, and from there to delta-hat_A(q_A,ax), which must be an accepting state. Thus, A accepts ax.

Question #4:

a) epsilon + b

b) epsilon + b + ab*a

c) b*ab*(ab*ab*)*

Grading Notes: The most common mistakes were forgetting that if you go around a self loop more than once, you're passing through the state numbered as high as that state. Another common mistake was forgetting epsilon when you're not changing states.

Question #5: An easy solution:

a) Choose w = 1^n 0^(n+1)

b) Choose i = 3

c) |xy| <= n, so it must consist of only 1s. Since y != e, it must contain at least one 1. xyyz thus contains at least one more 1s than xyz, and no more 0s; thus it has at least n+1 1s and n+1 0s, so it's not in L.

Any reasonable w, i, and explanation was accepted. Points were automatically taken off if one chose i = 1 - in this case the string is xyz, which we chose to be in L, so we can't show the same string is not in L.

Question #6:

a) S -> 0A -> 00AA -> 001SA -> 001A -> 0011S -> 0011

b) S -> 0A -> 00AA -> 00A0AA -> 00A0A1S -> 00A0A1 -> 00A01S1 -> 00A011 -> 001S011 -> 001011