3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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

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

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.

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