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

3.1

 決定性有限オートマトン

65

3.1.2

　出力

これだと役に立たないので、有限オートマトンは基本的な出力生成手段を備えています。とはい

え、実際のコンピュータほど高機能なものではありません。一部の状態に特別な印を付けて、機械が

その特別な状態にいるか否かを、1ビットの出力として表現するだけです。図にある機械の場合、二重

のサークルで示されている状態2 が特別な状態になります。

図3-2

この特別な状態は受理状態（accept state）と呼ばれ、機械が特定の入力シーケンスを受理もしくは

拒否するという概念を表しています。このオートマトンは、状態1から開始して、文字

a

を読むことで

受理状態である状態2に移動します。したがって、この機械は文字列

'a'

を受理する、と言えます。こ

れに対し、最初に文字

a

を読んで、そのあともう1文字

a

を読むと、最終的に状態1に戻ります。状態

1は受理状態ではないので、この機械は文字列

'aa'

を拒否します。この機械が長さが奇数の

a

の文字

列 を 受 理 す るこ とは、 容 易 に わ か る で し ょう。

'a'

、

'aaa'

、

'aaaaa'

は 受 理 さ れ、

'aa'

、

'aaaa'

、

''

（空文字列）は拒否されます。

これで少しは役に立つものになりました。文字のシーケンスを読んで、それが受理可能かどうか、

イエスかノーで示すという機械です。このオートマトンは計算を実行している、と言っても差し支えな

いでしょう。なぜなら「この文字列の長さは奇数ですか」という質問に対して、意味の ...