JXPATH: nice jar from Apache Commons to evaluate XPATH over graph objects (i.e. JavaBeans).
HashCodeBuilder: another nice Apache Commons API to overwrite your Java hashcode() methods the-right-way (hope).
From S. Tringali. link Let be a set and denote by the free monoid on , which we write, as usual, in multiplicative notation. Let be the identity element of and the function mapping a word to its length (here, means the non-negative integers). Then, pick .
1. Prove that for every there exists at most one pair such that and .
2. Prove the following: If and are such that , then there exists such that and .
1. If and then hence .
2. for . By symmetry wlog and .
It must be for some .
So , then , right multiply by to get .
That is .
From this we have .
Now, since we set and observe by induction that
if then and the thesis follows.
Otherwise let . There must be a word s.t. .
Apply induction hypothesis we see that there must be a word and integers s.t. and .
Hence and . We pick the longest such .
From it must be , since otherwise we pick against the maximality of .
Moreover if we set observe and denote by such a number.
is a multiple of both and .
Since and we picked the longest , there cannot be a smaller such , since otherwise we pick .
This imply , that is and .Q.E.D.
Excercise from Shallit. Let . Then is not context free.
Contradics the pumping lemma for context free languages.
Proof. Suppose is context-free, then there exists such that for every word with there exists words such that and for every .
Now pick .
Then . Consider any factorization s.t. . We have one of three cases:
1. ends exactly in or at the left of in .
2. or begins at the left of in end ends at the right of in .
3. begins exactly in or at the right of in .
Consider the following values for .
Case 1., pick .
Case 2., pick any .
Case 3. pick any .
Then holds for every case. This contradicts the pumping lemma, thus is not context-free. Q.E.D.
Exercise from Diestel. Let be a graph and let be a cycle in . Let . Let be a path from to of length (i.e. number of edges) equal to . Then there exists a path in of length .
Proof. Wlog , otherwise we are done. Let and . Let for every and let . Then , hence . Let be such that , then is a cycle of length .Q.E.D..
Ex from Shallit. Let be a language. If is s.t. say that has finite index equal to . Then for every there exists a regular language of finite index equal to .
Proof. Fix and pick such that .
Let be the language of words containing at most one distinct letter in . This is a regular language. Then is the language of words containing at most distinct letters in . Since one has that for every but . Q.E.D.