Last week of class!

Wow! Where has this semester gone?? Second year has flown by for me.

Well, our final week lecture content consisted of using elimination techniques to take a NFSA and convert it to a regex expression. The technique, although very procedural, was very long and I suppose I will have to just take my time during the exam to make sure I get it right.

Having assignment 3 behind us now I found a very cool concept for Q1 which was called the Pigeonhole Principle. I gotta say, this question drove me bonkers without knowing about this mathematical principle, but once I was told to research this online I had that amazing rush of finally getting somewhere with the question! Haha. The question was asking us to prove why a DFSA under 16 states couldn't exist for a certain language. Basically, the whole idea behind the question was that if for some reason there wasn't 16 states available and the nature of the machine required to have knowledge of the 16 different permutations of the length 4 binary string then there must be a state which has two different strings on it if there is less than 16 states in the machine. But anyways, in short the answer followed from this fact that eventually the machine will drive the two strings to a state which will both be an accepting state and denying state which helped us devise contradiction.

Some interesting examples that helped me understand the application to Q1 of the Pigeonhole Principle I found are:

• Softball team

  Imagine five people who want to play softball (n = 5 items), with a limitation of only four softball teams (m = 4 holes) to choose from. The pigeonhole principle tells us that they cannot all play for different teams. At least 2 must play on the same team.

  [edit]Sock-picking

  Assuming that in a box there are 10 black socks and 12 blue socks, calculate the maximum number of socks needed to be drawn from the box before a pair of the same color can be made. Using the pigeonhole principle, to have at least one pair of the same color (m = 2 holes, one per color) using one pigeonhole per color, you need only three socks (n = 3 items). In this example, if the first and second sock drawn are not of the same color, the very next sock drawn would complete at least one same-color pair (m = 2).

  
  

  (Cited from http://en.wikipedia.org/wiki/Pigeonhole_principle)