Final Words

Contrary to CSC165, I actually enjoyed this course. It laid more emphasis on applications rather than theoretical proofs. The problem solving techniques helped me tackle problems in different ways (specially in physics) and upgraded my problem solving abilities. I learnt that all problems do not need to be solved mathematically but a bit of logic can help a lot; example the binary arithmetic trick for the 4th question for A3.

Although I did run into some medical issues during the semester, I am a bit worried about my marks but I was able to catch up most of the work I missed and Danny was very helpful throughout the term. I am very thankful to him for all his help in CSC165 and CSC236 and to the TA's at the CS Help Center. This course makes me feel more confident that I will actually be able to do the AI specialist without glitches and inspires me to continue in this field.

Happy holidays to everyone!

Bimal

Test 3

Today we had test 3 but I did not do so well in it (I dont know, maybe I did). I have a bad fever and a flu since 5 days and its been bugging me a lot... I cant even study properly... I thought of going to the hospital but the fear of having to take a blood test forced me to take the test no matter what; because last time I took a blood test, the syringe needle broke in my arm and getting that thing out was the most painful experience in my life and since then, has become my greatest fear...

About the test, the first question about the DFSA seemed familiar to Q4 from the third assignment. I think I got all the state declarations right and I think the way to tackle part b of the first question was to count the odd/even number of 1's and their sums and match them to the declaration that suits it.

I think I bombed the second question, I thought about it on my way home and I think I got the wrong answer for it. I proved that if there is a regex for R1 and R2 then there is a subset that can be denoted for L(R1 + R2) and since R1+R2 belongs to R, then the subset (0,1,epsilon) exists...

The third question was easy but I think I used the wrong technique... I made a DFSA that represents L2 and by using minimisation techniques, I got a regular expression that takes from state epsilon to a final accepting state and that regular expression was eqivalent to the L( ... ) expression. I wanted to make a formal proof but my head hurt too much and I couldnt concentrate anymore.

I hope I will get better soon because my finals start next week and I need to study for them.

An interesting example on the Pumping Lemma

I had some problems understanding the Pumping Lemma and while reading a book (Introduction to Automata Theory Languages and Computation 2nd edition page 128) I came across an interesting example of how they described the Pumping Lemma as a game:

The Pumping Lemma as an Adversarial Game

... The pumping lemma is an important example in a theorem that involves several alternations of 'for-all' and 'there-exists' quantifiers that can be thought of as a game between two players, since it in effect involves four different quantifiers: "for all regular languages L there exists n such that for all w in L with /w/ >= n there exists xyz equal to w such that ..." We can see the application of the pumping lemma as a game, in which:

1. Player 1 picks the language L to be proved nonregular.

2. Player 2 picks n, but doesn't reveal to player 1 what n is; player 1 must devise a play for all possible n's.

3. Player 1 picks w, which may depend on n and which must be of length at least n.

4. Player 2 divides w into x, y, and z, obeying the constraints that are stipulated in the pumping lemma; y != epsilon and /xy/ <= n. Again player 2 does not have to tell player 1 what x,y, and z are, although they must obey the constraints.

5. Player 1 "wins" by picking k, which may be a function of n,x,y, and z, such that x(y^k)z is not in L.

Building a DFSA from an NFSA

Suppose we have a Non-Deterministic Finite State Automaton (NFSA) and we want to derive a DFSA from it. Lets take for example, a NFSA that accepts strings containing at least '00' or '11' and can be of even or odd length:
We can see that if we input strings containing at least two zeroes or two ones, those strings are accepted by this machine. To derive a DFSA from this machine, we need to draw the state transition table.

First lets observe the transitions when we input 0's and 1's:

If we input a 0, we remain in q0 and at the same time we go to q1 therefore q0q1
If we input a 1 we remain in q0 and go to q3 therefore q0q3

Now that we have the transitions for q0, we now have new states q0q1 and q0q3 and we now have to deal with them.

if we are in q0q1 and we input a 1, if 0 enters q0 it transits to q1 and if 0 enters q1 it transits to q2. We then get a new state q0q1q2. And when we are in q0q1 and we get a 1, we remain in q0 and it transits to q3 as well. When we get a 1 for q1, there is no state transition for 1 so we don't move anywhere. Then we get state q0q3 which we already found for the transitions for q0.

