QUIZ 1 SOLUTIONS

1. 
	             	     a   b
		----------+-----------
		-> 0      | {1}  null
   		   {1}F   | null {1,2}
   		   {1,2}F | {1}  {1,2}

2. A = (0+1)* 11 (0+1)*
   This is exactly the set of strings that do contain the substring 11.
   The complement of this language is a language in which no word 
   contains the substring 11. Thus, there must be a 0 after each 1
   or the word must end there. One possible solution is

   ~A = 0* (100*)* (1 + [epsilon])



3.	
	a(a+b)*b + b(a+b)*a

4.


5.
(a) Let L be the given language. Then L intersect a*b* ={a^n b^n  |
    m>n>0} which is not regular as given in the hint. Since regular
    languages are closed under interestection, L cannot be regular.


(b) Let L=the given language. Define a homomorphism h from {a,b}* to {1}*
    by
		h(a)=h(b)=1

    Then h(L)={ 1^(n*n*) | n>=0 } which is not regular. Hence L is not
    regular.

(c) Let M be a DFA accepting a regular language L. Assume M has no 
    inaccessible states. Then from M get M' where the only change is
    that a non-final state q in M becomes a final state is M' if  
    there is a path from q to a final state in M.  L(M')=Prefix(L). 
    Hence Prefix(L) is regular.

(d) Let L=the given language. Define a homomorphism h from {a,b,c,d}* to
    {a,b}* by
		h(a)=a
		h(c)=b
		h(b)=h(d)=epsilon

    Then h(L)={a^n b^n | n>=0} which is not regular. Hence L is not regular.