このページでは、入力と今の状態で次の状態が決まる順序機械と有限オートマトンの読み方、正規表現との関係、プッシュダウンオートマトンとチューリング機械の違いがわかります。
-
記号の書き方(このメモのルール):
- 本来は上に線を引いて表す「否定」「補集合」は、論理なら ¬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個以上の集合)
- 有限オートマトン(正規言語)/プッシュダウンオートマトン(文脈自由言語、スタック付き)/チューリング機械(句構造言語、コンピュータのモデル)