1
$\begingroup$

I was asked to prove that language described by $$ L =\{ a^{2n}: n\ge1\}$$ is regular using pumping lemma. Pumping Lemma states that for regular language we can break down language described by language into $xyz$ where pumping length $p \ge 1$ such that

  1. $|y|>0$
  2. $|x.y| \le p$
  3. $x.y^{i}.z$ is in L for $i \ge 0$

taking pumping length $n = 3$ , my language becomes $L = \{ aaaaaa\}$ and then let $$x = aaa$$ $$y = aa$$ $$z= a$$

clearly this violates condition 2 because $|xy| > p$ where $p=3$ and it also violates condition 3 for many values of $i$ thus this language cannot be regular but in the question I was asked to prove it to be regular, am I missing something?

$\endgroup$
  • $\begingroup$ @ArghyaChakraborty why can't I choose n = 3 , isn't it arbitrary ? $\endgroup$ – Sigma Aug 7 '17 at 4:55
  • 3
    $\begingroup$ "I was asked to prove that [a language] is regular using pumping lemma." -- that's unlikely, since it's impossible. The pumping lemma can't be used in that way. $\endgroup$ – Raphael Aug 7 '17 at 5:44
  • $\begingroup$ Duplicate? $\endgroup$ – Raphael Aug 7 '17 at 5:45
  • $\begingroup$ @Sigma Forget my last comment. I was out of my mind. Anyways while proving not regular you have to prove for all $n$'s not just $n=5$ or something. And as the answer states, you can't use pumping lemma to prove language is regular. $\endgroup$ – User Not Found Aug 7 '17 at 7:55
  • $\begingroup$ Please check your assignment. Do you mean $\{ a^{2^n} \mid n\ge 1\}$? $\endgroup$ – Hendrik Jan Aug 7 '17 at 9:10
4
$\begingroup$

The pumping lemma states that if a language $L$ is regular then there exists an integer $p$ such that every word $w \in L$ of length at least $p$ has a decomposition $w = xyz$ such that $|xy| \leq p$, $|y| \geq 1$, and $xy^iz \in L$ for all $i \geq 0$.

Your language satisfies the pumping lemma, with $p = 3$ (as it must, since the minimal DFA contains 3 states). Indeed, let $w \in L$ be a word of length at least 3, so that $w = a^{2n}$ for some $n \geq 2$. Then $w$ can be decomposed as follows: $w = xyz$, where $x = \epsilon$, $y = a^2$, $z = a^{2n-2}$. Note that $|xy| = 2 \leq p$, $|y| = 2 \geq 1$, and for all $i \geq 0$, $xy^iz = a^{2n-2+2i} = a^{2(n-1+i)} \in L$ since $n \geq 2$.

The pumping lemma states that every long enough word $w \in L$ has some decomposition $w = xyz$ satisfying the requirements in the lemma. It doesn't claim that all decompositions satisfy the requirements.

$\endgroup$
3
$\begingroup$

Your language is regular. It is a set of even length $a$s expressed by the regular expression $r=aa(aa)^*$. The pumping lemma is used usually to prove that a language is not regular.

$\endgroup$

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.