Now, we have to take care of q0q3. If we get a 0 we remain in q0 and branch to q1 and when we get a zero for q3, we don't move anywhere since there are no state transitions described for a 0 input. Then we get state q0q1. Now when we get a 1 in q0, we remain in q0 and branch to q3. When we get a 1 for q3, we branch to q4. So we geta new trsnaition state q0q3q4 and we have to take care, as always for every new state derived, of it and observe its transitions. If we get a 0 for q0q1q2 we get the same state transition: q0q1q2 and if we get a 1, we get q0q3.

Similarly if we get a 0 for q0q3q4 we get q0q1 and if we get a 1 we get q0q3q4 again. In our NFSA, q2 and q4 were final accepting states so in our DFSA, any state containing q2 or q4 will be accepting states as well. We will highlight them in red and all others in blue. So now we dont have anymore new states and we can start building our DFSA but lets build the transition table first so that we get a clearer picture of what's happening:

-------------------Inputs--------------|
---------------0-------------1---------

q0-----------q0q1---------q0q3

q0q1--------q0q1q2-------q0q3

q0q3--------q0q1---------q0q3q4

q0q1q2------q0q1q2------q0q3

q0q3q4------q0q1--------q0q3q4


And our DFSA looks like this:

Problem 4 Assignment 3

Use the Cartesian Product technique from Section 7.5 of the Course Notes to construct a DFSA that accepts binary strings of odd length, and that are multiples of 5 when interpreted as base two numbers. For example, your machine should accept 101 (5 in base two), but not 1111 (15 in base two). State, without proof, the appropriate state invariants (see Section 7.3).


My teammate and I worked on a solutiona nd came up with the following:

The following is the state invariants of a DFSA that accepts binary strings of
odd length, and that are multiples of 5 when interpreted as base two numbers.

Note: In the expression x%5 = n, n denotes the remainder of x divided by 5.


State invariants of a DFSA that accepts binary strings of odd length.

Q_1 = {q'_0, q'_1}.

Sigma_1 = {0, 1}.

