Problem 1.32

The key to this problem is to construct a DFA that can recognize that reverse sum language. With that, we can invoke problem 1.31 to show the sum language is also regular.

The proposed DFA has 3 states, the first state is the start state and represents the last digit has no carry, and the second state is the with carry state represents the last digit has a carry. The third state is the error state. The first state is also the final state.

To simplify discussion, any unrecognized alphabet in a state go to the error state, and it stuck forever there by having all alphabets points towards it.

Now in the start state, we have these transitions:

$ \left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right) $ , $ \left(\begin{matrix} 0 \\ 1 \\ 1\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 0 \\ 1\end{matrix}\right) $ goes to start state.
$ \left(\begin{matrix} 1 \\ 1 \\ 0\end{matrix}\right) $ goes to carry state.

In the carry state, we have these transitions:

$ \left(\begin{matrix} 0 \\ 0 \\ 1\end{matrix}\right) $ goes to the start state
$ \left(\begin{matrix} 0 \\ 1 \\ 0\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 0 \\ 0\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 1 \\ 1\end{matrix}\right) $ does to carry state.

That's it, we completed the description for the DFA that can recognize the reverse sum language. 

That shows the reverse sum language is regular. By problem 1.31, the sum language is also regular!

Q.E.D.

Problem 1.31

Finally, we really doing something about the theory of computation!

To show the reverse $ L^R$ of a regular language L is also regular. We will construct a non-deterministic finite automata (NFA) for the language. Since L is a regular language, it has a deterministic finite automata (DFA).

The idea is simply to run the DFA backward. But there is one complication - a DFA could have multiple final states. So we simply extend the original DFA to NFA by joining merging all the final states to a single final state with epsilon transition.

Then we reverse all transitions to go backward, using the merged final state as start state, and the original start state as the final state, we obtain a NFA for the reverse language.

To show the constructed NFA actually works. Consider a string w in L, there exist a path from the original start state to the merged end state. So there exist a reverse path in the constructed NFA as well. The transitions are exactly the same as it was, only in reversed order, so the reverse string is recognized.

For a string that is NOT in w, however, the original DFA will lead to a non-final state, so we cannot take the epsilon path to the merged final state. Note that before exhausting all input symbols, it might reach the final state and took the epsilon path before. But since the merged final state does not consume any symbol, the path cannot extend there.

Now assume somehow the reverse is accepted, so there exists a path from the merged final state back to the original start state with symbols reversed, but then it would mean a path exist from the original start state to the merged final state by reversing it, which we already proved doesn't exist. The contradiction shows the reverse cannot be accepted.

Together we show our constructed NFA accepts precisely the reverse language. So the reverse language is regular.

Problem 0.14

This isn't really a problem computational theory. But I will complete this anyway.

Define x to be the monthly payment. r to be the monthly interest rate, T be the number of months.

Total future value of these payment is

$ \sum\limits_{i = 0}^{T-1}{x(1+r)^{i}} = x\frac{(1+r)^n - 1}{(1 + r - 1)} = x\frac{(1+r)^n - 1}{r} $

But then it must equals to the future value of the loan, so we have

$ x\frac{(1+r)^n - 1}{r} = p(1+r)^n $

Plugging in the values it is easy to see the answer is $536.82.

(*) Problem 0.13

Moving forward, I will use a star in the subject to indicate the problem is not easy.

As a first attempt, I tried Erdo's lower bound for Ramsay number. It doesn't work, since larger than the lower bound says nothing about its relative magnitude with the actual Ramsay number.

Now I try the hint on the book.

Pick a node x.

If x's degree is larger than a half of the number of remaining nodes. Then add it to pile A, and dump all the nodes that is not connected to x. Intuitively, we are trying to find a clique, so anything not connected to x is useless. We can dump at most half of the nodes.

Otherwise x's degree is less than a half of the number of remaining nodes. Then add it to pile B, and dump all the nodes that is connected to x. Intuitively, we are trying to find an independent set, so anything connected to x is useless. Again, we can dump at most half of the nodes.

The algorithm proceed until there is no more nodes. Any node in pile A must be connected to each other which means it is a clique. Any node in pile B must not connect to each other which mean it is an independent set.

The algorithm can only throw at most half the number of nodes each time, which means it will take at least $ \log_{2}n $ steps to run. So in the worst case the nodes are distributed evenly so that the size of either clique or independent set is at least $\frac{1}{2}\log_{2}n$.

Q.E.D.

As as aside - this is a genius method - I couldn't have thought about it. I thought about trees (when I see logarithm, but I haven't thought about this simple algorithm)

Problem 0.12

A graph can be decomposed into connected components. Among the connected components, there exist one with maximum size. Suppose the connected component is K with |K| node. Assume K has more than 1 node, since K is connected, the degrees of the nodes in K must be at least 1 and at most |K|-1, but there are |K| nodes, by the pigeonhole principle, there must be two nodes with the same degree.

On the other hand, if the maximum sized connected component has only 1 node, it must be the case that all nodes are not connected, pick any two nodes they will have the same degree = 0.

Q.E.D.

Aside 1: Graph theory is a great fun of it own - if I find good graph theory problem I will post it here.
Aside 2: It is a pleasure to type Q.E.D. I mean it!

Problem 0.11

This one is tricky. The simple observation is that this crap statement break down even when there are two horses, so let's expand the statement in that case.

Assuming any set of one horse has the same color.

Given a set H of two horses, name them by their color, let's say, black and white. The argument about H1 has only one color still follows. The argument that H2 has only one color still follow. But the last 'therefore' statement is flawed. It is possible for a set of horse to have two subset H1 and H2 of horses of the same color but H doesn't.

This shows the induction breaks at the least breaking point, even if S(1), S(2) => S(3) => S(4) are all sound. As long as S(1) does not imply S(2), S(3), S(4) are just all as crap as all horse has the same color!

Problem 0.10

This one is easy. The division by (a - b) is not a legal arithmetic operations since a = b, which implies (a - b) = 0.

Heck, one can show anything equals to anything with this 'trick'.

Starting of the blog

I am currently reading Introduction to the Theory of Computation (pdf). The book is awesome in the sense that it takes away the boring detailed proof and replace them with ideas. It is also awesome with very interesting exercises.

So I am writing this blog to document the answers to the problems I have attempted. Stay tuned.