アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

66

3

章 最も単純なコンピュータ

下の図は、3つの状態を持ち、入力として文字

a

と

b

を読むことができるオートマトンです。

図3-3

この機械は

'ab'

、

'baba'

、

'aaaab'

といった文字列を受理し、

'a'

、

'baa

'、

'bbbba'

といった

文字列を拒否します。少し実験してみると、この機械は

'ab'

というシーケンスを含んだ文字列しか受

理しないことがわかります。この機械もそれほど役に立つものではありませんが、少なくともある程度

の賢さがあるように見えるでしょう。この章の後半では、もっと実用的な応用について紹介します。

3.1.3

　決定性

ここで重要なことは、この種のオートマトンは決定的である（deterministic）ということです。現在

いる状態がどこであれ、読む文字が何であれ、機械が次にどの状態になるかは、必ず確実に決まって

います。次の2 つの制約を守る限り、この確実性は保証されます。

●

矛盾がないこと：競合する規則があることによって、次の移動があいまいになるような状態がな

いこと（同じ入力文字に対して、取り得る状態が複数存在しないことを意味します）。

●

省略がないこと：規則が欠けていることによって、次の移動がわからなくなるような状態がない

こと（状態はすべて、可能な入力文字に対して少なくとも1つの規則を持たなくてはならないこ

とを意味します）。

要するに、これらの制約が意味しているのは、機械は状態と入力の組み合わせに対して、必ず規則

を1 つだけ持つ必要があるということです。この決定性制約に ...