心得：按照步驟來(lái)走，不會(huì)走就別跑，搞得糾結(jié)半天為什么簡(jiǎn)化不了，原來(lái)是自己拿著NFA在簡(jiǎn)化。

題目：

考慮正則表達(dá)式who|what|where。使用Thompson構(gòu)造法，從這個(gè)正則表達(dá)式構(gòu)建一個(gè)NFA。使用子集構(gòu)造法，從生成的NFA構(gòu)建一個(gè)DFA。并最小化這個(gè)DFA。
首先構(gòu)造出NFA，然后用Graphviz畫(huà)出圖形。
重點(diǎn)：正則表達(dá)式轉(zhuǎn)NFA(Thompson算法)
dot代碼如下：

digraph G {

S0->S1 [label = "w"];
S1->S2 [label = "h"];
S2->S3 [label = "o"];

S4->S5 [label = "w"];
S5->S6 [label = "h"];
S6->S7 [label = "a"];
S7->S8 [label = "t"];

S9->S10 [label = "w"];
S10->S11 [label = "h"];
S11->S12 [label = "e"];
S12->S13 [label = "r"];
S13->S14 [label = "e"];

S15->S0 [label = "NULL"];
S15->S4 [label = "NULL"];

S3->S16 [label = "NULL"];
S8->S16 [label = "NULL"];

S17->S9 [label = "NULL"];
S17->S15 [label = "NULL"];

S14->S18 [label = "NULL"];
S16->S18 [label = "NULL"];
}

生成的圖片為：

Paste_Image.png

然后是確定化NFA，也就是NFA轉(zhuǎn)DFA。
重點(diǎn)：NFA轉(zhuǎn)DFA(子集構(gòu)造法)
dot代碼為:

digraph G {

I0->I1 [label = " w"];
I1->I2 [label = " h"];
I2->I3 [label = " e"];
I3->I6 [label = " r"];
{
    node [style = filled];
    I6->I8 [label = " e"];
}

{
    node [style = filled];
    I2->I4 [label = " o"];
}
I2->I5 [label = " a"];
{
    node [style = filled];
    I5->I7 [label = " t"];
}
}

圖片為：

Paste_Image.png

無(wú)需進(jìn)行DFA簡(jiǎn)化。