I have to proof that $L = \{ a^{2i} b^{2j} \mid i,j \in \mathbb{N} \}$ is a regular language, and how it meets the Pumping Lemma condition.

For the PL, there is a string $xyz \in L$ such that $y \neq \epsilon$ and any string $xy^nz$, for any $n \ge 0$, is in $L$.

From what I understand, I cannot use the pumping lemma to prove that a language is regular.

I am a bit puzzled how I have to show that this $L$ meets this condition. Do I have to divide a string into $xyz$ again?

  • 1
    $\begingroup$ The proof of the pumping lemma shows that every regular language satisfies the conditions of the pumping lemma. In fact, the pumping lemma states that every regular language satisfies the conditions of the pumping lemma. This is the contents of the pumping lemma. $\endgroup$ – Yuval Filmus Apr 9 '20 at 10:48
  • $\begingroup$ I have to show by example that this language satisfies the PL condition. That's why I'm confused. What you are saying is true, but I'm not sure how this has to be proven by example? Thank you for your answer by the way! $\endgroup$ – ano Apr 9 '20 at 10:59

The language is regular since it is the language of the regular expression $(aa)^*(bb)^*$.

Every regular language satisfies the conditions of the pumping lemma – this is precisely the statement of the pumping lemma! So one way to show, from first principles, that this language satisfies the conditions of the pumping lemma would be to just repeat the proof of the pumping lemma.

However, in this case we can show this more directly. We will show that the pumping lemma holds with a pumping constant of $p = 2$. Suppose that $w = a^{2i} b^{2j} \in L$. Note that $|w| \geq 2$. We consider two cases:

  • Case 1: $i \neq 0$. In this case, we can break $w$ in the following form: $x = \epsilon$, $y = a^2$, $z = a^{2(i-1)} b^{2j}$. We have $w = xyz$, $|xy| = 2 \leq p$ and $y \neq \epsilon$. For every $n$, $xy^nz = a^{2(i-1+n)} b^{2j} \in L$.

  • Case 2: $i = 0$. In this case, $j \neq 0$. We break $w$ into $x = \epsilon$, $y = b^2$, $z = b^{2(j-1)}$. The rest of the proof is very similar.

  • $\begingroup$ Wonderful explanation! Thank you. The only part I am struggling is when you use exponents like $a^2(i-1). I understand your explanation, but I'm just a tiny bit struggling with this. I've never seen exponents used like this before. Can you perhaps explain this to me? If not, do you have any recommendations on youtube videos/readings to look at in order to comprehend this? $\endgroup$ – ano Apr 10 '20 at 12:33
  • $\begingroup$ The notation $w^n$ means the word $w$ repeated $n$ times. In $a^{2(i-1)}$, we have $w = a$ and $n = 2(i-1)$, so it's the word $a$ repeated $2(i-1)$ times. $\endgroup$ – Yuval Filmus Apr 10 '20 at 12:38
  • $\begingroup$ Ah I see. And how should I interpret i-1? how come you have to substract it by 1? and can you maybe explain why you broke w in the form given xyz form? why is x specifically chosen to be empty? I'm sorry if these are all beginner questions. Our teachers are not easily accessible due to the coronavirus crisis and we are all kind of left to fetch for ourselves. Thank you for taking the time to help me out. $\endgroup$ – ano Apr 10 '20 at 12:45
  • $\begingroup$ The notation $w^n$ only makes sense for integer $n \geq 0$. Fortunately, once I assume that $i \neq 0$, it follows that $i \geq 1$, and so $a^{2(i-1)}$ makes perfect sense. $\endgroup$ – Yuval Filmus Apr 10 '20 at 12:47
  • $\begingroup$ As to why I chose this particular decomposition, there is no good reason. There are other decompositions which could have worked (depending on the values of $i,j$). You might want to work out the full range of decompositions that work. In proofs there is often a lot of freedom. It's not like high school math. $\endgroup$ – Yuval Filmus Apr 10 '20 at 12:48

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.