What is Pumping length for Union of Regular languages? This is an exam question.
For E = {a,b}. let us consider the regular language
$L= \{x|x = a^{2+3k} or x=b^{10+12k}, k &gt;= 0\}$
Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
A)3
B)9
C)5
D)24
Ans is 24.
As per me pumping length is the length which gets actually repeated.
So, basically it's the length of y as per pumping lemma statement.
Now, for the first regular language, $a^{2+3k}$
How I visualized?
There would be sure 2 states which accept min 2 'a' ( since k&gt;=0).
Now, then I have $a^{3k}$
Means, which should definitely have a loop of length 3.
So, I choose x=2 (first 2 states) y=3 (the repeating part) and z=0.
So this first language must have atleast 3 as the pumping length.
And in similar lines the other must have. Atleast 12 as pumping length.
(X=10, y=12, z=0)
And that's why as per me 24 is right.
(Still sketchy at concluding)
Plz tell me if my understanding of Pumping length is right?
If no plz try suggesting some links/references.
If yes then have I applied the Concept right?
A pumping length is a positive integer $p$ such that any string of $L$ of length at least $p$ can be decomposed in the form $xyz$ with $|xy|\leq p$, $|y|&gt;0$ and for all $n\geq0$ the words $xy^nz$ are in $L$.
Assume that $p&lt;12$. Then the word $b^{10+12}$ should be able to be decomposed as above. We cannot take $y$ with $1\leq|y|\leq p &lt;12$. Otherwise $xz=xy^0z$ wouldn't be in $L$.
We can take $p=12$ or larger.
If $10+12k=|b^{10+12k}|\geq p\geq 12$ then $k\geq1$ and we can decompose $b^{10+12k}$ as $xyz$, with $x=\epsilon$, $y=b^{12}$ and $z=b^{10+12(k-1)}$. Then $|xy|=12\leq p$ and for all $n\geq0$ we have $xy^nz=b^0b^{12n}b^{10+12(k-1)}=b^{10+12(n+k-1)}$ in $L$, since $n+k-1\geq k-1\geq0$
If $2+3k=|a^{2+3k}|\geq p\geq 12$, then $k\geq4$. We can decompose $a^{2+3k}$ as $xyz$ with $x=\epsilon$, $y=a^3$ and $z=a^{2+3(k-1)}$. We have that $|xy|=3\leq p=12$, $|y|=3\geq1$ and for all $n\geq0$ we have $xy^nz=a^0a^{3n}a^{2+3(k-1)}=a^{2+3(n+k-1)}$ in $L$, since $n+k-1\geq k-1\geq0$.
So, the minimum pumping length of $L$ seems to be $12$. Any larger value would also work in this case.