s_1 = {q'_0)}

F_1 = {q'_1}
q'_0 if the length of x is even
P_1(x): delta*(s_1, x) = q'_1 if the length of x is odd


State invariants of a DFSA that accepts binary strings that are multiples
of 5 when interpreted as base two numbers:

Q_2 = {q_(epsilon), q_0, q_1, q_2, q_3, q_4}.

Sigma_2 = {0, 1}.

s_2 = {q_(epsilon)}

F_2 = {q_0}

--------------q_(epsilon) if x is an exmpty string
--------------q_0 if x%5 = 0 when interpreted as a base two number
--------------q_1 if x%5 = 1 when interpreted as a base two number
P_2(x): delta*(s_2, x) = q_2 if x%5 = 2 when interpreted as a base two number
--------------q_3 if x%5 = 3 when interpreted as a base two number
--------------q_4 if x%5 = 4 when interpreted as a base two number


State invariants of a DFSA that accepts binary strings of odd length, and
that are multiples of 5 when interpreted as base two numbers.

Q = {q_(epsilon), q_0, q_1, q_2, q_3, q_4, q'_0, q'_1}.

Sigma = {0, 1}.

s = {(q_(epsilon), q'_0)}

F = {(q_0, q'_1)}

------------(q_(epsilon), q'_0) if x is an empty string
------------(q_0, q'_0) if length of x is even and x%5 = 0
------------(q_0, q'_1) if length of x is odd and x%5 = 0
------------(q_1, q'_0) if length of x is even and x%5 = 1
------------(q_1, q'_1) if length of x is odd and x%5 = 1
P(x): delta*(s, x) = (q_2, q'_0) if length of x is even and x%5 = 2
------------(q_2, q'_1) if length of x is odd and x%5 = 2
------------(q_3, q'_0) if length of x is even and x%5 = 3
------------(q_3, q'_1) if length of x is odd and x%5 = 3
------------(q_4, q'_0) if length of x is even and x%5 = 4
------------(q_4, q'_1) if length of x is odd and x%5 = 4

How to nail an assignment

Image Courtesy: Jared - MAT237 Assignment 2

I just discovered one of the major problems I had when doing assignments (Whether it was for CSC165 or CSc236 or any other subject) while working on Assignment 3. I found that I was thinking too hard and most of the time, I misread the question. While working on A3, the first thing I noticed about question 1 was a proof on an iterative program. Immediately I put in some values and calculated the output and I noticed that q returned the number of times the while loop executed and r would give the GCD() of the two numbers n,m. I wrote a 1.5 page proof on it...

Well it sure was ugly and when I showed it to my assignment partner, he was surprised and he simply asked me:

"Why?"

I was surprised and when he told me what the function exactly does and the fact that it was already described, I felt stupid and I felt that I wasted a lot of time writing the unnecessary proof. It was so simple that after sometime I asked myself:

"Why didn't I think of that in the first place? and what made me think of GCD()?!!"

The second mistake I made was on question 4. I actually thought we had to hand in a complete DFSA. Well it turned out that we simply had to submit the state invariants and that would give the TA's a clear idea of how the machine worked. It shows that I didnt even read the question properly and thought too much on it when it was simple. Maybe I panicked and tried designing a DFSA and used a series of inputs to test it. But when I did so, I found that I was going round and round and that trial-and-error may not be effective in solving this kind of problem.

I did have some problems understanding how to develop a technique to count multiples of 5. Thats when I went to Danny and he explained to me how to tackle this sort of problem. Well everything went well after that but the only thing bothering me is that I feel being careless can be very dangerous and can account for most mistakes. Simple misinterpretations can lead to disaster and working with a partner really helped me find my faults.

I hope any student that reads this post will learn something about my experiences and will be careful when tackling assignments. Anyways I have made it a habit now that for any subject, if I dont understand something in the assignment, I would go and ask the TA's at the help center or the instructor.

The Koch Curve

I know its slightly off topic but still, there is some connection to CSC236 -- Paterns. The Koch Curve is sort of a fractal, we can use the equations and change it to make interesting shapes. Here is the python code for a Koch Curve (got it from wikipedia) that will model a snowflake:

import turtle
set="F"
for i in range(5): set=set.replace("F","FLFRFLF")
set=set+"R"+set+"R"+set
turtle.down()
for move in set:

#Get rid of the underscores, replace by a sinlge tab as blogspot doesn't like leading blank spaces.
____if move is "F": turtle.forward(100.0/3**i)
____if move is "L": turtle.left(60)
____if move is "R": turtle.right(120)
input ()

And we get this image:

Now what if we try and modify the equations?

Lets try:

import turtle

import math

set="F"

c = 2f

for i in range(5): set=set.replace("F","FLFRFLF")

set=set+"R"+set+"R"+set

turtle.down()

for move in set:

____if move is "F": turtle.forward((100/c**i))

____if move is "L": turtle.left(60/c**(c-i*i))

____if move is "R": turtle.right(math.cos(45*(i/i**2))*i**4)

input ()

And we get a more interesting pattern:

Looks fun, now lets terribly screw it over and see what happens :)

Lets try:

import turtle

import math

set="F"

c = 2

for i in range(5): set=set.replace("F","FLFRFLF")

set=set+"R"+set+"R"+set

turtle.down()

for move in set:

____if move is "F": turtle.forward((100/c**i))

____if move is "L": turtle.left(60/c**(c-i*i))

____if move is "R": turtle.right(math.cos(45*(i/i**2))*i**4)

____set=set+"L"+set+"L"+set

____for move in set:

________if move is "F": turtle.forward((100/c**i))

________if move is "L": turtle.left(60/c**(c-i*i))

________if move is "R": turtle.right(math.cos(45*(i/i**2))*i**4) #set=set+"R"+set+"R"+set

input ()

After a couple of minutes of computation, we get this:

Now if we let the computation continue for a while (7mins) we get this:

And finally after 21 minutes, we get this beautiful image:

God knows what it is but I like it. Now there's something worrying me a bit, its still drawing! I dont know when it will stop drawing but i think i'll let it draw till tomorrow morning and see what the final image is like.