有限オートマトンとは
有限個の「状態」と、入力による「状態の移り変わり」で動作を表すモデル。文字列が条件に合うかの判定などに使います。
解説
有限オートマトンは、初期状態から入力記号を1つずつ読み、遷移規則に従って状態を移していくモデルです。入力を読み終えたときに「受理状態」にいれば、その入力列を受理（条件に合うと判定）します。状態遷移図（丸が状態、矢印が遷移）や状態遷移表で表すことが多く、正規表現で表せる文字列の集合は有限オートマトンで判定できます。
試験での出方
状態遷移図を読んで、ある入力列を受理するかを判定する問題や、与えられた条件を満たす遷移図を選ぶ問題が出ます。入力を1文字ずつ追って状態をたどれば解けます。
あわせて読みたい用語
この用語が解説に出てくる問題
- 平成31年度 春期 問46UMLにおける振る舞い図の説明のうち，アクティビティ図のものはどれか。
- 平成30年度 秋期 問46UML 2.0のシーケンス図とコミュニケーション図のどちらにも表現されるものはどれか。
- 平成30年度 春期 問4入力記号，出力記号の集合が{0，1}であり，状態遷移図で示されるオートマトンがある。0011001110を入力記号とし…
- 平成29年度 秋期 問46UML 2.0において，オブジェクト間の相互作用を時系列に表す図はどれか。
- 平成28年度 秋期 問3300円の商品を販売する自動販売機の状態遷移図はどれか。ここで，入力と出力の関係を“入力／出力”で表し，入力の“a”は…
この用語がよく出る分野：基礎理論の要点と過去問一覧