0
$\begingroup$

I am solving basic questions about Recursive and Recursively-Enumerable languages. I know that base on the below theorem, to prove that a language is RE we should define an Enumeration Procedure for it.

A language is recursively enumerable if and only if there is an enumeration procedure for it.

And for the below question, I said that if $L$ is finite, it means that it is countable and for every $w ∈ L $, $|w|$ is also finite (I am not sure about this). So we can write $L$ in the below form:

$L = \{w ∈ L | y \geqslant|w| \geqslant x \} $

But I can not understand how to implement a procedure for it to enumerate all the strings in $L^+$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

First start with a related task: enumerate all (finite) sequences of natural numbers. We will devide those sequences into a sequence of finite sets, and then we can enumerate all sequences by taking the sets one after another and enumerating the items in those sets.

Note that we cannot enumerate first all sequence of length one, then of length two, etcetera. Each of those sequences is infinite and does not end. So we have to weave the infinite sequences of infinite length into one single sequence. The process is called dovetailing.

For every sequence of numbers $(n_1, n_2, \dots, n_k)$ let the complexity of the sequence be the maximum of the length of the sequence and the numbers involved: $\max \{k, n_1, n_2, \dots, n_k\}$. Now each sequence has a complexity, and we can enumerate the sequences by increasing complexity. Starting with the empty sequence, sequences of one integer that can only be $0$ or $1$, etcetera.

The task of enumerating $L^+$ is simular. If the language $L$ is enumerable, then there is a procedure that lists its elements, $x_0, x_1,x_2,x_3, \dots$. In that way we assign a number to each word. Then sequences of numbers map to sequences in $L^+$, and we can enumerate in that way. Thus $(5,2,2,0)$ maps to $x_5\cdot x_2\cdot x_2\cdot x_0$.

Note that we will possibly find some strings in $L^+$ several times, as the decomposition might not be unique (eg., $ab \cdot a = a \cdot ba$). For enumeration that is ok, but you can drop duplicates if you want.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I did not completely understand the meaning of "First enumerate L, that is we assign a number to each word". $\endgroup$
    – Aylin Naebzadeh
    Commented Jun 17, 2022 at 13:58
  • $\begingroup$ But in enumerating L, we will have strings with lengths from $x$ to $y$. And after $L$, can we enumerate $L^2$, then $L^3$, etc? $\endgroup$
    – Aylin Naebzadeh
    Commented Jun 17, 2022 at 14:00
  • 1
    $\begingroup$ If $L$ itself is finite then we can first enumerate $L$, then $L^2$ etcetera. If $L$ on theo other hand is infinite that would not work, and we enumerate them in growing "complexity" for some measure of complexity such that each complexity is finite. I started here with simple numbers as that is intuitively simpler. I think. $\endgroup$
    – Hendrik Jan
    Commented Jun 17, 2022 at 14:11
  • $\begingroup$ Yes fortunately $L$ is finite, but you mentioned that we can remove the duplicates, how we can do that? $\endgroup$
    – Aylin Naebzadeh
    Commented Jun 17, 2022 at 14:13
  • $\begingroup$ We remove duplicates in the most simple way. We look into the list of already generated strings and just check whether we have seen the new string before. If not, we add it. Otherwise we drop the string. $\endgroup$
    – Hendrik Jan
    Commented Jun 17, 2022 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.