Term Test 2   --- selected Solutions

2. LI: if answer=false then for all 0<= j < s, i^2 != n and if answer=true that n=(s-1)^2
P(i): If there are least i iterations, then 
          if answer_i = false then for all 0<=j<s_i j^2 != n and 
          if answer_i = true  then (S_i - 1)^=2=n

P(0): answer_0 = false and since there are no j such that 0<=j<s_0 = 0 and so the condition
      0<=j<s_i j^2 != n holds vacuously.
P(i)->P(i+1)
      If answer_{i+1}=flase this means that the condition on line 4 didn't hold, 
     so (s_{i+1}-1)^2 != n. Notice that s_{i+1}-1 = s_i so s_i^2!=n. Now by P(i)
     we can see that answwer_i must be false (as otherwise (s_i-1)^2=n which is 
     impossible as s_i^2<=n), and so we get that 0<=j<s_i, j^2 != n and 
     together with s_i^2 != n  we get       0<=j<s_{i+1} j^2 != n.

     Since at exit s_i^2>n, if the final variable answer is false we know that
     0<=j<s_i, j^2 != n and so n cannot have an integer square root.
     if the answer is true then we know that s_i-1 is the square root of n.

     termination: n-s_i^2 is a decreasing sequence of natural numbers (it ends
     the first time it becomes negative).
 



3. If L is finite and nonempty, then there is a srting s in L with maximum 
length, say m > 0. Since ss is in L o L, then there is a string in LoL 
which is of length 2m. But LoL is L, so this means that there is a string
in L which is of length 2m > m. That is  contradiction, and so if such
a finite nonempty language L exists, it must be that L={eps}.