Many of the questions on this final have been worked in class or as homework problems. Here are solutions for the others.

3.  S->A1A1A1
     A->0A|1A|epsilon

5. Here is a decider for the language.

TM S on input w:
1. Mark the leftmost 1. If there are no unmarked 1's, check whether there are unmarked 0's - if so, accept; otherwise, reject.
2. Mark leftmost 0. If there are no unmarked 0's, accept.
3. Mark leftmost 0. If there are no unmarked 0's, accept. Otherwise goto step 1.

7. a) The language is regular.

Regular expression: 00^+10^* union 100^+ union 010^+