NIL言語を使用しているCFGは決定可能ですか？

Question

gの言語がゼロであるようにコンテキストフリーの文法gを持っている場合、gは決定できますか？

答えはイエスだと知っていますが、これを証明するのに苦労しています。私の最初の考えは、Gに相当するチューリングマシンのスタート状態であり、受け入れた状態であるQ1のみが1つしかないということです。州。これは受け入れられる答えですか、それとも私はここから離れていますか？

編集：

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

編集：

上記のソリューションは、言語l（g '）= {""}を受け入れることが証明されました。

Answer 1

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

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

何も受け入れないTMを定義するには、受け入れる状態のセットを空にします。マシンが常に停止することを保証するために、移行機能も空になる可能性があります。