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.

DFSA

I had some problems understanding how to create the state transition table for a given DFSA. I knew how to form transition tables using circuits but this one is a bit different. I read this great book: "Introduction to automata theory languages and computation 2nd edition by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman" and the bank-store-customer example they used made it clear to me.

I used an example from the book and tried to solve it.

Problem 1: Design a DFSA that accepts a string that has the sequence "01" somewhere in the string

Solution: Let L be the language where:

{x01y where x and y are any strings of 0's and 1's}

So that means "01", "11010", "100011" ε L
but "100", 110000", "000", "111" is not contained in L.

Let q0 be the starting state. Now since we need to find string "01" we need a 'variable' to store the previous character so that we can compare. Let q1 be the state when we see a zero. So when we are in q1 and we see a "1", we can move to a final state q2 which is the accepting state. Now, if we are in q1 and we still encounter a "0" character, we shall stay in the same state. Similarly if we are in q0 and find a "1", its useless since the string desired should start with "01".

Finally once we step into q2, we dont have to worry if we encounter a "0" or "1" anymore since we will remain in q2 no matter what. (By the way, if i remember, in a JK flip-flop system, this is denoted by capital X which means 'dont care' state).

So our transition table looks as follows:

∂(q0, 1) = q0

∂(q0, 0) = q1
∂(q1, 0) = q1
∂(q1, 1) = q2
∂(q2, 0) = q2
∂(q2, 1) = q2

and our state diagram looks like:

Now what if we try and modify it and say we want it to accept any string containing the string "0101"

Problem 2: Design a DFSA that accepts a string that has the sequence "0101" somewhere in the string

So our state transition table will change and we have to introduce new states q3 and a final accepting state q4. So if we start at q0 and find a "1", its pretty useless and we remain in the same state q0. but if we find a "0" means that it is the start of the substring we are looking for. So we jump to state q1. Now from q1, if we find a "0" as the next character, we are back to square 1 so we jump back to q0. But if we find a 1, we jump to q2. Similarly, if we get a "0" while being in state q3, its useless since its not forming the substring we are looking for and we jump back to q0. But if we find a "1", then we jump to the final accepting state q4. Once we are in state q4, we 'dont care' about the incoming characters since we have already found our substring and we remain in state q4.

So our transition table becomes:

∂(q0, 1) = q0 ---------- ∂(q0, 0) = q1

∂(q1, 0) = q0 ---------- ∂(q1, 1) = q2

∂(q2, 0) = q3 ---------- ∂(q2, 1) = q0

∂(q3, 0) = q0 ---------- ∂(q3, 1) = q4

∂(q4, 0) = q4 ---------- ∂(q4, 1) = q4

And our state diagram would look like this:

I must thank Danny for showing us jFlap. Its a great tool to analyse state diagrams and find flaws.

Problem Set 5

Problem: Prove that if language L has a finite number of strings, then there is is some regular expression that denotes L.

The first thing i noticed is that since L has a finite number of strings, there exists a Regular Expression (RE) that denotes L.

//This roof resembles a proof we did in linear algebra (MAT223) where we had to prove that a vector v = (v1,v2,v3,..,vm) belongs to a vector space.

Let L = {L1, L2, L3, ... ,Lm} over Ʃ

Any substring from L can be denoted as L_a where a should at least be 1 and at most be m. Given that strings are a concatenation of characters, we can define a string:

L_a = (L_a1, L_a2, L_a3, ... ,L_an), since L_a belongs to L and L_a belongs to Ʃ

Then L_a1 is a regex for Ʃ ==> L_a1L_a2 is also a regex;
Then L_a1L_a2...L_an is a regex for Ʃ

RE(L_a1L_a2...L_an) is a regex for Ʃ and given that L_a = (L_a1, L_a2, ... L_an), L_a defines the string.

Then RE(L_a1L_a2...L_an) is the String L_a.

All substrings in L have regular expressions RE_1, RE_2, RE_3, ... ,RE_n
RE_1 is a regex for Ʃ
(RE_1 + RE_2) is also a regex for Ʃ
.
. Concatenating the regexes
.
(RE_1 + RE_2 + RE_3 + ... + RE_n) is also a regex for Ʃ

The sum of all regexes is equivalent to the language L.

n
Ʃ RE _i <=> (RE_1 + RE_2 + RE_3 + ... + RE_n) <=> L
i=0

Then if L has a finite number of strings, there exists a regular expression RE that denotes L;

Problem set 4

Problem set 4 was OK, i missed a perfect score because I did not use the induction hypothesis but here is my solution: (Please note that blogspot does not like spaces so indentation is a problem; sorry about that)

def revString(s):
if len(s) <>
else: return revString(s[1:]+s[0])

