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