有限オートマトン - およそMECEでないアカシックレコードの200那由多飛んで3万分の3

有限オートマトン

文字列を入力したときに、内部でハードコードされている規則を満たすかどうかを出力する機械

幾つかのとりうる状態と現在の状態を記憶する機能を持った機械

入力: 一度に1文字しか読めない外部入力ストリーム

出力: 受理したか拒否したか（受理状態）

状態間の移動は規則によって決められている

規則の集合がハードコードされている

入力によって状態を移動させる

できること: この文字列の長さは偶数であるか否かに対してtrue/falseを返す

例

code:mermaid

stateDiagram-v2

* --> 1

1 --> 2 : a

2 --> 1 : a

2 --> *

規則

状態1でaを受け取ると状態2へ移動する

状態2でaを受け取ると状態1へ移動する

"a""aaa"は受理されるが、"""aa"は受理されない

参考

『アンダースタンディングコンピュテーション』