语言L1={a^p|p为非素数且p≥0}是否属于递归可枚举语言？

你提到的判断是完全成立的：L1确实是递归可枚举语言，同时不属于正则语言、也不属于上下文无关语言，具体推导如下：

1. L1属于递归可枚举语言的证明 #

L1是L2和L3的差集，本质就是{a^m | m≥0，且m不是素数}，也就是L3相对于全集L2（a的任意次幂串集合）的补集。
首先明确：素数集合是可判定集合，我们可以构造一个确定性算法，在有限步骤内判断任意给定的非负整数是不是素数，因此L3本质属于递归语言，递归语言对补运算封闭，因此L1也是递归语言，而所有递归语言都属于递归可枚举语言，因此L1自然满足递归可枚举的属性。

2. L1不属于正则语言的证明 #

正则语言类对补运算封闭，如果L1是正则语言，那么它的补集L3（素数长度的a串集合）也必然是正则语言，我们可以用正则语言泵引理推翻这个假设：

• 假设L3是正则语言，存在泵长度p
• 取一个大于p的素数q，构造字符串s = a^q，显然s属于L3
• 根据泵引理，s可以拆分为xyz三部分，满足|xy| ≤ p、|y| ≥1，且对任意非负整数i，xy^i z都属于L3
• 设y的长度为k（k≥1），那么xy^i z的长度为 q + (i-1)k
• 当i = q + 1时，字符串长度为q + qk = q(k+1)，显然是合数，对应的字符串不属于L3，和泵引理的要求矛盾
  因此L3不是正则语言，推导可得L1也不可能是正则语言。

3. L1不属于上下文无关语言的证明 #

形式语言领域有明确的已证明结论：一元字母表（仅包含一个字符的字母表）上的所有上下文无关语言都是正则语言。
我们已经证明L1不是正则语言，因此它自然也不属于上下文无关语言。

内容的提问来源于stack exchange，提问作者Franklin Choi