有限オートマトンと状態遷移
更新日:
用語解説
有限オートマトンは、有限個の状態と、入力記号による状態の移り変わり（遷移）で表した計算のモデルです。入力を読み終えたときに受理状態にいれば、その文字列を受理します。
■ 試験で押さえるポイント
決定性有限オートマトン（DFA）では、現在の状態と入力から次の状態が一つに決まります。
状態遷移図では状態を丸、遷移を矢印で表し、受理状態は二重丸で表します。
正規表現で表せる文字列の集まり（正規言語）を判定でき、括弧の対応のような無限の記憶が必要なものは扱えません。
■ 選択肢での判断ポイント
入力を一文字ずつたどって状態を移し、最後の状態が受理状態かどうかで判定します。
例: 1の個数が偶数かどうかは、「偶数」「奇数」の二つの状態で、1を読むたびに状態を入れ替えれば判定できます。