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).

Skip to content
#
Month: September 2012

# Goodnight links…

# Combinatwordsing on sunday…

# Non-context-free xcy language.

# Paths from cycles

# Regular languages of finite index

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 .

**Proof.**

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. .

Observe .

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.**