Question

I came across following problem:

Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine
$L_1 =\{M|M$ accepts at most 2016 strings$\}$
$L_2=\{M|M$ accepts at least 2016 strings$\}$
If $L=L_1\cap L_2$, then which one of the below is correct?
A) $L'$ is recursively enumerable
B) $L\cap L'$ is recursively enumerable
C) $L\cup L'$ is recursively enumerable
D) $L$ is recursively enumerable

The solution given was:

$L_1$ by definition is regular language (“atmost”). $L_2$ by definition is recursively enumerable (“at least”). Recursively enumerable languages are closed under regular intersection. Hence, $L = L_1 ∩ L_2$ is recursively enumerable. Thus option D. Recursively enumerable languages are not closed under complementation. Hence $L’$ is not recursively enumerable. Hence option A is wrong. And since $L’$ is not recursively enumerable, options B and C are also wrong.

My doubt

I am struggling with how $L_1$ is regular and $L_2$ is recursively enumerable, that is with first two sentences:

$L_1$ by definition is regular language (“atmost”). $L_2$ by definition is recursively enumerable (“at least”).

Usually language definition specifies criteria on format of input string which will allow us to reject or accept it. But here the definition specifies how many strings the language has or its corresponding Turing machine accepts.

I found this similar sounding problem, in which the answer gives membership algorithm and hence proving language in that problem is indeed recursively enumerable. But I feel this does not applies in my problem. Correct? Or the problem is incorrect in telling number of strings languages can accept instead of format of acceptable strings?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top