例3.1 正规式书写

| image.png | ①(a|b)(ab)(a|b)
②(bb)
③(ababa)
④a(a|b)aa|aa | | —- | —- |

(a|b)*表示ε,a,b,ab,ba…任何ab组合

⭐例3.2 子集构造法NFA转换成DFA

对(a|b)*a|b,①画出NFA;②NFA转换为DFA;③最小化DFA;

  1. NFA如下


image.png

  1. 转换表如下: | T | Dtran[T,a] | Dtran[T,b] | | —- | —- | —- | | {1,2,3,4,6,9,11}
    1 | {5,8,3,4,6,9,10,13}
    2 | {7,8,3,4,6,9,12,13}
    3 | | {5,8,3,4,6,9,10,13}
    2 | {5,8,3,4,6,9,10,13}
    2 | {7,8,3,4,6,9}
    4 | | {7,8,3,4,6,9,12,13}
    3 | {5,8,3,4,6,9,10,13}
    2 | {7,8,3,4,6,9}
    4 | | {7,8,3,4,6,9}
    4 | {5,8,3,4,6,9,10,13}
    2 | {7,8,3,4,6,9}
    4 |

由于13为接收状态,则转换后2,3,4为最终态
image.png

  1. 最小化

由②,I={2,3,4},J={1},Π={{1},{2,3,4}},move(I,a)={2},move(I,b)={4},而二者都属于分组{2,3,4},该状态集中状态彼此等价,J无需再拆分,则最终状态集Π={{1},{2,3,4}},令{2}代表{2,3,4}
image.png