是 {a^n | n >= 0} 和 {a^p | p = 素数} 不规则？
Are {a^n | n >= 0} and {a^p | p = prime number} not regular?
在 CS 课程中，我有以下示例：{a^n | n >= 0} 和 {a^p | p = prime number}
这些语言是否正规？有没有人可以提出泵引理矛盾？
正如哈罗德所说。这个例子
a^n|n>=0
是一种常规语言，它是*。
第二个例子
{a^p | p = prime number}
正如抽取引理所说，N = p -> 我们的单词将是 a^N。所以，根据定义 |uv|< N 我们可以选择 u=a^p (p>=0) 和 v=a^s (s>=1)。世界其他地方将是我们的 w=a^(N-p-s)。
定义说，uv^mw (m>=0) 必须在语言中。我们可以选择m=N+1。
u*v^(N+1)w = a^pa^(s*(N+1))*a^N-p-s = a^N(S+1)
有冲突，因为a^N(S+1)不是质数（因为除数肯定是S+1），所以这个语言不正则
在 CS 课程中，我有以下示例：{a^n | n >= 0} 和 {a^p | p = prime number}
这些语言是否正规？有没有人可以提出泵引理矛盾？
正如哈罗德所说。这个例子
a^n|n>=0
是一种常规语言，它是*。
第二个例子
{a^p | p = prime number}
正如抽取引理所说，N = p -> 我们的单词将是 a^N。所以，根据定义 |uv|< N 我们可以选择 u=a^p (p>=0) 和 v=a^s (s>=1)。世界其他地方将是我们的 w=a^(N-p-s)。 定义说，uv^mw (m>=0) 必须在语言中。我们可以选择m=N+1。
u*v^(N+1)w = a^pa^(s*(N+1))*a^N-p-s = a^N(S+1)
有冲突，因为a^N(S+1)不是质数（因为除数肯定是S+1），所以这个语言不正则