IT資格用語解説応用情報技術者試験・コンパイラ理論
オートマトン
更新日:
用語解説
オートマトンは、入力の記号を順に読みながら、内部の状態を変えていく計算のモデルです。
■ 試験で押さえるポイント
有限オートマトンは、有限個の状態と状態遷移で表し、正規言語を受理します。
入力を読み終えたとき、受理状態にあれば、その入力を受理します。
状態遷移図や状態遷移表で表します。
■ 過去問での着眼点
状態遷移図をたどって、入力が受理されるかを判定できるようにします。
例: 自動販売機の動作を、投入金額を状態とするオートマトンで表します。