# Converse of pumping lemma for regular expressions

I want to come up with a language that satisfies the pumping lemma while not being a regular expression.

I thought of $$\{0^i1^j: i > j > 0\}$$. The pumping seems to work just fine, and this is not a regular expression, as it would not be possible to create an automata that recognizes it. This last part is where I'm having a bit of trouble, as I think I have the right idea, but can't formalize it. This language is just a regular expression $$\big(\{0^i : i \in \mathbb{N}\}\big)$$ concatenated with something that is not a regular expression $$\big(\{0^i1^i: i \in \mathbb{N}\}\big)$$.

Is my thought process correct? Can this be generalized? If $$L$$ is a RE and $$L'$$ is not, then $$LL'$$ is also not a RE? I believe so, because we know that if $$L$$ is a RE then so is $$L^r$$. And so we end up with $$(L')^rL^r$$, and we can use the contrapositive of the pumping lemma to prove this language is not regular. Any insight would be helpful!

Yes, $$L_>=\{0^i1^j: i > j > 0\}$$ is a non-regular language.

However, it does not satisfy the pumping lemma for regular languages. Assume for the sake of contradiction that $$p$$ is a pumping length for $$L_>$$. Consider $$w=0^{p+1}1^p$$. Let $$w=xyz$$ with $$|y|>1$$ and $$|xy|. Then $$y$$ contains 0 only. There is no more 0's than 1's in $$xy^0z=xz$$. That contradicts that $$p$$ is a pumping length.

The most we can say is that all words in $$L_>$$ can be pumped up.

If $$L$$ is a RE and $$L'$$ is not, then $$LL'$$ is also not a RE?

No. A simple counterexample is $$L=\Sigma^*$$, the language of all words while $$L'$$ is any non-regular language that contains the empty word such as $$\{a^{n^2}\mid n\in \Bbb N_0\}$$. $$LL'$$ is still the language of all words, which is regular.

Exercise 1. Find two languages $$A$$ and $$B$$ such that

• $$A$$ is regular
• $$B$$ is not regular
• $$A\subsetneq B$$
• $$AB$$ is regular.

Exercise 2. Find a non-regular language that satisfies the pumping lemma for regular languages.

• Thank you for your answer, apreciate it a lot! In regards to Exercise 1, if you choose A = $\varnothing$, then I believe it works :) – mathmathmath Jun 29 at 18:29
• @mathmathmath nice answer. To make it more difficult, I should have added $A$ is not empty. – Apass.Jack Jun 29 at 19:30

For a language that isn't regular, but satisfies the pumping lemma, take:

$$L = \{a b^r c^r \colon r \ge 1\} \cup \{a^r b^s c^t \colon r \ne 1 \wedge s, t \ge 1\}$$

Given $$\sigma = a b^r c^r$$, you can pump the starting $$a$$, the result is always in $$L$$. Given a string that starts with no $$a$$, you can pump some starting $$b$$s; if it starts with 2 or more $$a$$, you can repeat the first two $$a$$s at will.

Suppose $$L$$ is regular. Then $$L \cap \mathcal{L}(a b^* c^*) = \{a b^r c^r \colon r \ge 1\}$$ is regular, but an easy use of the pumping lemma shows this not to be the case.