本文共 504 字,大约阅读时间需要 1 分钟。
最小化确定有限自动机
最小化下图的有限自动机DFA。
概念补充(不懂没关系,直接示范)
- DFA化简定义:找一个状态数比原来得确定有限自动机状态数少得确定有限自动机,但是表示得语言和原来的确定有限自动机相同
- 状态等价:
- 状态s和t等价,意味着从s和t出发,读出识别同一个字符α,都到达了终态,那么这两个状态s和t是等价的
- 状态可区分:
- 状态s和t可区分,存在一个字符α,分别让s和t读取之后,分别处于终态和非终态
实时演算
- 方法:
- 将S划分成终态和非终态两个子集,形成基本划分
- 然后分别对各个子集进行字符运算,观察彼此的结果是否在同一个子集中
- 如果经过所有的字符运算之后,在同一个子集,那么就是自己所有的状态都是等价的
- 如果不是经过某个字符运算之后,不在同一个子集,那么在进行划分,结果为同一个子集的划分到一起
演示
- 将所有的状态根据终态和非终态进行基本的划分,分别进行输入a的运算,发现如下的变化
![在这里插入图片描述](https://img-blog.csdnimg.cn/2020052609582726.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrb3V0ZHJhZ29u,size_16,color_FFFFFF,t_70)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526100557533.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrb3V0ZHJhZ29u,size_16,color_FFFFFF,t_70)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526101746517.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrb3V0ZHJhZ29u,size_16,color_FFFFFF,t_70)
转载地址:http://uggpb.baihongyu.com/