6

受け入れ状態がマークされていないときに Turing Machine T, ACCEPTS がマークされ、受け入れ状態がマークされているときに拒否する理由がわかりません。

E(dfa) = {| A は DFA であり、L(A) = 空集合 (記号を持たない)}

E(dfa) は決定可能な言語です。

証明: DFA は、DFA の矢印に沿って移動することによって、開始状態から受け入れ状態に到達する場合、何らかの文字列を受け入れます。この条件をテストするために、例 3.23 で使用したものと同様のマーキング アルゴリズムを使用する >TM T を設計できます。

T= "入力時、ここで A は DFA です: 1. A の開始状態をマークします。 2. 新しい状態がマークされなくなるまで繰り返します: 3. 既にマークされている状態から移行する状態をマークします。 . 4. 承認状態がマークされていない場合は承認し、それ以外の場合は拒否します。

これは私には逆に思えます。誰でもこれを説明できますか？

ありがとうございました。

4

1 に答える 1

8

あなたの混乱は、「受け入れる」と「拒否する」という言葉が異なる文脈で使用されていることに起因すると思います。大まかに言うと、この混乱を避けるのは簡単です。チューリング マシンTを定義して、DFA であるAが独自に承認と拒否を行うプロセスを参照しないようにすることができるからです。

L( T ) は { A | L( A ) は空です}。これはあなたの質問で定義された E(dfa) と同じですが、 L( T ) を使用すると、ここで 2 つの別々の言語を扱っていることがより明確になります。

高レベルから低レベルに作業すると、次のように言えます。

  • L( T ) は、L( A ) が空のときはいつでも A を受け入れます。
  • しかし、L( A ) が空かどうかはどうやって判断するのでしょうか? Aがすべての文字列を拒否すると、 L( A ) は空になります。
  • 文字列がAで拒否されたことをどのように知ることができますか? 受理状態で終わらない。

低から高まで非常に簡単に作業することもできます。

  • Aに与えられた文字列が受け入れ状態で終わらない場合、それは拒否されます。
  • すべての文字列がAによって拒否される場合、 L( A ) は空です。
  • L( A ) が空の場合、 L( T ) はAを受け入れます。

TがAを受け入れるかどうかを決定する方法について、あなたの証明はもう少し詳細になりますが、あなたの混乱は、受け入れと拒否の複数の使用に関連していると思います。非常に大まかに言うと、 Aがすべてを拒否する場合、 TはAを受け入れると言えます。

于 2014-03-07T23:04:55.677 に答える