オ ト ト ７回目 オートマトン 回目 前回の復習 認識機械 受理状態，非受理状態 状態遷移 a pq M x pn 1 p1 M ˆ 入力記号aで状態pから状態qへ p q 入力記号列xで状態p1から状態pn+1 拡張状態遷移関数 今日のキーワード 等価性 等価性判定アルゴリズム 有限オートマトンの最簡形 有限オ トマトンの最簡形 k-等価性分類法 2.2.2 等価性 等価（equivalent） 受理する言語L(M1)，L(M2)が等しい場合 M1≡M2 （ L(M1) = L(M2) の場合） M1 M2 （ L(M1) ≠ L(M2) の場合） 状態に対する等価 p q p≡q p q （ L(p) (p) = L(q) (q) の場合） （ L(p) ≠ L(q) の場合） 到達可能（reachable） 初期状態q0から状態p への遷移が可能 到達可能 q0 1 1 0 r 状態 状態s s1 1 状態 0, r, t 状態q 到達不可能 0 0 t 0 到達不可能状態とそれから出る遷移を除 いても，元のオートマトンと等価 どの最終状態も到達不可能状態であると き，それの受理する言語は空（empty） 無駄な状態を削除するには… 到達可能状態だけを 逐次拾い上げる 初期状態から到達可 能な状態がわかる 到達不可能状態がわ 到達不可能状態 わ かる (0)q0 0 1 ①q0 ②r 1 0 ③t 0 ⑤t ④r 1 ⑥r 2.2.3 等価性判定アルゴリズム M1≡M2 すなわち L(M1) = L(M2) いかなる入力記号列xについても x q01 p1 かつ q p M によって定まる状態対p1，p2に対して 共に最終状態 または 非最終状態である x 02 1 M2 2 一方のみが最終状態となるならば， 一方のみがそのxを受理し もう一方は受理しない 一方のみがそのxを受理し，もう一方は受理しない よってL(M1) ≠ L(M2) であるため，等価でない． 図 図2.21 等価性判定木 （comparison tree） (0)q0≡r0 0 1 ①q2≡r0 0 ③q2≡r0 ②q1 ≡r1 1 1 0 ④q1≡r1 ⑤q1≡r1 ⑥q3≡r1 0 1 ⑦q3≡r1 ⑧q1≡r1 2.2.4 状態対の等価性判定法 状態対の等価性を判定する際には， 任意の状態対を根（root）として判定する． 2.2.5 有限オートマトンの最簡形 最簡形（minimal form あるいは reduced form） すべての状態が初期状態より到達可能である どの状態対をとっても 互いに等価でない どの状態対をとっても，互いに等価でない 等価な状態を統合し続ける． k-等価性分類法 等価性分類法 ハフマン・ミーリーの簡単化法 状態qi，qjが等価 任意の記号列xによる おのおのからの遷移 状態 区別不可能 状態が区別不可能 → すべての記号列xに対して， 確認することは不可能 長さk以下のすべての記号列xを対象とする． qiとq と jはk-等価である（≡ はk 等価である（ k）． ） 定義より 「qi，qjのうちの一方だけが，最終状態」のとき ，かつ そのときに限ってqi 0 qjである． 「δ(qi,a)=qi’，δ(qj,a)=qj’ かつ qi’ kqj’であるよ うなあるa∈Σが存在する」とき，「qi k+1qj 」で ある i≡kqjであり，かつ前記のようなa∈Σが ある．q であり かつ前記のような Σが 存在しないときに，qi≡k+1qjである． 任意のk（≧0）に対して 任意のk（≧0）に対して，p ならば k+1qで で kqならばp ある． 帰納法において，木の高さ（kの値）の小さ い順序で判定木を下から上へ積み上げて 構成してゆく → ボトムアップ方式 ※前節の判定法は等価性判定木を上から 下 と少しずつ拡張しながら調べてゆくト 下へと少しずつ拡張しながら調べてゆくトッ プダウン方式 状態対の等価性判定 最簡形を求める際の基礎となる これ自身，非常に重要な概念 手元にある機械が正常な機械と同じ動作をす るかどうかをチェックすることは，等価性判定 操作に他ならない． 操作に他ならない 2.3 非決定性有限オートマトン 決定性有限オートマトン 各状態と各入力記号のすべての組合わせに 対して，その遷移先状態を必ず 個指定しな 対して，その遷移先状態を必ず１個指定しな ければならない（１個のみしか指定できない）． この条件を緩めてみる ある状態から先の遷移を許さない場合 いくつかの異なった遷移の可能性を許す場合 次回は 非決定性有限オートマトン 状態遷移
© Copyright 2024 ExpyDoc
