目次

Theoretical Computer Science

参照

決定性と非決定性

定義

決定性有限オートマトン

\mbox{A finite automaton is 5-tuple (Q, \Sigma, \delta, q_0, F)} \\ \left\{ Q \mbox{ is a finite set of states, } \\ \Sigma \mbox{ is a finite set of alphabet, } \\ \delta : Q \times \Sigma \longrightarrow Q \mbox{ is the transition function, } \\ q_0 \in Q \mbox{ is the start state, and} \\ F \subseteq Q \mbox{ is the set of accept states } \right

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

Graph

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

ちなみに，この機械が受理する言語は見ての通り…なんだけど，L = \{ 1^n0 ^\vee 0^n1 | n \in \mathbb{N} \} って感じ。

非決定性有限オートマトン

\mbox{A nondeterministic finite automaton is 5-tuple (Q, \Sigma, \delta, q_0, F)} \\ \left\{ Q \mbox{ is a finite set of states, } \\ \Sigma \mbox{ is a finite set of alphabet, } \\ \delta : Q \times \Sigma_\epsilon \longrightarrow \mathcal{P}(Q) \mbox{ is the transition function, } \\ q_0 \in Q \mbox{ is the start state, and} \\ F \subseteq Q \mbox{ is the set of accept states } \right

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

Graph

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

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

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