几种不同的转换----形式语言与自动机理论

绝地灬酷狼 2022-06-10 02:20 192阅读 0赞

一：DFA的最小化。

DFA最小化，最简单的理解就是“劈枝斩叶留主干”，最小化的DFA比原状态等价且状态数少。

劈枝斩叶留住干，在化简时候就是对等价的状态进行合并。

那么怎么找等价状态呢？所有的终结符号都是等价的。这也是找之后等价符号的基础。详情看下面例子。

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _]

化简步骤：

1，画出状态矩阵图

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _ 1]

2，找终结符（等价的）。

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _ 2]

3，根据找到的等价的终结符，在继续找其他的等价符号。

解：由于q2，q3等价，q0，q1 1到达q2，（q0,q1)==(q1,q0)  所以 q0,q1等价。

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _ 3]

4，转换。如图示

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _ 4]

5，所得到的最小状态的DFA.

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _ 5]

二：NFA->DFA的转换。

给定的NFA为图

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _ 6]

转换步骤：

1，写I ， I0 ，I1,2，写I=\{q0\}开始符号         3，求I0 ，I1          4，所有包含终态的都是终态。

NFA的矩阵如图示

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _ 7]

转换图：

![1340633444_7931.png][]

总结：I  的第一个是开始符号q0,第二第三个就是上一个中的跟之前的I 不相同的。

直到I中将所有的I0，I1都包括了，就停止了。

三：带空移动的NFA到NFA

带空的NFA如图3-1示

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _ 8]

转换为等价的NFA的步骤：

1，类似NFA转换到DFA的第一步，不同的是，左侧的第一个是开始符号q0以及q0和空之后的所有字符。  例：图3-1的第一个就是\{q0,q1,q2\}

2，第二步是找第二个字符，及所有的所能识别的空移动到达的字符。

3，之后的以此类推，直到所有的字符都出现。

转换图如3-2所示

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _ 9]

等价的NFA为图3-3所示

![几种转换----形式语言与自动机 - 李双喆 - 李双喆 廊坊师范学院九期信息技术提高班][----_ - _ - _ 10]

总结：带空的NFA到NFA与NFA到DFA的不用是左侧的符号，NFA到DFA左侧符号不能很方便的看出来，得根据右侧，第一个就是一个开始符号，空NFA到NFA左侧是所有的符号及识别空所能到达的符号，第一个符号是开始符号或者是开始符号和识别空所到达的符号。

[----_ - _ - _]: https://img-my.csdn.net/uploads/201206/25/1340630820_5336.png
[----_ - _ - _ 1]: https://img-my.csdn.net/uploads/201206/25/1340630869_8686.png
[----_ - _ - _ 2]: https://img-my.csdn.net/uploads/201206/25/1340630882_7568.png
[----_ - _ - _ 3]: https://img-my.csdn.net/uploads/201206/25/1340630894_8831.png
[----_ - _ - _ 4]: https://img-my.csdn.net/uploads/201206/25/1340633030_5244.png
[----_ - _ - _ 5]: https://img-my.csdn.net/uploads/201206/25/1340633077_6438.png
[----_ - _ - _ 6]: https://img-my.csdn.net/uploads/201206/25/1340633123_2014.png
[----_ - _ - _ 7]: https://img-my.csdn.net/uploads/201206/25/1340633156_5037.png
[1340633444_7931.png]: https://img-my.csdn.net/uploads/201206/25/1340633444_7931.png
[----_ - _ - _ 8]: https://img-my.csdn.net/uploads/201206/25/1340633259_8850.png
[----_ - _ - _ 9]: https://img-my.csdn.net/uploads/201206/25/1340633664_9668.png
[----_ - _ - _ 10]: https://img-my.csdn.net/uploads/201206/25/1340633705_6543.png