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?
-
$\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$– EugenNov 11, 2018 at 20:05
1 Answer
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$.