心得：按照步骤来走，不会走就别跑，搞得纠结半天为什么简化不了，原来是自己拿着NFA在简化。
题目：
考虑正则表达式who|what|where。使用Thompson构造法，从这个正则表达式构建一个NFA。使用子集构造法，从生成的NFA构建一个DFA。并最小化这个DFA。
首先构造出NFA，然后用Graphviz画出图形。
重点：正则表达式转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转DFA。
重点：NFA转DFA(子集构造法)
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
无需进行DFA简化。
