Problem Set 5

Although this problem set seemed trivial at first, it took me sometime to express the proof formally. The theorem was: If language L has a finite number of strings, then there is some regular expression that denotes L. Any finite set of language can be expressed by a regular expression using the union or concatenation operator. As long the theorem can be proven using one of these operators, then it would be true for all cases. I used induction on the number of strings in an arbitrary language to prove the theorem. Let the language L be {l1, l2, l3, l4}. This language can be denoted by the RE, R= l1+l2+l3+l4. If a new string (l5) is added to L, then it could be denoted by R= l1+l2+l3+l4+l5, thus proving that any language of finite length can be denoted by a regular expression.

Assignment 3 Question 3

In this question we (group effort) had to proof that a regular expression that doesn’t include the Kleene star would denote a finite language. The way we understood this question was that, if we include the Kleene star in our regular expression then we would have infinite repetitions of a pattern, thus consequently not a finite language. We set out to proof by simple induction that Kleene star leads to an infinite language. But this approach didn’t seem promising when we got to describing languages and alphabets. Thus we abandoned this approach and set out to proof that if the Kleene star was excluded, we would have a finite language. More specifically, if we only had union and concatenation available to our regular expression, then we would only be able to match languages consisting of finite number of strings. This approach was more plausible and was easier to carry out. We used complete induction on the sets of language, and show that the concatenation of two unions yielded a finite language.

Second Test

The Second test was a disaster for me. I got the morning session and the office hour mixed up and ended up showing up for the test 20 minutes past the start. I was stressing out of my mind. I managed to answer two of the three questions. I did well on the test than I anticipated, I actually passed. Professor Heap was very understanding and fair towards my situation. Thank you Professor.

Second Assignment

The first question on this assignment seemed complicated at first because it involved a combinatorial explosion. The trick in solving this question was to find a pattern and generalize it for all number of nodes. I made sure I understood the question thoroughly before I proceeded to solve it. I started out by drawing ternary trees from the root node. I expanded each combination of nodes and noticed the pattern as the number of nodes increased. I realized that the distribution of the nodes among the three sub-trees behaved like combination without replacement. Thus I devised a summation formula that yielded the total number of non-equivalent ternary trees given n nodes. The number of nodes available for each sub-tree is the total number of nodes minus that used by the previous sub-trees at that specific height. I tried the formula on different number of nodes and convinced myself that it works for all n.

Problem Set 3

Finding the closed form for the given function was tricky. Unwinding it in the conventional sense didn’t quite lead to the closed form. The crucial steps towards finding the closed form were done after unwinding and recognizing the patter in the un-winded terms. After unwinding and simplifying, I realized that each term was a multiple of 3. More specifically, the ratio between two consecutive term is 3. Thus the expansion was that of a geometric series. Thus to find the closed from of G(n), I had to use the geometric series formula, and plug in the ratio and the first term in the series. After finding the closed form of G(n), proving it using simple induction was pretty straightforward.

First Assignment

The most challenging question of the first assignment would have to be question 4. I didn’t know how to approach the question to begin with. But after wrestling with it for awhile and getting help on it, the question started to make sense to me. Proving the contradiction was a bit tricky, because we had to choose the well ordering principle. I had to prove that there exists a smallest numerator for a quotient representing the golden ratio. This led to the required contradiction proving that the golden ratio is an irrational number, which I used to answer the last part of the question: proving 5^1/2 is irrational.