有限オートマトンと状態遷移

有限オートマトンは有限個の状態、入力記号、状態遷移、初期状態、受理状態から成り、入力列に従って状態を移して受理可否を判定する計算モデルです。

■ 試験で押さえるポイント

• 決定性有限オートマトン（DFA）は各状態・入力記号の組に次状態が一意に定まり、入力を読み終えた状態が受理状態なら受理します。

• 非決定性有限オートマトン（NFA）は同じ入力で複数遷移やε遷移を許しますが、受理できる言語の範囲はDFAと同じ正規言語です。

• 状態遷移図は状態を節点、入力による遷移を有向辺で示し、状態遷移表は現在状態と入力から次状態・出力を表します。

• 有限状態しか記憶できないため、任意深さの括弧対応等は有限オートマトンだけでは扱えず、スタックを持つプッシュダウンオートマトン等が必要です。

■ 選択肢での判断ポイント

DFAは現在状態と入力から次状態が一意で、入力終了時の受理状態で文字列を判定します。正規表現と有限オートマトンは正規言語を表す点を押さえます。

例: 2進入力中の1の個数が偶数かを、偶数状態と奇数状態の二つで表し、1を読むたびに状態を交互に遷移させられます。