a) 0*11*222*

b)

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*.

(c)
*F_B=F_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

c)

S / \ 1 B / \ 0 S / \ 0 A / \ 1 S | epsilon