patternMinor
Minimum pumping length of concatenation of two languages
Viewed 0 times
languageslengthminimumtwopumpingconcatenation
Problem
there's this small part of my homework that I just can't figure out.
Let us denote $p(L)$ as the minimum pumping length of some language $L$. I'm supposed to find two regular languages $A,B$ so that
$$
p(AB)=p(A)+p(B)
$$
But whatever I try, I can only find languages so that
$$
p(AB) < p(A)+p(B)
$$
I've been sitting at this the whole day and I'm just going in circles. Can someone please give me a hint?
Let us denote $p(L)$ as the minimum pumping length of some language $L$. I'm supposed to find two regular languages $A,B$ so that
$$
p(AB)=p(A)+p(B)
$$
But whatever I try, I can only find languages so that
$$
p(AB) < p(A)+p(B)
$$
I've been sitting at this the whole day and I'm just going in circles. Can someone please give me a hint?
Solution
For a language $L$, denote $P(L)$ as the minimum pumping length of $L$. It is implied that $P(L)\ge1$.
Proposition. Let $A,B$ be two languages with finite minimum pumping lengths. We have $P(AB)\le P(A)+P(B)-1$. Moreover, there exist regular $A,B$ such that the equality holds.
Proof. Let $w=w_Aw_b\in AB$, where $w_A\in A, w_B\in B$. Assume $|w|\ge P(A)+P(B)-1$. Then either $|w_A|\ge P(A)$ or $|w_B|\ge P(B)$; otherwise, $$|w|=|w_A|+|w_B|\le P(A)-1 + P(B)-1\lt P(A)+P(B)-1,$$
which contradicts the assumption.
Now there are two cases.
-
$|w_A|\ge P(A)$. Since $P(A)$ is a pumping length for $A$, $w_a\in A$ can be written as $w_a=xyz$, satisfying the following conditions:
Hence, $w$ can be written as $w=xyz_B$, where $z_B=zw_B$, satisfying the following conditions:
That is, $w$ can be pumped with pumping length $P(A)+P(B)-1$.
-
$|w_B|\ge P(B)$. This case is similar to the case above.
Combining the two cases, we have proved $P(A)+P(B)-1$ is a pumping length for $AB$.
Let $A=\{\epsilon,\alpha, \alpha^2, \cdots, \alpha^{n-1}, \beta^n, \beta^{2n}, \beta^{3n}, \cdots, \}$, which is a regular language of minimal pumping length $n$. Let $B=\{\epsilon,\alpha, \alpha^2, \cdots, \alpha^{m-1}, \beta^m, \beta^{2m}, \beta^{3m}, \cdots\}$, which is a regular language of minimal pumping length $m$. Since $\alpha^{n-1}\alpha^{m-1}$, which is a word in $AB$ of length $n+m-2$, cannot be pumped, $AB$ is a regular language of minimal pumping length $n+m-1$.
Proposition. Let $A,B$ be two languages with finite minimum pumping lengths. We have $P(AB)\le P(A)+P(B)-1$. Moreover, there exist regular $A,B$ such that the equality holds.
Proof. Let $w=w_Aw_b\in AB$, where $w_A\in A, w_B\in B$. Assume $|w|\ge P(A)+P(B)-1$. Then either $|w_A|\ge P(A)$ or $|w_B|\ge P(B)$; otherwise, $$|w|=|w_A|+|w_B|\le P(A)-1 + P(B)-1\lt P(A)+P(B)-1,$$
which contradicts the assumption.
Now there are two cases.
-
$|w_A|\ge P(A)$. Since $P(A)$ is a pumping length for $A$, $w_a\in A$ can be written as $w_a=xyz$, satisfying the following conditions:
- $|y|\geq 1$
- $|xy|\leq P(A)$
- $\forall n\geq 0, xy^{n}z\in A$
Hence, $w$ can be written as $w=xyz_B$, where $z_B=zw_B$, satisfying the following conditions:
- $|y|\geq 1$
- $|xy|\leq P(A) + P(B)-1$ (since $P(B)\ge1$)
- $\forall n\geq 0, xy^{n}z_B=(xy^nz)w_B\in AB$.
That is, $w$ can be pumped with pumping length $P(A)+P(B)-1$.
-
$|w_B|\ge P(B)$. This case is similar to the case above.
Combining the two cases, we have proved $P(A)+P(B)-1$ is a pumping length for $AB$.
Let $A=\{\epsilon,\alpha, \alpha^2, \cdots, \alpha^{n-1}, \beta^n, \beta^{2n}, \beta^{3n}, \cdots, \}$, which is a regular language of minimal pumping length $n$. Let $B=\{\epsilon,\alpha, \alpha^2, \cdots, \alpha^{m-1}, \beta^m, \beta^{2m}, \beta^{3m}, \cdots\}$, which is a regular language of minimal pumping length $m$. Since $\alpha^{n-1}\alpha^{m-1}$, which is a word in $AB$ of length $n+m-2$, cannot be pumped, $AB$ is a regular language of minimal pumping length $n+m-1$.
Context
StackExchange Computer Science Q#126803, answer score: 3
Revisions (0)
No revisions yet.