computer-science - {a^n | n >= 0} および {a^p | p = 素数} 規則的ではありませんか?

Question

CSコースでは、次の例があります{a^n | n >= 0}。{a^p | p = prime number}

それらの言語は規則的ですか？ポンピング補題の矛盾を作れる人はいますか?

Answer 1

ハロルドの言うとおりだ。この例

a^n|n>=0

は正規言語です。

2番目の例

{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 であるため) ため、競合が発生するため、この言語は規則的ではありません。