オートマトン/第一類/順序機械

最初に例を挙げて，順序機械 (sequential machine) について考えてみよう．

300 円切符だけを販売する自動販売機を考え、一度に投入できる硬貨は 100 円玉 1 枚ずつだけであるとしよう．このとき，この機械が以前の投入金額の合計を「記憶」することができることは，絶対に必要な要件である．この自動販売機は最初は「投入金額 0 円」の状態に設定される．そして，これに 100 円硬貨が投入されると，投入金額が 100 円であることを記憶した状態に移る．切符はまだ出さない．次に 100 円硬貨が投入されると，投入金額の合計が 200 円であることを記憶した状態に移る．切符はまだ出さない．最後に 100 円硬貨が投入されると，ここで初めて 300 円切符を出力し，一方投入金額の合計は 0 円の状態に戻る．

このようにして，この機械は投入金額が 0 円・100 円・200 円であるという 3 種類の状態を持ち，それ以外の状態は考慮する必要はない．これらの状態を $q_{0},q_{100},q_{200}$ としたとき，上記の機械の刻々の時間変化は，次の図1のように表すことができる．

ここで， $q_{0}$ から $q_{100}$ に向かう矢印につけられたラベル「\100/0」は，この矢印が示す状態変化が入力 \100 により発生し，そのときの出力は 0 すなわち「なし」であることを意味する．また， $q_{0}$ から出て $q_{0}$ へ向かうループ状の矢印とラベル「\0/0」は，入力が \0 ならば出力も 0 で，状態の変化もないことを意味する．他の部分も同様に，矢印に添えられた斜線の左側が入力，右側がそれに対する出力を表す．

もう一つ別の順序機械をみてみよう．次の状態推移 (state transition) の図（図2）は，コンパイラにおいてユーザーの書いたソースプログラムの字句(token) を認識するための簡単な字句解析器(lexical analyzer)を実現する順序機械である．ここでは字句として識別子(identifier) を考えており，識別子は英字で始まる長さ1以上の英数字列として定義されている．つまり、入力記号列 B28, DC1 は正しいが，順序のみが異なる 2B8, 1DC はエラーとして認識される．

以上のように、過去の一定の範囲内の入力に応じた状況を記憶することができ，その記憶内容と新たな入力との組み合わせによって次の動作が決まるような機械を順序機械(sequential machine) という．ここで記憶できる内容はあらかじめ定められた有限種類の範囲内であることが順序機械の能力として本質的である．順序機械がこれらの各記憶内容を保持しているとき，それに対応した状態 (state) あるいは内部状態 (internal state) にあるという．また入力により引き起こされる状態の変化を状態推移 (state transition) と呼ぶ．

形式的には，機械の取りうる状態は保持できる記憶の種類だけの記号（図1 では $q_{0},q_{100},q_{200}$ , 図2 では $p,q,r$ ）の有限集合 $Q$ として与え，その具体的意味づけは対象とするシステムの用途に応じて定められる．入力および出力についても同様であり，おのおのの考慮するべき入力および出力の種類だけの記号の有限数号 ${\mathit {\Sigma }},{\mathit {\Delta }}$ として与える．順序機械は，これらの中での状態推移および出力の仕方を指定することにより定められる．図1 では， $Q=\{q_{0},q_{100},q_{200}\}$ ，初期状態は $q_{0}$ ， ${\mathit {\Sigma }}=\{$ \ $0,\$ \ $100\},{\mathit {\Delta }}=\{0,$ 300 円切符 $\}$ で，具体的意味づけは既に述べたとおりである．その状態推移および出力の仕方は図1 に記されている．

順序機械の形式的定義は，その出力の方式の違いにより，「ミーリー型」と「ムーア型」とに分けて与えられる．図1 の自動券売機の例はミーリー型順序機械と呼ばれる型のものであり，図2 の字句解析器の例はムーア型と呼ばれるものに属する．