有限オートマトンとは
有限個の「状態」と、入力による「状態の移り変わり」で動作を表すモデル。文字列が条件に合うかの判定などに使います。
解説
有限オートマトンは、初期状態から入力記号を1つずつ読み、遷移規則に従って状態を移していくモデルです。入力を読み終えたときに「受理状態」にいれば、その入力列を受理（条件に合うと判定）します。状態遷移図（丸が状態、矢印が遷移）や状態遷移表で表すことが多く、正規表現で表せる文字列の集合は有限オートマトンで判定できます。
試験での出方
状態遷移図を読んで、ある入力列を受理するかを判定する問題や、与えられた条件を満たす遷移図を選ぶ問題が出ます。入力を1文字ずつ追って状態をたどれば解けます。
あわせて読みたい用語
この用語が解説に出てくる問題
- 平成30年度 春期 問5DFDの記述例として，適切なものはどれか。
- 平成29年度 春期 問14DFD の表記に関する記述として，最も適切なものはどれか。
- 平成24年度 秋期 問53関係データベースの設計で用いられる E-R 図が表現するものは何か。
- 平成24年度 春期 問41プロジェクトマネジメントにおいて計画を立てる際に用いられる手法の一つであり，プロジェクト全体を細かい作業に分割し，階層…
- 平成24年度 春期 問76E-R 図の説明と，その応用例として，適切なものはどれか。
この用語がよく出る分野：基礎理論の要点と過去問一覧