1
$\begingroup$

If I have two languages L1 and L2 that are pumpable, what is the minimum pumping length for the union of them?
Does it differ if either of them contains just one string like 001?

$\endgroup$
1
  • $\begingroup$ Are the languages regular, or at least context-free? And what is meant by "detecting just one string", that the language is singular (that is, having just one element)? $\endgroup$
    – Eugen
    Nov 11, 2018 at 20:05

1 Answer 1

2
$\begingroup$

Consider the following two languages: $$ L_0 = 1(0+1)^* + 0^{n_0}, \\ L_1 = 0(0+1)^* + 1^{n_1}. $$ The minimum pumping length of $L_0$ is $n_0 + 1$, and that of $L_1$ is $n_1 + 1$. Yet $L_0 \cup L_1 = (0+1)^+$ has a minimum pumping length of 1.

What does hold is that the pumping length of $L_0 \cup L_1$ is at most the maximum of the pumping lengths of $L_0,L_1$. In fact, it can be any number between 1 and that maximum. Indeed, suppose that $1 \leq a,b \leq c$, and consider the languages $$ \begin{align*} L_0 &= 1(0+1)^* + 0^{a-1}, \\ L_1 &= 0(0+1)^* + 1^{c-1} + 2^{b-1}. \end{align*} $$ The maximum pumping length of $L_0$ is $a$, that of $L_1$ is $c$, and that of $L_0 \cup L_1 = (0+1)^+ + 2^{b-1}$ is $b$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.