オートマトン

このページでは、入力と今の状態で次の状態が決まる順序機械と有限オートマトンの読み方、正規表現との関係、プッシュダウンオートマトンとチューリング機械の違いがわかります。

  • 記号の書き方(このメモのルール):

    • 本来は上に線を引いて表す「否定」「補集合」は、論理なら ¬A、集合なら Aᶜ と書く
    • 2乗などのべき乗は 2³、σ² のように書く。log の底は log₂ のように書く
  • 一言で言うと:

    • 「今の状態」と「入力」で次の状態が決まる機械のモデル。文字列が決まった形になっているかを判定する(字句解析など)のに使う。

状態をもつ機械(順序機械・有限オートマトン)→ 正規表現との関係 → もっと強い機械(その他のオートマトン)

覚え方の軸

  • 順序機械は「入力+今の状態」で決まる:
    • 出力と次の状態が、入力だけでなく今の状態にもよる(=過去を覚えている)
  • 有限オートマトンは5つ組:
    • 状態の集合K、入力記号の集合Σ、状態遷移関数δ、初期状態q₀、受理状態の集合F
  • 判定のルールは「最後にいる状態」:
    • 入力を全部読み終えたとき、受理状態(◎)にいれば受理
  • オートマトンの強さの順番と、認識できる言語:
    • 有限オートマトン(正規言語)< プッシュダウンオートマトン(文脈自由言語)< チューリング機械(句構造言語)

有限オートマトン:状態を移りながら文字列を読む機械

  • 順序機械:
    • 1つの入力値で1つの出力値が決まるのではなく、入力値と、そのときの状態によって出力値(と次の状態)が決まる機械
    • フリップフロップ回路や自動販売機のように、過去の状態を記憶できる回路や機械をモデル化したもの
    • ブラックボックスで表すと:
      • 入力(t)と状態(t)から、出力(t)と次の状態(t+1)が決まる(tは時刻)
  • 状態遷移表:
    • 状態と入力の組合せごとに、「出力」と「次の状態」を書いた表
  • 状態遷移図:
    • 状態を丸、遷移を矢印で描いた図。矢印に「入力/出力」を書く(例:1/0は入力1で出力0)
    • 例:
      • 状態Pのとき1を入力すると、0を出力してQへ遷移する、という具合に読む
  • 有限オートマトン(FA:Finite Automaton):
    • 順序機械に、言語を認識するアルゴリズムを与えた数学的なモデル
    • 定義(5つ組):
      • 有限オートマトン=<K,Σ,δ,q₀,F>
      • K:
        • 状態の有限集合
      • Σ:
        • 入力記号の有限集合
      • δ:
        • 状態遷移関数(今の状態と入力記号から、次の状態を決める)
      • q₀:
        • 初期状態(Kの要素の1つ)
      • F:
        • 受理状態集合(Kの部分集合)
    • 状態遷移関数の書き方:
      • 状態aで入力0を受けて状態bに移るなら、δ(a,0)=b
      • δは「K×Σ から K への写像」。K×Σは集合KとΣの直積集合(全部の組合せ)
    • 状態遷移図の書き方:
      • 初期状態を「➡」、受理状態を「◎」で表す
  • 例:
    • 「末尾が01で終わるビット列」を受理する有限オートマトン
    • K={a,b,c}、Σ={0,1}、q₀=a、F={c}
状態 入力0 入力1
a(初期) b a
b b c
c(受理) b a
  • 状態の意味:
    • a=まだ何も読んでいないか最後が「1」(01の途中ではない)、b=最後が「0」、c=最後が「01」
  • 「1101」:
    • a→a→a→b→c。最後がcなので受理する
  • 「0110」:
    • a→b→c→a→b。最後がbなので受理しない
  • 有限オートマトンのモデル:
    • テープに書かれた入力ビット列を読む有限状態機械とみなせる
    • 動き方:
      • 入力ヘッドをテープの左端に置き、初期状態から始める → 1マス読むと状態遷移関数に従って遷移し、ヘッドを1マス右に進める → 最後のビットを読んで遷移した先が受理状態集合Fに入っていれば受理
    • 有限状態部:
      • 今の状態を持っている部分
    • 入力テープ:
      • 右に延びた半無限長のテープ。入力ビット列が左から1マス1ビットずつ書かれている。空白はビット列の区切り

有限オートマトンと正規表現

  • 正規言語:
    • 正規表現で表される言語。有限オートマトンは、正規言語を認識するために使う
  • 正規表現のメタ記号(詳しくは後の「正規表現」)
    • r1|r2:
      • r1 又は r2
    • (r)*:
      • r の0回以上の繰返し
  • 例:
    • 正規表現 0(10)* が表す文は、0、010、01010、0101010、…
    • 特徴:
      • 「0で始まり0で終わり、0と1が交互に並ぶ」
    • これを受理する有限オートマトン:
      • Q₀(初期):0なら Q₁ へ、1なら Q₃ へ
      • Q₁(受理):1なら Q₂ へ、0なら Q₃ へ
      • Q₂:0なら Q₁ へ戻る、1なら Q₃ へ
      • Q₃:0でも1でも Q₃ のまま(一度入ると出られない。交互にならなかったら不合格)
  • 正規表現から有限オートマトンを作る方法は出題範囲外。試験では「この有限オートマトンが受理する正規表現はどれか」が問われる

その他のオートマトン

  • プッシュダウンオートマトン:
    • 文脈自由文法から作られる文脈自由言語を認識する
    • 有限オートマトンにプッシュダウンストアというスタックを付けたもの。入力記号、スタックの一番上の記号、今の状態で次の状態を決める
  • チューリング機械(チューリングマシン):
    • プッシュダウンオートマトンより能力が高い。ノイマン型コンピュータの動作原理の理論的な基本モデル
    • 句構造言語を認識する

混同しやすいペア

  • 順序機械(入力と状態で決まる。過去を覚える)/有限オートマトン(順序機械に言語を認識させるもの)
  • 状態遷移表(表)/状態遷移図(丸と矢印)
  • 初期状態 q₀(➡、1つ)/受理状態集合 F(◎、0個以上の集合)
  • 有限オートマトン(正規言語)/プッシュダウンオートマトン(文脈自由言語、スタック付き)/チューリング機械(句構造言語、コンピュータのモデル)

← 01 基礎理論の目次に戻る

タイトルとURLをコピーしました