4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ related: a question to find a non-regular language that satisfies the pumping lemma: cs.stackexchange.com/a/9182 . Actually the construction I gave there allows arbitrarily complex languages. $\endgroup$ – Hendrik Jan Dec 13 '18 at 0:48
4
$\begingroup$

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.

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