(1) Define our P(n)
{
____P(n) = /forall s /in Strings+ { if len(s) == 1: revString(s)
____else if len(s) > 1: revString(s[1:]+s[0])
}

Lets assume that the program does not take empty strings (strings with length 0) and lets denot all strings with positive lengths but Strings+. i.e: /forall x /in Strings+, len(x) > 0.

Proof:
Base case:
len(s) = 1

Assume s /in Strings+
{

__Then s is a string with at least 1 element
__Then len(s) = 1 and 'if' condition is satisfied
__Then revString() executes line: 'if len(s) is less than 2: return s
__Then revString() is correct.

}
Then /forall s /in Strings+, len(s) < 2 =""> revString() is correct and our base case passes=> Post condition is true.

Inductive case:

Assume n /in N #Generic natural number
_Assume s /in Strings+
__Assume i=0_V^n P(i) (*) (Want to prove P(n+1))
___Assume len(s) >= 2

{
____Then 'if' condition is false and line 'if len(s) <>
____Then line 'else: return revString(s[1:] + s[0])' is executed.
____Then len(s[0])=1 && (len(s[0]) <= len(s[1:]).
____Since len(s[0]) = 1, from our base case we know that len(s) == 1 ==> return s.
____So return revString(s[1:]) + s[0] # *1 = s[0] part is then true.
____Then revString(s[1:]) is called.

____Case 1: len(s[1:]) == 1:
_____by base case, if len(s) == 1: then return s
_____Then s[1:] is returned and revString() is correct.
_____s[1:] + s[0] means string returned is reversed ==> Post condition is true.

____Case 2: len(s[1:]) >= 2:
_____Then line 'else: return revString(s[1:] + s[0])' is called.
_____# s[0] by *1 is true
_____Then by (*), revString() is correct.
_____==> Post condition is true
}

___Then revString() is correct # proof by cases
__Then P(n+1)
_Then i=0_V^n P(i) => P(n+1) # intro =>
Then /forall s /in Strings+, i=0_V^n P(i) => P(n+1) #intro
/forallThen /forall n /in N, /forall s /in Strings+, i=0_V^n P(i) => P(n+1) #intro /forall

Then Post condition holds and revString() is correct

Test 2

Unfortunately, I had a lot of problems to look after (some related to school and some not) and I did not have enough time to study for any subject... :( As a result I did find test 2 difficult but i still gave it a shot from what I followed in lectures.

The first question was a bit confusing, I think I got the wrong idea... I stated unwinding G(n) and tried to prove that T(n) can be derived and exists in G(n). I used the same unwinding technique from problem set 3 but I dont know if that was the solution to it...

The second question was fine, we had done something similar in lecture and in CSC165 during summer. The third question was a bit tricky, i had trouble finding an appropriate invariant but I knew that we had to show that the loop terminates. We know that n keeps on getting smaller after each iteration and at some point, the condition would be false and the loop would terminate.

To summarize, i knew part of the solutions but i'm not sure whether they are correct... I will have to catch up on the forthcoming problem sets/assignemnts and tests.

State machines... we meet again

On Wednesday, we were introduced to state diagrams and how to draw a circuit from given states and state transitions... I did FSMs back home when I was studying electronics... They are very useful for designing sequential circuits using JK flip-flops. I was surprised and happy to learn that we are learning how to use state machines in CSC236 but this time, we are not lighting leds or making a vending machine... instead we are building "circuits" to analyse strings.

Professor Danny used a very interesting software called jKFLAP (? not sure) where he made the circuit simply by drag-and-drop. I was also amazed that it can even test the circuit.. Now, how I wished I knew back then that there was such a software...

Unfortunately because of some personal problems, I missed two lectures (the ones dealing with formal languages) but it was pretty easy to catch up on the slides. I found that the laws for the equivalent REs on the slides were similar to the laws whether a vector belongs to a vector space from linear algebra (MAT223).

For example, there has to be the zero element or empty string such that:

( R + Ø ) = R # Ø is the empty string.

Theres only one thing I'm not too sure about and that is the "Idempotence of Kleene start" where:


( R** = R* )

I missed that lecture, unfortunately, but i'm wondering whether there is a typo and if it should have been: Kleen star (thats what google says)

Wikipedia states that: http://en.wikipedia.org/wiki/Kleene_star

1) If V is a set of strings then V* is defined as the smallest superset of V that contains λ (the empty string) and is closed under the string concatenation operation. This set can also be described as the set of strings that can be made by concatenating zero or more strings from V.


2) If V is a set of symbols or characters then V* is the set of all strings over symbols in V, including the empty string.

So for example:

{'a', 'b', 'c'}* = {λ, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", ...}

Applying the Kleene star would mean it contains the zero element λ and all the elements 'a', 'b', 'c'

And then it would looke like:




We can notice a pattern in the number of elements that form after every "step" as shown in the image below: