「有限オートマトン」は記号列を読んで識別する自動機械の数学的モデル(記憶容量が有限)。
- 入力前に特定の初期状態にセット
- 記号列を入力すると先頭から1文字ずつ読む
- 読んだ記号によって「状態」が変わり、全部読み終えたときの状態によって「yes/no」の答えを得る
有限オートマトンMは
状態の有限集合 Q (≠φ),
入力アルファベット Σ,
状態遷移関数 δ:Q×Σ→Q,
初期状態 q0 (∈Q),
受理状態の集合 F (⊆Q)
によって規定される。
状態遷移関数 δ:Q×Σ→Q とは?
Q×Σ={(q,x)|q∈Q,x∈Σ}だから、この部分は「ある状態qにある文字xを組み合わせた」ものだ。それを変化後の状態に対応させる。
例:Q={出勤前,定時出勤,遅刻,欠勤}、Σ={0,1,2}としよう。ちなみにΣの数字は前夜に飲みに行った店の数を表す。初期状態は出勤前。前夜飲みに行っていなければ定時に出勤、1軒飲みに行くと遅刻し、2軒飲みに行った場合は二日酔いで欠勤。
Q\Σ | 0 | 1 | 2 |
---|---|---|---|
出勤前 | 定時出勤 | 遅刻 | 欠勤 |
定時出勤 | |||
遅刻 | |||
欠勤 |
うむ。表にすると考えが浅くて漏れているところがよくわかるな。
初期状態以外のときに0,1,2が与えられたらどう解釈するか…当日の行動が決まった後で、その原因となった昨夜の行動を与えられても変わらないと考えるのが妥当だろう。
Q\Σ | 0 | 1 | 2 |
---|---|---|---|
出勤前 | 定時出勤 | 遅刻 | 欠勤 |
定時出勤 | 定時出勤 | 定時出勤 | 定時出勤 |
遅刻 | 遅刻 | 遅刻 | 遅刻 |
欠勤 | 欠勤 | 欠勤 | 欠勤 |
遅刻しちゃった後で「昨日は全然飲んでないじゃん(0)」などと言われても遅刻は遅刻。well-defined? 図にするとこんな感じか。
受理状態は2重の輪で表す。
つまり受理状態の集合F={定時出勤,遅刻,欠勤}。
Pingback: 有限オートマトン2-1.定義 その2 | デザイナーの数学