Problem solving.

The following problem was taken from A3, it is number 3 on the assignemnt.

The language defined by L(R), where R is a regular expression that does not include a Kleene star, is a finite language.

1. UNDERSTANDING THE PROBLEM

The problem is asking to prove that if the condition( R is a regular expression that does not include a kleen star) is true, then the language L(R) must be finite.


2. DEVISING A PLAN

Looking at this at first sight, it appears like it would be easily solved using structural induction, so I will right out the outline of the proof and solve it.


3. CARRYING OUT THE PLAN

Basis:
If R is a regular expression, by definition then either R = \phi or R = \empty string or R = a, for some a \in \Sigma.
L(\phi) = \phi (the empty language, consisting of no strings)
L(\epsilon) = \empty string (the language consisting of just the empty string)
For any a \in \Sigma, L(a) = {a} (the language consisting of the one-symbol string a)

Induction Step:

Suppose S and T are two regular expressions that do not contain
Kleene stars, and that they denote finite languages L(S) and L(T).
Then (S+T) denotes the union L(S) u L(T), and its length is no
longer than the length of L(S)+L(T),which is a finite number.
Also (ST) denotes the concatenation L(S)L(T), and is no longer than
the length of L(S) x L(T), again a finite number(a mutiple of finite numbers).

Thus, both (S+T) and (ST) denote finite languages and all regular expressions
that do not include the Kleene star denote finite languages.

4. Looking Back

Looking back at my solution, I dont think there is any easier way to do this, and first looking at the problem I knew it must be true.

week 12+13

Today was my last day of 236, and I must say I enjoyed this course and I might even miss it ! The material for the last 2 weeks has continued to be interesting and this week we started context free grammar, which is also very interesting. I had my final test today and I think it went great, I was actually the first to finish the exam and I was surprised when I relized I still had around 25 minutes after I was done. I am pretty sure I did everything right so I am satisifed with my preformance. I have my finals next week and I really need to start studying.

My exam schedule is terrible, 4 exams in 4 days, but atleast 236 is the last one and I wont need much time to study for it as I believe im already well prepared for the final. I have to say this course was by far my favourite course, it was very well organized and the marking scheme was helpful, unlike my other courses in which one mistake could affect you greatly. Also in terms of material I really enjoyed this course and prof Danny was great in teaching this course, he passed his ideas to us in a clear way and still allowed us to develop our own thoughts in the course which, for me atleast, helped me a great deal to understand the material better .

Overall it was a great exprience, so I would like to thank prof Danny for this, and hopefully we will meet again !

week 10 + 11

These past two weeks have been much better than the ones before, due to a lesser work-load. Looking back at my other posts iv realized that all iv done mostly is complain , but your just going to have to bear with me :P. So we have done more regular expressions and wev started finite state automats. I like this section better then induction and programme correctness, its sort of like a game and I find it rather interesting. I actually missed handing problem set 5 in due to my failing alarm clock, which is really annoying, but atleast I managed to hand in problem set 6 this week and im fairly sure its entirely correct so I suppose that will somewhat compensate for missing ps5. I have also started working on assignement 3 which I think is much easier than the two before it, maybe it has to do with the fact that I enjoy doing FSA's and regex more, but I mean its taken me atleast a third of the time the other two assignments took. Next week my work load is back up so im doing more work this week so that Im not under much pressure next week, so hopefully everything will turn out to be just fine !

Week 9

This week has been fairly interesting. We have started a totally new and different section in 236 which is about regular expressions, its very interesting and after playing around with site danny gave us for regex's, I could even say its fun. We also had out test just now, and I think it went pretty well, maybe I could have made my answers clearer but hopefully that wont affect my mark too much. As for other courses, im still under alot of pressure due to the work load, which is really ridiculous, but im dealing with it and next week is a semi-break so im looking forward to that.

week 8

This week has been terrible, I have so much work its really getting to me. After finishing A2 for monday, which took a longgg time, I still had loads and load of work to do. I am really not enjoying my other courses as they are poorly organized and packed with work, but atleast I like 236 because everything makes sense in it ! After finishing A2 I dont have anything else for 236 due this week, so that a relief, although I would be rather working on 236 than any other course !

week 7

well iv began working on a2 and its pretty difficult, ps4 was pretty easy so it wasnt too much to worry about , but a2 is on another level, especailly the first question, iv spent hours on it and i cant seem to find a direct relation between one value and the next, altho i think i know how to solve it its probably more of a probability question cuz each child is related to the one before, anywho iv finished question 3 that wasnt too hard and im starting question 2 for now, before i get back to question 1 and try to finally solve it, again my schedule has been hectic this week so thats no fun, but oh well gota deal with it, speaking of which, im off to finish q2 now, later !

week 6

hmm this iv been mostly busy with my other courses, i did well on test 1 so im happy, altho i think i couldv(maybe shouldv) done better, but oh well im satisfied. This week we have a problem set iv looked at it and it doesnt look to hard so im not worried, my other courses are getting really hectic and this week i have loads of work so im gona concentrate on that first, before i start a2 !

week 5

so this week has been rather stressful, more so than the previous weeks, we had our first term test on friday, i thought I did rather well, so im hoping for a good grade. We have learned some structural induction techniques, they seem quite similar to the previous induction techniques, so they it shouldnt be much of a problem. My workload is increasing exponentially and im starting to stress out, but after this midterm I have some time to relax, if only for a day, but hopefully all goes well.

week 4

I finished and submitted the assignment on monday, which rather took a long time to finish, well not too long but quite a bit. After that I relized theres no problem set due this week, which ment I could relax for a while, well not really since I have alot of work in other courses, but hey Im not complaining( although I kind of am). The lectures this week were a little different since we started working on recursive programmes which is interesting so far. We have an exam next week which I am actually looking forward to, should be easy, I hope ! Well since no problem set or assignement is due this week theres not all that much too talk about, so I will continue my blogging next week, until that, bye !

Week 3

This week has defenitly been tougher than the previous ones, the work load for all my courses is increasing significantly so I have to put a bigger effort in . We had a problem set due friday and an assigment due monday, I thought that was probably too much work but after looking at problem set two, which was extremely easy, I did not mind too much. The assignment however is a different story, defenitly more challenging than the problem sets and even more so than the questions we have been doing in class. I am still working on it and I think I have finally managed to solve question 1 and 2 and now im trying to do 3, which seems more difficult than the previous two. I am aiming to finish the assignment today so I can begin working on my other courses already since I have alot of work, so far its going well so I should accomplish my goal.

Week 2

Week 2 was better than week 1 in my opinion, the problem set was interesting tho not that challenging but thats good since its not ment to be too challenging. 236 has defenitly become my favourite course since I enjoy combining logic with my problem solving skills . The first question on the problem set was easy since we did a very similar one in class, therefore the basic idea was already there, the second one was more challenging and altho I got the idea right I wasn't sure that i had gotten the solution correct since I did it my own way, but anyway I solved it so I should atleast get most of the mark. Class has been fun as well and I really enjoy prof Heaps methods of teaching since he allows us to think our own way and encourages creative thinking so we'r not just solving questions one way all the time.

week 1

Well week 1 started pretty slowly , much of it was just revision of things we had studied in 165, a course I particularly enjoyed. I'm hoping 236 would be as good as 165 was , but I'm pretty sure its going to be more difficult. The first 3 classes went by nicely and smoothly, not many difficult concepts and we already have a problem set due next week, I havn't looked at it yet but I intend to over the weekend, hopefully it wont be to challenging, altho I would not mind that all that much.