Automata – Pumping Lemma for Union of Regular Languages

automatapumping-lemmaregular-language

In the question, we have regular languages L1, L2 with the constant of the pumping lemma – n1,n2.
Also, we have the language L = L1 + L2 with the constant n of the pumping lemma.
I need to prove that n <= max(n1,n2)
I'm really having trouble doing so.
Any help will be much appreciated!

Best Answer

Say that $m$ satisfies the pumping property for a language $L$ if the following holds :

pumping property for $L$ : For every word $w$ in $L$ of length at least $m$, $w$ can be written as $w = xyz$ where :
$|y| \geqslant 1$
$|xy| \leqslant m$
$\forall k \geqslant 0, \ xy^kz \in L$

Let $m := \max(n_1, n_2)$. We show that $m$ satisfies the pumping property for $L_1 \cup L_2$ :

Indeed, let $w \in L_1 \cup L_2$, then either $w \in L_1$ or $w \in L_2$. If $w \in L_1$, then since $n_1$ satisfy the pumping property for $L_1$, $m$ also satisfies the pumping property for $L_1$ (since $n_1 \leqslant m$). Hence we can write $w=xyz$ as required. Likewise if $w \in L_2$. QED

Now, $n$ just happens to be the minimum of all $p$s satisfying the pumping property for $L_1 \cup L_2$, hence $n \leqslant m = \max(n_1, n_2)$.