0
$\begingroup$

I have a question to find out that L = {a^(2k)|k>=1} is regular. I know that it is regular set but I was looking to find out if pumping lemma is satisfying or not. So I tried it as -

Let # of states in the FA be n & I select the string w = a^2n
Now let xyz = w
xy = a^n
y = a^m | m is odd number
now x(y^2)z = a^(n-m)(a^2m)(a^n) 
= a(2n+m) does not belong to L

which says this regular set doesn't satisfy pumping property. Please let me know if I am doing something wrongly.

Thanks in advance.

$\endgroup$
1

1 Answer 1

0
$\begingroup$

The pumping lemma says that every (long-enough) string in a regular language can be divided in some way such that it can be pumped (subject to the other stated conditions).

Note that the statement is that every string has at least one way of dividing it up. Not every division of a string necessarily works. As you have shown, some don't work, however there is a different division (any one where $m$ is even) that does work. So the language does satisfy the pumping lemma.

$\endgroup$
0

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