DFA_construction

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

Download Report