形式0^n（nは素数）の言語が規則的でも文脈自由でもないことを証明する

Question

私はかなり長い間これを考えていますが、それでもまだ遠くには行けませんでした。 最初のステップは、フォームo^Mの任意の言語を考慮すると簡単です。ここでMは、相手が与えたものよりも大きいプライムです（nと言うことができます）。私たちがここからどのように証明できるかを理解することはできません。相手は文脈自由言語のクラスに属していないことを示すために私たちはいつもそれを汲み上げることができる文字列を壊します。

PS：宿題に関する質問ではありません。私はすでにこのコースを修了しています。コース期間中に解決できなかったので、それを解決しようとしています。

Answer 1

与えられた言語が文脈自由であるとします。 pumping lemma for context-free languagesを使用すると、x、x + y、x + 2y、x + 3yなどがすべて素数であるようなxとyの数値が得られます。しかし、これは可能ではない。なぜなら、素数間の任意の大きなギャップが存在するからである（これを証明するためには、任意の自然数n> = 2に対してn！+2、n！ 2 - それらはすべて複合です）。

もう1つのアプローチは、単一アルファベットを超える文脈自由言語がすべて正規言語であるという定理を使用することです。次に、単一アルファベットのDFAがどのように見えるかを考えてみましょう。到達不能状態を除去した後、状態はq_0、q_1、... q_kでなければならず、q_iからq_ {i + 1}への遷移は1 < = i < kであり、q_kからの遷移はある状態になる。 q_0は初期状態です。選択された最終状態セットに関係なく、これは{0^n | nは素数です} - 矛盾を得るために素数間に任意の大きなギャップがあるという事実を再び使用します。