0

これについてどうやって行くかについて私にいくつかのアイデアを教えてください

少なくとも4つの重要な（つまり、拒否されない）状態と少なくとも6つの重要な（つまり、拒否されない）遷移を持つチューリングマシンを（Sipser表記を使用して）描画します。

4

1 に答える 1

2

チューリングマシンには次のものがあります。

  • 有限数の状態。そのうちの1つは受け入れ、もう1つは拒否します。このタスクには、明らかに5つの状態（4つの非拒否（そのうちの1つは受け入れている必要があります）と1つの拒否）が必要です。州は通常、それぞれの中にラベル（州名）が付いた円として描かれます。状態の1つは開始状態です; それを指す矢印でマークされています。
  • 有限入力アルファベット。{0、1}または{a、b}が一般的な選択肢です。
  • 有限のテープアルファベット。これには、特別な空白の記号、入力アルファベットのすべての記号、および場合によってはさらに多くの記号が含まれます（ただし、これは必須ではありません）。
  • 状態とテープシンボルの各組み合わせに、状態、テープシンボル、および方向を割り当てる遷移関数。方向はL（左）またはR（右）にすることができます。遷移は、ある状態から別の状態への矢印（または状態からそれ自体に戻る円形の矢印）として描画され、矢印には2つのテープ記号とLまたはRのラベルが付けられます。明らかに、このような矢印は6つ必要です。

マシンには、セルに分割された無限のテープもあります。各セルには、テープアルファベットの記号を含めることができます。最初にテープにあるシンボルは、マシンへの入力と呼ばれます。マシンには、常にセルの1つに配置されている読み取りヘッドがあります。状態Aから状態Bへの遷移矢印があり、その上に記号a、b、およびRがあるとします。つまり、「マシンが状態Aにあり、テープヘッドの下の記号がaの場合、その記号をbに置き換え、状態Bに移動し、読み取りヘッドを1セル右に移動する必要があります。」

于 2011-02-24T20:14:35.707 に答える