Misinterpreted a multiple of 4 ones to mean a string containing n amount of 1111 where n is an natural number... Completed proof and then started thinking: this seems kind of stupid since we might as well of said a string containing 1111... I decided to check Piazza and someone had it clarified already. Time to rewrite the question -_-;

Oh my Assignment 3; When the general idea behind the solutions don't come to your head within the first few readings of each question, you know it'll take a while :(

Thankfully I had time to finish question 1! And it's not even the day it's due, personal record j/k lol;

DFSAs are pretty cool 'machines' xD So simple yet so complex. Though I wish there were more slides or parts to the textbook on DFSA/NFSAs; A lot of reading online had to be done for a more in-depth understanding.

Continuing the Problem:

To recap:
The strings are now broken into three sections:
The first bit, the inner bits, and the last bit.

Now in order to do this breakup, the length of the string must be at least 3. This gives us a general indication of what base cases we need (so far 0, 1 and 2).

Now given that the string is broken into three pieces, we can consider the relationship between the first bit and the inner bits, and the last bit and the inner bits. What's nice is we know that the first and last bits are the same. If the first bit is 0, so is the last bit, and if the first bit is 1, so is the last bit. Now consider the inner bits. These bits also form a string which we can apply our predicate to.

There are two cases:
a) The inner string has the same first and last bit.
b) The inner string has different first and last bits.

For a) we can apply our predicate. We know that the inner string has 0 or 1 as the first and last bit and also that the inner string has an even number of occurrences of substrings from {01, 10}. If we look at the inner string, we can represent it as follows. 0 - stuff - 0 or 1 - stuff - 1 In order to break it up like this, the length of the string must be at least 4. Therefore our base cases are now: 0, 1, 2 and 3.
Putting the inner string together with the outer bits we have:
(00 - stuff - 00) or (10 - stuff - 01) or (01 - stuff - 10) or (11 - stuff - 11)
Clearly, the number of occurrences of substrings from {01, 10} remains even. We either have even  number + 0 or even number + 2.

For b) we must look for a way to represent the string such that we can apply our predicate to the inner string. The inner string is now either 1 - stuff - 0 or 0 - stuff - 1. Appending the outer bits we have:
(01 - stuff - 00) or (11 - stuff 01) or (00 - stuff - 10) or (10 - stuff - 11)
The trick here is to consider the string as two parts:
ie. for the first string of (01 - stuff - 00)
Look at it like (01 - stuff - 0) + 0
From this representation, we see that there is an inner string with the same first and last bits (0) appended with a 0 to one end. From our predicate and the assumptions in Complete Induction, the inner bit has an even number of occurrences of substrings from {01, 10} and the appending of 0 to the end (which is also a 0) causes no change in the number of occurrences, thus the number remains even.

This representation can be applied to the four cases for part b).

From here you just have to write the proof out formally (including the base cases) and voila. you're done.

Continuing the Problem:

For complete induction.

P(n) : Binary string of length n beginning and ending with the same bit has an even number of occurrences of substrings from {01, 10}

If P(a), P(a+1), ... , P(n-1) implies P(n) then for all n in N greater than or equal to a, P(n).

a is a natural number and represents the step after the base case or cases. As of now, a is unknown but when we continue the solution, we will figure it out.

So, next is to reconsider the question in terms of the type of proof. We are allowed to assume P(x) for x less than n, which lends itself to the idea of building the string from the concatenation of smaller strings. This is because adding bits to a string will only increase or leave the same, the number of occurrences of {01, 10}. It will never decrease the number of occurrences. So in an attempt to search for the method of building the string, I listed out the set of strings that satisfy P(n) for n in {0-4}.

0 : {}

1 : {0, 1}

2 : {00. 11}

3 : {000, 010, 111, 101}

4 : {0000, 0100, 0010, 0110, 1001, 1101, 1011, 1111}

So the general idea is to split the string into sections. As a hint, we were told to combine this claim with a similar claim about binary strings that begin and end with different bits. Intuitively, it would seem that a binary string beginning and ending with different bits would have an odd number of occurrences.

Following the hint, I decided to break the string into three sections.

Eg. for 0000 : n = 4

0 - 00 - 0

Section 1 : First bit

Section 2 : Inner bits

Section 3 : Last bit

Now using complete induction, I know that since the inner bits is of length less than n, the inner bits will satisfy P(x); which is nice, but not explicitly useful until we consider the construction of the inner bit as well.

Well the first step to answering any question is to read it (something I seem to forget quite often on tests :\) so here it is:

Question 4:

Use Complete Induction or Mathematical Induction to prove that any binary string that begins and ends with the same bit has an even number of occurrences of substrings from $\{01,10\}$, e.g. $010$ has two: $01$ and $10$.  You may find it useful to combine this claim with a similar claim about binary strings that begin and end with different bits, and then prove the combined claims simultaneously.

The second step is to begin gathering important information on the topic. First thing I did was write down the binary strings for a number of lengths. From this it is always a good idea to make a guess as to whether or not the claim is false.

Length : Strings

0 : {}

1 : {0, 1}

2 : {00, 11}

3 : {000, 010, 111, 101}

So far it seems that the claim holds. Now the next question is why it would hold. Seeing as we are to use either Complete or Mathematical Induction, I chose to assume Complete Induction (as it assumes more than Mathematical) in order to approach the question.

So after reading the solutions to assignment 1 (I was bored and decided to see how they looked) I've realized that my solution style is completely different to the sample. So as a sample on other methods of presenting proofs: I link my solution! Which I think looks beautiful of course :)

https://docs.google.com/open?id=0BwY_GV-lFUUzamJoSnlDYXNYMmM

As a note I did not receive full marks. The error was in question 1 -_-; If you look carefully at question 1 I did not actually use Complete Induction, I used Mathematical Induction :( And it wasn't explained really well due to the lack of words. Basically, the idea was a full ternary tree of height n satisfies P(n) and since all ternary trees of height n have less than or equal number of nodes to the full ternary tree, they satisfy P(n) as well. I should of put
F(n) = F(n-1) + 3*l
N(n) <= F(n)
before
N(n) <= F(n-1) + 3*l
to clarify it a little more.. Oh wells.

My solution to the last question is also really different to that of the sample, so I will explain it in a number of posts this week; Yay!

Second test was not as hard as expected; I already forgot what was on it though hahah. Two questions I think? Professor was definitely right in telling us to just look at the past tutorial problems and problem Thanks! I hope the exam is at a similar level of difficulty xD Looked over Tutorial Excercises 6 and definitely need to read course notes now :/ The issues of not going to a single lecture >.<;;;