Let $L$ be the set of all languages that satisfy the pumping lemma, including non-regular languages that satisfy it. Is the set $L$ closed under concatenation?
I couldn’t prove it or find a counterexample.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Suppose that $L_1$ satisfies the pumping lemma: there exists $p_1$ such that every word $w \in L_1$ of length at least $p$ can be decomposed as $w = xyz$, where $|xy| \leq p_1$, $y \neq \epsilon$, and $xy^iz \in L_1$ for all $i \geq 0$. Similarly, suppose that $L_2$ satisfies the pumping lemma, with constant $p_2$.
I claim that $L = L_1L_2$ satisfies the pumping lemma with constant $p = p_1 + p_2$. Suppose we are given a word $w = w_1w_2 \in L$ of length at least $p$, where $w_1 \in L_1$ and $w_2 \in L_2$. Then either $|w_1| \geq p_1$ or $|w_2| \geq p_2$. You take it from here.