私はこれについてかなり長い間考えていますが、それでもそれについては遠くまで行くことができませんでした。最初のステップは、形式o ^ Mの言語を考えると簡単です。ここで、Mは、対戦相手が与えたものよりも大きい素数です（たとえばn）。ここから、対戦相手がどのようであっても、どのように証明できるかわかりません。文字列を壊して、文脈自由言語（したがって正規言語）のクラスに属していないことを示すために、いつでもそれをポンピングできます。
PS：宿題の質問ではありません。私はすでにこのコースを完了しています。コース期間中に解決できなかったので、解決しようとしています。
与えられた言語が文脈自由であると仮定します。文脈自由言語のポンピング補題を使用すると、x、x + y、x + 2y、x+3yなどがすべて素数になるような数xとyが得られます。ただし、素数の間には任意に大きなギャップがあるため、これは不可能です（これを証明するために、任意の自然数n> =に対して、数n！+ 2、n！+3、.... n！+nを考慮してください。 2-それらはすべて複合です）。
別のアプローチは、単項アルファベット上のすべての文脈自由言語が正規言語であるという定理を使用することです。次に、単項アルファベット上のDFAがどのように見えるかを検討します。すべての状態に1つの出力エッジがあります。到達不能な状態を排除した後、状態はq_0、q_1、... q_kである必要があります。ここで、q_iからの遷移は1 <= i <kの場合、q_ {i + 1}になり、q_kからの遷移はある状態になります。q_0は初期状態です。選択した最終状態のセットに関係なく、これは{0 ^ n | nは素数です}-ここでも、矛盾を得るために素数の間に任意に大きなギャップがあるという事実を使用します。