正規表現からのDFA直接構成
正規表現からのDFA直接構成 McNaughton-Yamadaの構成法でできるNFAの特殊性を利用してDFAを直接構成する。 e以外の遷移ができる状態を重要状態という。 問 例で構成したNFAの重要状態をマークせよ。 各重要状態は何に対応するか？ 何故「重要」か： move({s}, a)はsが重要状態の時に限り空でない。 したがって部分集合構成法の e-closure(move(T, a))= e-closure(∪move({s}, a)) に寄与するのは重要状態だけ。 s∈T
部分集合の同一性 McNaughton-Yamadaで得られるNFAは 注意： 部分集合構成法では、同じ重要状態をもち、 受理状態を含むか否かが同じであるような 二つの部分集合は同一視してよい。 とくに受理状態が１つだけであれば、 同じ{重要状態or受理状態}を含むとき同一視してよい。 McNaughton-Yamadaで得られるNFAは ただ一つの受理状態をもち、 それは出る辺を持たないので重要状態ではない。
正規表現の拡大 もとのアルファベットSにない記号#を導入し、 S上正規表現rからS ∪{#}上の正規表現(r)#をつくる。 (r)#からMcNaughton-Yamadaで得られるNFAは となり、もとのNFA N(r)の受理状態は重要状態になる。 前ページの注意で受理状態を特別扱いしなくてもよくなる。 N(r) #
拡大正規表現の構文木 (a|b)*abb#の構文木 ･ ･ # 6 ･ b 5 ･ b 4 構文木： 葉 — 記号 (出現順に番号ラベル—位置) 内部節点 — 演算子 ･ — cat-節点 | — or-節点 * — star-節点 * a 3 | a 1 b 2
DFA構成のアルゴリズム(1/3) n nullable(n) firstpos(n) lastpos(n) true Φ false nはeをラベルとする葉 true Φ nは位置iをラベルとする葉 false {i} n | c1 c2 nullable(c1) or nulable(c2) firstpos(c1) ∪firstpos(c2) n ･ nullable(c1) and nulable(c2) if nullable(c1) then firstpos(c1)∪firstpos(c2) else firstpos(c1) n * c1 前ページの各nにnullable(n),firstpos(n),lastpos(n)を書き込め。
DFA構成のアルゴリズム(2/3) followpos(i)=位置iのすぐあとにくる位置の集合 followpos(i)の特徴づけ： nがcat-節点でその左右の子がc1,c2であり、iがlastpos(c1)の要素であればfollowpos(i)はfirstpos(c2)のすべての要素を含む。 nがstar-節点でiがlastpos(n)の要素であれば、followpos(i)はfirstpos(n)のすべての要素を含む。 followpos(i)の計算： 構文木を上から深さ優先で巡回して上の規則を満たさせる。 練習 前々ページの構文木にfollowpos(i)を書き込め。 ラベルをノードとする有向グラフ (辺： i → followpos(i)の要素)
DFA構成のアルゴリズム(3/3) アルゴリズム(DFAの直接構成) (r)#に対する構文木の根をrootとする。 Dstates := {firstpos(root)}; (印はつけない。) while Dstatesのなかに印のついていない要素Tがある do Tに印を付ける; for 各入力記号a do U := ∪ followpos(p); if Uが空集合でなく、Dstatesの中にもない then Uを、印がついていない状態としてDstatesに追加; Dtran[T,a] := U; end p∈Tがaの位置