# Subset of regular language $a^*$

Given $L\subseteq a^*$, then

1. $L$ is definitely decidable
2. $L$ is definitely Turing – recognizable
3. $L$ may not be Turing – recognizable.
4. $L$ is regular

My attempt:

$L$ may not be regular, regular languages not closed under subset property $(L=a^{n^2})$.

$L$ can be CSL, so option $(2)$ can be true.

If $L$ is REC(Recursive) then option $(1)$ will be true.

If $L$ is RE(Recursively enumerable) then option $(2)$ will be true.

But, I stuck for $L$ : Is it RE or REC? Can you explain, please?

## 1 Answer

Let $S \subseteq \mathbb{N}$ not be $RE$.

Take $L = \{ a^n \ | \ n \in S \}$.

Then $L$ is not $RE$.

You can also construct explicit examples of such sets, like $L = \{ a^n \ | \text{ The } n^{\text{th}} \text{ Turing machine halts on all inputs} \}$.

To go even further, any infinite set has subsets which are not $RE$. Let $A \subseteq \mathbb{N}$ be an infinite set. If $A$ is not $RE$ take $L = A$. If $L$ is $RE$, then a Turing machine exists which enumerates the elements of $A$. let $a_0, a_1 \dots$ be the sequence enumerated by such a Turing machine. Then take $L = \{ a_n \ | \text{ The } n^{\text{th}} \text{ Turing machine halts on all inputs} \}$. If $L$ is $RE$, then we can recognize the set of Turing machines which halt on all inputs as follows: Given a Turing machine encoded as an integer $n$, compute $a_n$ and check if it is in $L$. Hence $L$ is not $RE$.

• Thanks for nice explanation. – Mithlesh Upadhyay Jun 13 '16 at 13:43