ケータイ小説 計算機科学入門 第2話

定義だけなら
サルでもできる
理論は例と定理が命

有限状態オートマトンの例

入力として
0と1の列を考える

自然数nを2進数で
大きい桁から順に書いた列よ

nが3の倍数かどうか
「計算」するオートマトンを作るわ

状態集合Qは{q_0, q_1, q_2}
つまり状態はq_0, q_1, q_2の3つ

現在の状態がq_iだったら
それまでの入力列が表す自然数nを
3で割った余りはiになる

そうなるように
遷移を定義するの

例えば現在の状態がq_2のとき
それまでのnを3で割った余りは2

そこに入力0が来たら
2進数の下一桁に0を付け加えるのだから
nは2nに変化する

nを3で割った余りが2ならば
2nを3で割った余りは1だから
状態はq_1に変化する

つまり q_2 ---0---> q_1

状態q_2に
入力1が来たら
nは2n+1に変化する

nを3で割った余りが2ならば
2n+1を3で割った余りも2だから
状態はq_2のまま

つまり q_2 ---1---> q_2

同様に考えて
q_0 ---0---> q_0
q_0 ---1---> q_1
q_1 ---0---> q_2
q_1 ---1---> q_0

すべてまとめると
遷移関係T = { (q_0,0,q_0), (q_0,1,q_1), (q_1,0,q_2), (q_1,1,q_0), (q_2,0,q_1), (q_2,1,q_2) }

「3の倍数かどうか」って「計算」だから
入力が終わったときの状態がq_0だったら答えは「yes」
q_1かq_2だったら「no」

試しに2進数で「1001」（10進数で9）を入力してみると
q_0 --1--> q_1 --0--> q_2 --0--> q_1 ---1--> q_0
で
最後の状態はq_0
だから確かに
答えは「yes」

受理状態、受理言語

「計算」＝「情報の処理」だから
入力だけじゃなくて
出力もないと意味がない

一番簡単な計算モデルだから
入力に対する答え（出力）は
「yes」か「no」しかないことにして

入力に対して
「yes」と答える状態が「受理状態」
受理状態じゃなければ答えは「no」

一般に
受理状態は一つじゃなくても良いから
受理状態の集まりを
集合Aで表すわ

状態集合Q
遷移関係T
初期状態q_0
受理状態の集合A

それらからなる一つのオートマトンMが与えられたとき
q_0 --a--> q_i --b--> q_j --c--> q_k --d--> ... --z--> q
のように遷移を繰り返して
qが受理状態になる（Aに属している）

そうなるような入力列abcd...zの集まりを
そのオートマトンMの受理言語と呼ぶわ

たとえばさっきの例に出てきたオートマトン
Q = { q_0, q_1, q_2 }
T = { (q_0,0,q_0), (q_0,1,q_1), (q_1,0,q_2), (q_1,1,q_0), (q_2,0,q_1), (q_2,1,q_2) }
A = { q_0 }
これの受理言語は
「2進数とみなしたら3の倍数になるような、
0と1からなる列」の集合

練習問題

入力として
0と1と2からなる列を受け取って
「012」と連続して現れる部分が「ない」

そういう列（だけ）を受理する
オートマトンを与えてご覧なさい

っていうか
オートマトンだから
初期状態はq_0として
状態集合Q
遷移関係T
受理状態の集合A
この3つを明示してみせなさい

みたいな？

練習問題２

「012」じゃなくて
「0101」だったら？
つまらなかったので削除
みたいな