Completely random selection of possible test questions

1.  Describe the DFA which is equivalent to the following NFA:

		INPUTS
     state     0        1
      q0      {q0,q2}  {q0,q1}
      q1      @        {q2}
      q2      {q1}     {q2}  where q2 is the final state.



2.  Construct an FA for the following regular expression:

	 (ab+a)*(aa+b)*


3.  Prove that the set of all strings with twice as many ones as zeros
    is not regular.



4.  If L1 is a regular set and L2 is a finite set, prove that their intersection 
    is regular.


5.  Assuming that L1, L2 are regular, prove that L1 - L2 is regular.


6.  Write a regular expression for the language which does not contain
    "101" as a substring.