有限オートマトン

finite automation、有限状態機械

有限個の内部状態を持つ

入力によって状態を遷移していき、最終的に受理できるかどうかが重要

コンピュータからさまざまな機能を取り除いて単純化したもの

特徴

永続的ストレージがない

いくつかの取り得る状態と現在どの状態にいるかを記録する能力はある

一度に一文字しか読めない外部入力ストリームを一つだけ持っている

一文字読むごとに規則に従って別の状態へ遷移する

初期状態は一つのみ、最終状態は一つ以上存在する

有限オートマトン$ Mは、初期状態$ q_0 \in Qより出発して、入力系統より$ \Sigmaの要素を1文字つ読み、読み込む度にその内部状態を変更する

この状態遷移は遷移関数$ \sigma : Q \times \Sigma \to Qによって定められる

用語と記号

有限オートマトン $ M

初期状態 $ q_0 \in Q

一つのみ

内部状態の有限集合 $ Q

受理状態の集合 $ F

拒否状態の集合 $ Q \setminus{F}

遷移関数 $ \sigma : Q \times \Sigma \to Q

規則集のこと

入力記号の有限集合 $ \Sigma

有限オートマトン$ Mが受理する集合$ L(M):{x \in \Sigma ^ \ast} \mid \delta(q_0, x)\in F\}

出力

一部の状態に対して、機械がその状態であるかどうかで1ビットの出力をする

ex.

s1, s2, s3という3つの状態を持つ機械のs3で出力を表現するとする

s1,s2にあるときはoff, s3の状態にあるときはonになる

accept state

何らかの入力に対し、出力がonになるかoffになるかみたいな話

ある機械では絶対にoffになる入力は拒否されると言い、逆は受理されると言う

何を入力しても、何文字入力してもどこかの状態には移動できるけど、

本質は「受理状態」までいけるかどうか

行けなければ拒否、行けるときのみ受理

n文字受け取ってn回遷移した後に最終状態にいなければ拒否される

換言すると、受理される入力の集合と、拒否される入力の集合がある

以下の図では二重丸は「受理状態」、それ以外は「拒否状態」

https://i.stack.imgur.com/JpLX5.jpg