有限オートマトン

state-machine.png

オートマトンとは

英語ではautomaton,複数形はautomata
直訳すると自動機械、自動人形。
情報処理の分野においては、オートマトンは
ある入力に対し、ある処理を自動的に実行し、ある出力を出すシステムのことである。

有限オートマトンとは?

有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である[1]
普通はパソコンのプログラムなどはメモリ容量が限られている。無限じゃない。
だからプログラムと有限オートマトンは密接な関係がある。
デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。


有限個の「状態」のうち1つの状態をとる。

現在状態

ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。

遷移

何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。
それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。
次は状態遷移図の見方をみてきましょう★

オートマトンは正規表現!?

有限オートマトンの別の表現として正規表現がある。[3]
規則に合致した文字列が入力された時に、文字列を受理する。
そうれない場合は受理しない。
正規表現は文字列の検索や置換などにも利用する。

Bibliography
2. オートマトン・言語理論….大学1年の時、この著者の先生の授業を受けて、それで買った本。懐かしいなぁ。
3. やさしい応用情報技術者講座 2009年版 やさしい講座シリーズ…高橋麻奈さんのシリーズは私、わかりやすくて大好きです。絵もかわいいし♪

サポートサイト Wikidot.com