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

http://d.hatena.ne.jp/takemita/20061228/p1
http://d.hatena.ne.jp/takemita/20061231/p1
http://d.hatena.ne.jp/takemita/20070101/p2
　順序機械の順序機械たる所以は、システムがどの状態のときにどんな入力があると次にどんな状態になるかが決まっているということにあったよ。いいかえると、状態推移関数が存在するということだよ。
　ただしこの「決まっている」というのはゆるい意味だよ。つまり必ずしも1つに決まっているという意味ではないよ。そこで、1つに決まっているときの有限オートマトンを決定性有限オートマトンというよ。
　1つに決まっていないときのことを考えるよ。これは、ある状態である入力があった場合、推移先（次の状態）が複数通りあるということだよ。（いいかえると、状態推移関数の値域が、（状態それ自体ではなくて）状態を要素とする集合となるということだよ。）この種の機械を非決定性有限オートマトンというよ。
　非決定性の場合、記号列の入力による状態推移の経路が複数通りできるわけで、だから入力が終わった時点でのシステム状態にも複数の可能性があるよ。ということは、ある経路で推移するとその記号列は受理される（最終状態に到達する）けど、別の経路だと受理されない（非最終状態に到達する）といったことが起きるよ。
　じゃあ非決定性有限オートマトンで「受理」とはどういう意味か、ということになるけど、これは、どれかの経路で受理される（最終状態に到達する）なら受理で、どの経路でも受理されないなら非受理ということにするよ。