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 !