David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 1

1a) 101^*01^*01^* | 10^*10^*10^*

1b) (([a-z]^+|[0-9]^+)[+-*/E])^*([a-z]^+|[0-9]^+|E))

1c) This language cannot be matched by a regular expression because
it requires either a stack or counting.  



David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 2


2a) The NFA will have an initial state that matches either a or b and
loops back onto itself and to the next state, which matches a2, then a
sequence of k states that match a or b, ending in a final state.

2b) The smallest number of states 2 + 2^k 


David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 3


3a) Yes, it's regular, matched by ((11|1001)^+(0)^*)^+

3b) The two base strings (11 and 1001) are both divisible by 3, and
when you append a 0 onto them, you double them, which is still
divisible by 3.  When you append either of those strings onto itself,
you either multiply it by a power of 2 and then adding something itself
divisible by 3, leaving the entire number divisible by 3.

3c) 33 (binary representation 100001)

<X> -> <X>0   |  <A>1
<A> -> <X>1   |  <B>0
<B> -> <A>0   |  <B>1

3d) ((1(01^*0)^*1)|0)^*



David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 4

4a) 
<exp> ==> <exp> + <exp>
      ==> <exp> + <exp> * <exp>
      ==> <exp> + <exp> * <exp> + <exp>
      ==> <id> + <exp> * <exp> + <exp>
      ==> <id> + <id> * <exp> + <exp>
      ==> <id> + <id> * <id> + <exp>
      ==> <id> + <id> * <id> + <id>

<exp> ==> <exp> * <exp>
      ==> <exp> * <exp> + <exp>
      ==> <exp> * <exp> + <id>
      ==> <exp> * <id> + <id>
      ==> <exp> + <exp> * <id> + <id>
      ==> <exp> + <id> * <id> + <id>
      ==> <id> + <id> * <id> + <id>

4b)

				 <exp>
				/  |  \
                            <exp>  +  <exp>
			    /	     /  |  \
	                  <id>   <exp>  *  <exp>
        		 	  /	  /  |  \
                                <id>  <exp>  +  <exp>
                                        |         |
				       <id>      <id>

				 <exp>
				/  |  \
                            <exp>  *  <exp>
			 /  |   |     |   | \
	              <exp> + <exp> <exp> + <exp>
        		|	|     |       |
                      <id>    <id>   <id>    <id>

4c)  <exp> -> <id> | <id> + <exp> | <id> * <exp>