Question

For Σ={ a, b} let us consider the regular language
L = $\{x\mid x=a^{2+3k}orx=b^{10+12k},k\ge 0\}$ Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma ) for L?

• A. 24
• B. 9
• C. 5
• D. 3

Answer 1

The correct option is A 24

$L=\left\{a^{2+3k}or{b}^{10+12k}\right\}fork\ge 0$

$=a^2\left(a^3{)}^{\ast }or{b}^{10}\right(b^{12}{)}^{\ast }$

$=\{a^2,a^5,a^8,...,b^{10},b^{22},b^{34}....\}$


The pumping length is p, than for any string w $ϵ$ L with $\mid w\mid \ge p$ must have a repetition i.e. such a string must be breakable into w = xyz such that $\mid y\mid \ge 0$ and y can be pumped indefinitely, which is same as saying xyz $ϵ$ L

$\Rightarrow x{y}^{\ast }zϵL.$

The minimum pumping length in this language is clearly 11, since $b^{10}$ is a string which has no repetition number, so upto 10 no number can serve as a pumping length. Minimum pumping length is 11. Any number at or above minimum pumping length can serve as a pumping length. The only number at or above 11, in the choice given is 24.

So correct answer is option (b).