基礎理論~オートマトン~
オートマトンとは
一般的には、 状態遷移図 や 状態遷移表 と表されます。
どういったものかと言うと、
こんなもの。
なにこれ?と思うかもしれませんが、個人的にはサービス問題だと思います。詳しく説明していきます。
有限オートマトン(オートマトン基礎)
オートマトンには複数種類がありますが、FEやAPなどで取り上げられるのはこの 有限オートマトンというものです。
簡単に言うと、 状態遷移表 という「地図」と 入力データ という「道順」を与えられるのでゴールまでたどり着いてください、という問題です。
上図は「状態遷移図」です。
- q1
- q2
- q3
という状態(地図で言う建物)があり、矢印を辿って q2 に辿り着こうね、という地図です。
最初のスタート地点(q1)を 初期状態 と言い、◎の q2を 受理状態 といいます。用語です。
さて、この地図と道順を渡されます。
「01101」という順番で行ってね! という形で入力値が渡されますので、
q1 からスタートして、
q1 -> 0 -> q1 -> 1 -> q2 -> 1 -> q2 -> 0 -> q3 -> 1........あれ?先の道がない。
このように、目的のゴールまでたどり着けない状態を 不受理されなかった 状態といいます。
成功例は、「01」や「011」などですね。
問題では「受理される入力データを選びなさい」という問題が頻出です。