Theoretical Computer Science

• このページは，理論計算機科学のメモ書きです。
• プラクティカルな情報は，ProgrammingとかSystemとかを参照してください。

• 非決定性ってのは，ある状態から次の状態への遷移方法が複数あること。
• 非決定性で受理するってのは，受理状態へ至る状態遷移のパターンが最低１通りあるってこと。
• 定義としては，状態遷移関数に違いが表れる。以下参照。

例えば， 以下のような状態遷移図で表される状態遷移関数（と各状態）を持つ機械について考える。

各状態から出て行く矢印を見ると，それぞれの状態から読み込まれた文字（矢印の近くの文字）によって遷移する状態は，ただ１つだけ決定される。例えば， から 1 を読み込んだときに から出て行く矢印は１本しかない。

ちなみに，この機械が受理する言語は見ての通り…なんだけど， って感じ。

• 状態遷移関数は，（「ある状態」と「読み込んだ文字」の組）（「ある状態」のべき集合 (power set)）という写像
  • 要するに，値域の要素がQの部分集合（の組み合わせ）ってことだから，複数の状態に遷移できるってこと。

例えば，以下のような状態遷移図で表される状態遷移関数（と各状態）を持つ機械について考える。

このとき， から 1 を読んだ場合，もうこの時点で次の状態候補が と の２つある。これは，どちらに進んでも構わないことを意味している。

ここで，入力文字列として 100 が与えられたとする。このとき，最初に から に進んでしまうと，この文字列は受理されない（受理状態へ至る道は無くなってしまう）ことになる。ところが， から に進めば即座に受理状態 に至り，受理されることになる。結果的に，この文字列はこの機械で受理される。

この様に，非決定性の機械で受理されるということは，受理状態へ至る道が最低１つあれば十分。