1

G の言語が nil であるような文脈自由文法 G がある場合、G は決定可能ですか?

答えがイエスであることはわかっていますが、これを証明するのに苦労しています。私が最初に考えたのは、q1 という 1 つの状態しかないということです。これは、G に相当するチューリング マシンの開始状態と受け入れ状態です。このマシンは、入力を受け入れず、受け入れに達したため、すぐに停止して受け入れます。州。これは受け入れられる答えですか、それとも私はここから離れていますか?

編集：

Joel が以下で述べたように、私が説明した言語はすべての文字列を受け入れます。これに対抗するために、私は 2 番目のマシン G' を提案します。G' には、開始状態 q1、受け入れ状態 q2、拒否状態 q3 の 3 つの状態があります。q1 は G' のアルファベットのすべてのシンボルで q3 に遷移し、q2 も同様です。q1 から q2 へのイプシロン遷移があります。したがって、G' に供給される文字列に記号が存在する場合、G' は拒否します。シンボルがない場合、唯一のオプションはイプシロン遷移を受け入れ状態にすることです。それはどのように聞こえますか？

編集：

上記の解は、言語 L(G') = {""} を受け入れることが証明されました。

4

1 に答える 1

1

あなたが言ったように、答えはイエスです。一般的な証拠は、CFG Gが与えられれば、その文法を使用して派生をシミュレートする TM を簡単に (まあまあ) 構築できるという事実です。ただし、空の言語の短い証明を探しています。(この場合、CFG があるという事実は関係ありません。)

特定の言語 L に対して常に停止する TM を構築できる場合、L は決定可能であるという点で、正しい方向に進んでいます。ただし、あなたが記述したマシンは、実際にはすべての文字列、つまりアルファベットのすべての可能な文字列で構成される言語を受け入れます。これは、開始状態も受け入れ状態である場合、チューリング マシンは開始時にすぐに受け入れられるためです。入力文字列全体 (またはその一部) を読み取る必要はありません。

何も受け入れない TM を定義するには、受け入れ状態のセットを空にします。マシンが常に停止することを保証するために、遷移関数も空にすることができます。

于 2011-03-22T06:05:59.233 に答える