有限オートマトン

(2016/08/22)
  • 順序機械に言語を認識するアルゴリズムを与えた数学的モデル

  • 小難しい定義で言うと「有限個の状態の集合K, 入力記号の有限状態Σ, Σに属する各入力記号と現在の状態が引き起こす状態遷移関数σ, さらに状態Kの集合の一要素である初期状態q0, 状態Kの部分集合である受理状態集合F
  • どういうことだってばよ
  • どういうことかざっくり解説を試みる

  • 受理状態集合Fってやつがすごい大事っぽい
  • 初期状態から入力を繰り返していって、最終的な状態がFに属するかどうかで受理されるかどうかが決まる
  • 正規表現 with 有限オートマトン

  • 有限オートマトンは正規表現に利用されたりする
  • a(b|c)dの例
  • 応用情報技術者試験

general(396)