In this short note I will try to demonstrate, through examples, the type of expectation I have 
with respect to proof that a certain FSA accepts a certain language. Notice that Daniela has 
shown is a proof of this sort as well, in her Nov 28 tutorial.

* Consider the maching for L1 from lecture 11. L1 = {x in {0,1}* : |x| is even }
The machinewe gave had two states
    M1 has two states, q0, q1. The transition is that whatever character read by M1 it changes state. 
    Further, F = {q0}. 
    We prove that delta*(q0,x) = q0 if |x| is even and delta*(q0,x) = q1 if |x| is odd.
    Notice that this is obviously true for the empty string (owhich is of even length, and delta*(q0,epsilom) = q0.
    Also, when we add a character, the lenghtof the string changes from odd to even and vice versa. But this is
    also the case for M1 whcih at every character changes state. Hence the claim above (state invariant holds).
    Now, sice q0 is in F and q1 is not in F, the state at which the FSA will be is in F precisely when the input is
    of even length, or in other words, precisely when the input string is in L1.

To prove that indeed, L(M1) = L1, we show inductively on strings that
    delta*(q0,x) = q0 if |x| is even and q1 if |x| is odd. Showing this is easy, and this implies
    what we want, because it shows that the terminal state is q0 if x is in L and q1 if not, and 
    since F = {q0} we get L(M1)= L1.

* consider this (new) example. This time I will describe the language using a regular expression L = L( 0*1*).
  In words, L is th elanguage of strings that start with a certain number of zeros (perhaps none) and end with 
  a certain number of 1s (perhaps none).
  The machine will have states q0, q1 q2. 
     - from q0 we move to q0 if we read a 0 and to q1 if we read a 1.
     - from q1 we move to q2 if we read a 0 and to q1 if we read a 1.
     - from q2 we move to q2 whatever the character is.
    F = {q0,q1}.

  To prove that L(M) = L  we give "meaning" to the states. 
  q0 represents reading a string with only zeros (perhaps none). Call this type 1 string.
  q1 represents reading a string with zeros followed by a positive number of ones. Call this type 2 string. 
  q2 represents reading a string that have zeros after ones. Call this type 3 string.

  Let's show the above meanings. 
  Notice that the above three types of strings cover the whole set of strings and are exclucive. In other words, 
  every string is precisely one of the above types of strings.
  The empty string corresponds to type 1 and of course after reading it the machine is at state q0.
  Consider a string xa. 

  If x is of type 1 then delta*(q0,x) = q0 (inductively). Now if a is zero we stay at q0 and indeed xa is of type 1.  If a is 1 then we move to q1 and indeed xa is of type 2.

  If x is of type 2 then delta*(q0,x) = q1. If a is 0 then xa is of type 3 and the machine moves to q2. If
  If a is 1 then xa is of type 2 and the machine stays at q1.

  If x is of type 3 then delta*(q0,x) = q2. No matter what a is xa is also of type 3. Also, from q2 the machine
  must stay in q2.

  We have shown that delta*(q0,xa) is consistent with the description of the meaning of the states above.

  To complete the proof, notice that types 1 and 2 are in L while type 3 is not, hence since F= {q0,q1} we are done.