こなさんち

しがないメンヘラエンジニアの日記。

基礎理論~オートマトン~

オートマトンとは

一般的には、 状態遷移図 状態遷移表 と表されます。

どういったものかと言うと、

f:id:cresta522:20190701195856p:plain
オートマトン

こんなもの。

なにこれ?と思うかもしれませんが、個人的にはサービス問題だと思います。詳しく説明していきます。

有限オートマトンオートマトン基礎)

オートマトンには複数種類がありますが、FEやAPなどで取り上げられるのはこの 有限オートマトンというものです。

簡単に言うと、 状態遷移表 という「地図」と 入力データ という「道順」を与えられるのでゴールまでたどり着いてください、という問題です。

上図は「状態遷移図」です。

  • q1
  • q2
  • q3

という状態(地図で言う建物)があり、矢印を辿って q2 に辿り着こうね、という地図です。

最初のスタート地点(q1)を 初期状態 と言い、◎の q2を 受理状態 といいます。用語です。

さて、この地図と道順を渡されます。

「01101」という順番で行ってね! という形で入力値が渡されますので、

q1 からスタートして、

q1 -> 0 -> q1 -> 1 -> q2 -> 1 -> q2 -> 0 -> q3 -> 1........あれ?先の道がない。

このように、目的のゴールまでたどり着けない状態を 不受理されなかった 状態といいます。

成功例は、「01」や「011」などですね。

問題では「受理される入力データを選びなさい」という問題が頻出です。