# Pumping Lemma on Language with subtracted length

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} \}$$

Questions:

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.

• Your language is regular! – Yuval Filmus Feb 11 '19 at 3:17

## 2 Answers

You could argue with a reasonably straight face that L is not well-defined, since it supposedly contains the word $$a^0ba^{-1}$$, so L wouldn't be a language at all, therefore not a regular language and not an irregular language either.

If you change it slightly to $$L = \{ w: w = a^k b a^{m-1} \mid k,m \in \mathbb{N} \}$$ then it is definitely regular; there's a very simple FSM with just two states for it.

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$$.