My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given

$$ L = \{ a^k b a^{m-1} \mid k,m \in \mathbb{N} \} $$


  1. How does $m-1$ affect my choice of the word to be pumped? There must be a way to rule out $m=0$ because otherwise my length would be negative.
  2. Would it be wrong to choose $w = a^{n-1}ba^n$ with the intent of pumping down $y = b$?

Every answer is highly appreciated.

  • $\begingroup$ Your language is regular! $\endgroup$ – Yuval Filmus Feb 11 at 3:17

Your language is regular. You won't be able to prove that it's not regular using the pumping lemma.

Regarding your first question, you're right that the language is present in a sloppy manner. We should add the condition $m \geq 1$. We can then notice another way of writing the language: $$ L = \{ a^k b a^m \mid k,m \in \mathbb{N} \}. $$ This is just the language of the regular expression $a^*ba^*$.

The reason that you can't "pump down" the word $a^{n-1}ba^n$ is that you don't get to choose the decomposition of the pumping lemma. This word can be decomposed as $a^{n-2} . a . ba^n$ (we can force $n \geq 2$ by choosing the pumping constant), and then the middle part can be pumped down or up while keeping the word in $L$.


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.