0
$\begingroup$

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 >= 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>=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?

$\endgroup$
1
$\begingroup$

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|>0$ and for all $n\geq0$ the words $xy^nz$ are in $L$.

Assume that $p<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 <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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So you mean to say that pumping length is not y but it's basically the length of the least string that gets accepted by the regular language? $\endgroup$ – Piyush Sawarkar Jul 3 at 15:49
  • $\begingroup$ The least string for a^(2+3k) would be a^5, so is pumping length 5? I'm a bit confused here. $\endgroup$ – Piyush Sawarkar Jul 3 at 15:50
  • $\begingroup$ @PiyushSawarkar I meant to say what is written above, which I copied from the linked article, and which seems to be different from what you are saying. The smallest length of a string in $L$ is $2=|a^{2+3\cdot 0}|$. A pumping length for this language cannot be smaller than $12$ from the argument above. $\endgroup$ – NotDijkstra Jul 3 at 15:53
  • $\begingroup$ Okay so I got my mistake in previous msg, sorry for that. So basically am I right to say that 3k and 12k is the repeating part, and thus we took smartly 10+12k as 12k+10 and then splitted as 12 (bcoz it's the min repeating stuff) and 12+3(k-1) as the rest part. $\endgroup$ – Piyush Sawarkar Jul 3 at 17:00
  • $\begingroup$ And also basically pumping length p is any positive number which can have x and first repeating part of y. For example, in 01*0 the min pumping length will be 01 i.e. 2, am I correct? $\endgroup$ – Piyush Sawarkar Jul 3 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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