computer-science - 是{a^n | n >= 0} 和 {a^p | p = 素数} 不规则？

Question

{a^n | n >= 0}在 CS 课程中，我有以下示例：{a^p | p = prime number}

这些语言是正规的还是不正规的？有没有人可以提出引理矛盾？

Answer 1

正如哈罗德所说。这个例子

a^n|n>=0

是一种常规语言，它是*。

第二个例子

{a^p | p = 素数}

正如抽引引理所说，N = p -> 我们的单词将是 a^N。因此，根据定义 |uv|< N 我们可以选择 u=a^p (p>=0) 和 v=a^s (s>=1)。世界其他地方将是我们的 w=a^(Nps)。定义说，u v^m w (m>=0) 必须是语言。我们可以选择m=N+1。

u*v^(N+1) w = a^p a^(s*(N+1))*a^Nps = a^N(S+1)

存在冲突，因为 a^N(S+1) 不是素数（因为除数肯定是 S+1），所以这种语言不规则。