【20200325】编译原理课程课业打卡十之DFA的最小化

分手后的思念是犯贱 2023-07-18 09:53 29阅读 0赞

### 【20200325】编译原理课程课业打卡十之DFA的最小化 ###

*  一、课业打卡十之DFA的最小化
 *   *  1、题解法一
     *  2、题解法二
 *  二、知识巩固
 *   *  1、关于DFA的最小化
     *  2、DFA的最小化拓展例题一
     *  3、DFA的最小化拓展例题二

***叮嘟！这里是小啊呜的学习课程资料整理。好记性不如烂笔头，今天也是努力进步的一天。一起加油进阶吧！***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center]

# 一、课业打卡十之DFA的最小化 #

题目如下：
    将图中的DFA最小化化。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 1]

## 1、题解法一 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 2]

## 2、题解法二 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 3]

# 二、知识巩固 #

## 1、关于DFA的最小化 ##

最小状态DFA
    没有多余状态(死状态)
    没有两个状态是互相等价（不可区别）
    
    两个状态s和t可区别：不满足

![在这里插入图片描述][20200326202101226.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 5]

## 2、DFA的最小化拓展例题一 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 6]  
**题解如下：**  
因为6,7是DFA的终态，其他是非终态，可将状态集分成两个子集：  
P1=\{1,2,3,4,5\}，P2=\{6，7\}。  
由于F（6，b）=F（7，b）=6，而6,7又没有其他输入，所以6,7等价。  
由于F（3，c）=F（4，c）=3，F（3，d）=F（4，d）=5，F（3，b）=6，F（4，b）=7，而6,7等价，所以3,4等价。  
由于F（1，b）=F（2，b）=2，F（1，a）=3，F（2，a）=4，而3,4等价，所以1,2等价。  
由于状态5没有输入字符b，所以与1,2,3,4都不等价。

综上，上图DFA的状态可最细分解为：P={ { 1,2}，{ 3,4}}，{ 5}，{ 6,7}}。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 7]

## 3、DFA的最小化拓展例题二 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 8]  
**题解如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 10]

**Ending！**  
更多课程知识学习记录随后再来吧！

就酱，嘎啦！

![在这里插入图片描述][20200207152559955.png_pic_center]

注：  
我们愈是学习，愈觉得自己的贫乏。 —— 雪莱

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/7e6e0cc891e549bebc63fc1dcf993cdf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/56f60159076a40758283d59c9092a049.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/2e34e2775bde481992cf5784da3cde64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230528/327d994484184fa396eca20a1378a64a.png
[20200326202101226.png_pic_center]: /images/20230528/7337a6868dbd425d9453d98e112fe9fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230528/f6f90a00f51b44e9b049844c8f60a589.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20230528/543e2c3c0d4841f7853b1d330e99170c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20230528/2754916ebe9d40e2ac7d8ef71c9d2955.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20230528/37536e436f674dc59a3103e05c9a4ab0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20230528/6bc5717664254c588f62b2fc5212e0f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20230528/8423925a66094fbdbbfd0cb3139ded88.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20230528/578b0c1b2173459583da4b8c2d12bad9.png
[20200207152559955.png_pic_center]: /images/20230528/30a33dc3b26f4866871ff2e94391330b.png