Combinatwordsing on sunday…

From S. Tringali. link Let \Sigma be a set and denote by \Sigma^* the free monoid on \Sigma, which we write, as usual, in multiplicative notation. Let \varepsilon be the identity element of \Sigma^* and |\cdot| the function \Sigma^* \to \mathbb N mapping a word w to its length (here, \mathbb N means the non-negative integers). Then, pick w \in \Sigma^+ .

1. Prove that for every k \in \mathbb N there exists at most one pair (e,v) \in \mathbb N \times \Xi^* such that v^e = w and |v| = k.

2. Prove the following: If v_1, v_2 \in \Xi^* and e_1, e_2 \in \mathbb N^+ are such that v_1^{e_1} = v_2^{e_2} = w, then there exists v \in \Xi^* such that w = v^{\text{lcm}(e_1, e_2)} and v_i = v^{\text{lcm}(e_1, e_2)/e_i}.

Proof.

1. If v_1^{e_1} = v_2^{e_2} and |v_1|=|v_2| then e_1=e_2 hence v_1=v_2.

2. v_1^{e_1}=v_2^{e_2} for e_1, e_2\geq 1. By symmetry wlog e_1 \leq e_2 and |v_1|\geq|v_2|.
It must be v_1=v_2x for some x\in\Sigma^*.
So v_1^{e_1}=(v_2x)^{e_1}=v_2^{e_2}, then (xv_2)^{e_1-1}x=v_2^{e_2-1}, right multiply by v_2 to get (xv_2)^{e_1}=v_2^{e_2}.
That is (v_2x)^{e_1}=(xv_2)^{e_1}\Rightarrow v_2x = xv_2\Rightarrow v_1=v_2x=xv_2.
From this we have v_1v_2 = (v_2x)v_2 = v_2(x v_2) = v_2v_1.
Now, since v_1 v_2 = v_2 v_1 we set n:=|v_1v_2| and observe by induction that
if n=2 then v_1=v_2 and the thesis follows.
Otherwise let n>2. There must be a word y\in\Sigma^* s.t. v_1=v_2y=yv_2.
Observe |v_2y|=v_1<|v_1v_2|=n.
Apply induction hypothesis we see that there must be a word v\in\Sigma^+ and integers a, b>0 s.t. v^a=v_2 and v^b=y.
Hence v_1=v^{a+b} and v_2=v^b. We pick the longest such v.
From |v|\mid |v_1|, |v_2| it must be |v|=\text{gcd}(|v_1|, |v_2|), since otherwise we pick v^{\text{gcd}(|v_1|, |v_2|)/|v|} against the maximality of |v|.
Moreover if we set a':=a+b, b':=b observe e_1a'=e_2b' and denote by l such a number.
l is a multiple of both e_1 and e_2.
Since v_1^{e_1}=v^l=v_2^{e_2} and we picked the longest v, there cannot be a smaller such l, since otherwise we pick v^{l/ \text{lcm}(e_1, e_2)}.
This imply l=\text{lcm}(e_1, e_2), that is a'=\frac{\text{lcm}(e_1,e_2)}{e_1} and b'=\frac{\text{lcm}(e_1,e_2)}{e_2}.Q.E.D.

Non-context-free xcy language.

Excercise from Shallit. Let L:=\{xcy | x,y\in \{a, b\}^*, y \text{ is a subseq. of } x \}. Then L is not context free.

Contradics the pumping lemma for context free languages.
Proof. Suppose L is context-free, then there exists n\geq 1 such that for every word w with |w|\geq n there exists words d,x,e,y,f \in \Sigma^* such that |xy| \geq 1, |xey|\leq n and w=dxeyf \in L \iff dx^i e y^i f \in L for every i\geq 0.

Now pick w:=a^nb^n c a^n b^n.

Then w\in L. Consider any factorization dxeyf=w s.t. |xey|\leq n. We have one of three cases:
1. xey ends exactly in c or at the left of c in w.
2. xey=c or xey begins at the left of c in w end ends at the right of c in w.
3. xey begins exactly in c or at the right of c in w.
Consider the following i values for d x^i e y^i f.
Case 1., pick i:=0.
Case 2., pick any i\geq 0.
Case 3. pick any i\geq 1.
Then d x^i e y^i f\not\in L holds for every case. This contradicts the pumping lemma, thus L is not context-free. Q.E.D.

Paths from cycles

Exercise from Diestel. Let G be a graph and let C be a cycle in G. Let u,v\in C. Let P be a path from u to v of length (i.e. number of edges) equal to k . Then there exists a path in G of length \geq \sqrt{k}.

Proof. Wlog |C|<\sqrt{k}, otherwise we are done. Let P\cap C :=\{v_0, \ldots, v_n\} and n < \sqrt{k}. Let P_i:=v_i P v_{i+1} for every 0\leq i\leq n-1 and let m:=max_{i} \{|P_i|\}. Then k=\sum_{i=0}^{n} |P_i| \leq \sum_{i=0}^{n} m = mn < m\sqrt{k} , hence m>\sqrt{k}. Let j be such that |P_j|=m, then v_j P v_{j+1} C v_j is a cycle of length l\geq m+1 > \sqrt{k}+1.Q.E.D..

Regular languages of finite index

Ex from Shallit. Let L\subseteq \Sigma^* be a language. If k\geq 1 is s.t. L^{k-1}\neq L^{k}=L^{k+1} say that L has finite index equal to k. Then for every k\geq 1 there exists a regular language of finite index equal to k.

Proof. Fix k\geq 1 and pick \Sigma such that |\Sigma| = k.
Let L_{\leq 1}\subseteq \Sigma^* be the language of words containing at most one distinct letter in \Sigma. This is a regular language. Then L^i=L_{\leq i} is the language of words containing at most i distinct letters in \Sigma. Since |\Sigma|=k one has that L^{i-1} \neq L^i \neq L^{i+1} for every 1 < i < k but L^{k}=L^{k+1}. Q.E.D.