This is probably my last slog post for CSC236. The final is coming up and the slogs are due in a couple of days. I've enjoyed the course even more than I thought I would, but I don't know if my grades will reflect that.

My assignment 3 was rushed to say the least but bad grades notwithstanding, I still found the problems interesting. Either way i'm happy to have been introduced to the Theory of Computation by Professor Heap and my TA Lila.

Regular expression - How not to do it

I just ordered a book on regular expressions, after giving in to the realization that they kept coming up again and again. I figure if I'm going to keep using them I might as well try to make the best of a bad situation.

Until amazon can ship me a copy of Mastering Regular Expressions over from the UK, I'll have to do this the hard way. Let's take a look at exercise 1 for the quiz tomorrow:

Devise an NFSA to accept L( ( (0 + 1) (01)*)* )

I'm not convinced this color  coding has made that any more approachable but, i'll take a crack:
EDIT: This was admittedly a bad crack at this question, but i'll leave it.

 The language is made up of all strings that are made up of any number of the substrings '0X', '1X' where X is string made up of any number of the substring '01'.

Examples:

• empty string
• 0
• 1
•  001
• 101

Maybe if I listed them in a more ordered way:

len(x)= = 0

• ''

numstrings = 1
 len(x) = 1

• '0'
• '1'

numstrings = 2
len(x) == 2
numstrings = 0

len(x) == 3

• '001'
• '101'

numstrings = 2
len(x) == 4

• '0010'
• '0011'
• '1010'
• '1011'

numstrings = 2

Again a pattern emerges in the listing process.  I think i should consider the length of the strings in this language. So that should be easy to figure out and probably relevant to the later proof.

for an arbitrary string x in L:
length(x) == (1 + 2x )y for arbitrary naturals y,x

if y == 0:
    return 0
else:
    if x==0:
        return y
    else:
        return (1+2x)*y

In the first return statement, we take care of the empty string. In the second, we take care of the stuation in which x is 0. Namely, all the strings in L that do not contain the substring 01.

It seems my initial list of valid strings may have been flawed. I'll come back to this later.

Back to DFSA's

The tutorial six exercise looks challenging, particularly because I've been taking a longer break than intended due to the long weekend. I will attempt question 1.

Devise a DFSA that accepts the language of finite binary strings whose length is a multiple of 3. Explain why it is correct.

I assume any DFSA that accepts this language, must have 3 states. I say this because the question should be reworded as the following:

Devise a DFSA that accepts the language L = {x |  len(x)%3==0}. Explain why it is correct.

We can see that this function f(x) = len(x)%3 can have only 3 possible outcomes for an arbitrary string x and a corresponding arbitrary integer i:

 

          1 iff len(x) = 3i+1

f(x) =  2 iff len(x) = 3i +2

      0 iff len(x) = 3i

 

Because of this close relationship to f(x), I assume the DFSA will have 3 states. As to what they will be, I shall post more on that later.

 

Thanks for reading.

Second assignment already

In my second post of the semester, I think it only makes sense to talk about the second assignment, which is due at the end of the week.

Although question one sounds intimidating at first, there really is a lot you can prove about Odd Maximal Contiguous Ones Free Strings. I figured the best way to really understand what the question was getting at was to actually look at valid OMCOFS of varying length and try to discern a pattern between the length of the string and how many OMCOFS can be found.

To make this simple and repeatable, I quickly wrote the following small set of python functions:
def enum(n, s):
    if(len(s)==n):
        return [s]
    else:
        return enum(n, s+'0')+ enum(n, s+'1')

def is_valid_omcof(s, count, index):
    if index == len(s):
        return count % 2 == 0
   
    elif (s[index] == '0' and count%2!=0):
        return False
    elif (s[index] == '0' and count%2==0):
        return is_valid_omcof(s, 0, index +1)
    else:
        return is_valid_omcof(s, count+1, index+1)
def count_omcofs(n):
    count = 0
    for i in enum(n, ''):
        if is_valid_omcof(i, 0, 0):
            print i
            count+=1
    return "count = "+ str(count)

Using these three functions, I can generate all the possible strings of length n, and check which one of them are valid OMCOFS. I started running it with different lengths and I found an interesting result about the listing process of omcofs. Programmatically:

list_omcofs(size) == ['0'+omcof  for omcof in list_omcofs(size-1)] +   

                                  ['11'+omcof  for omcof in list_omcofs(size-2)]

Reducing problems down to linearly easier problems is probably not that useful in terms of efficiency improvements but if it ever became desirable to express the list of omcofs of any length recursively as a combination of smaller length strings (e.g. due to a max size limit for list_omcofs() ), this would come in handy. 

About the course so far:

I like this course. The proofs we handle are intuitive and it feels as though reasoning my way through the ones we've had so far has paid off, which isn't always the case with UofT courses. For once, i feel a direct link between the quality and depth of the thought that goes into the assessments and my grade in them.

I'm not exactly sure how i feel about the Slogs so far, but I've read somewhere that keeping a blog can be an effective way to improve one's communication skills so I've definitely been curious. That said, I'm finally getting down to my first blog post. God knows, I've procrastinated it for long enough, but with the midterm done and the second assignment so far into the future, it seemed as though this was the only piece of work i could do for 236.

So all in all, i've enjoyed the lecture material so far and i look forward to starting newer topics in computational theory.