Language that fulfills pumping lemma but is not in RE

Question

I am supposed to find a language $$L\subseteq \Sigma ^*, \Sigma \subseteq \mathbb{N}$$ that fullfills the pumping lemma and is not in RE and not in coRE. I've never constructed a language with a given constraint, I've only shown that a certain language satisfies a given one. Not wanting to waste a bunch of time guessing some languages and prooving that they meet my criteria, I am looking for a hint on how to start.

Answer 1

Usual pumping lemma

Here is an answer when we are talking about the usual pumping lemma for regular languages that is taught in most introductory courses of computation theory.

Let alphabet $\Sigma=\{0,1\}$. Let $L$ be a non-recursively enumerable language over $\Sigma$. For example, $L$ can be the complement language of a semi-decidable but not decidable language such as $\overline{\{ \langle M \rangle \mid \text{ $M$ halt on empty input}\}}.$

Let $L'=\{00w\mid w\in L\}\cup\{01w\mid w\not\in L\} $. Then both $L'$ and $\overline {L'}$ are non-recursively enumerable languages.

Let $F=\{ 1w \mid w\in L' \} \cup \{ 1^kw \mid k\neq 1, w\in \Sigma^* \}$, following the construction in an answer by Hendrik Jan. Then $F$ is not in RE and not in coRE since its first part is not in RE and not in coRE while its second part is regular. It satisfies the usual pumping lemma for regular languages, since its second part is regular while its first part can be pumped down and up "into" its second part by choosing the first 1 to pump.

General pumping lemma

Here is an answer when we are talking about the general (or generalized) pumping lemma for regular languages.

Let alphabet $\Sigma_4=\{0,1,2,3\}$. Let $D$ be the finite language whose words are of length 3 and having a duplicate character. (In fact, $D$ has $4+4\times3\times3=40$ words.) Let $P=\Sigma_4^*\bullet D\bullet\Sigma_4^*$, the languages of all words that contain a substring in $D$. $P$ is a regular language. Any language over $\Sigma_4$ that contains $P$ satisfies the general pumping lemma.

Let $N$ be a language that is not in RE and not in coRE. For example, we can select language $L'$ constructed in previous section. Then $G=P\cup N$ is a language not in RE and not in coRE that satisfies the general pumping lemma.

---

Here are several exercises that readers can do so as to fill the gaps in the above sections.

Exercise 1. Show the class of non-recursively enumerable languages is closed under concatenation with a fixed string at the front.

Exercise 2. Show the class of non-recursively enumerable languages is closed under union with a regular language.

Exercise 3. Show any language over $\Sigma_4$ that contains $P$ satisfies the general pumping lemma.