《编译原理》构造与正规式 (0|1)*01 等价的 DFA - 例题解析

快来打我* 2022-01-10 04:07 1072阅读 0赞

### 《编译原理》构造与正规式 (0|1)\*01 等价的 DFA - 例题解析 ###

**解题步骤：**

*  NFA 状态转换图
 *  子集法
 *  DFA 的状态转换矩阵
 *  DFA 的状态转图

#### 解： ####

**已给正规式：(0|1)\*01**

画出 NFA 状态转换图如下：

![在这里插入图片描述][20190621004223453.png]

子集法的表格：

<table> 
 <thead> 
  <tr> 
   <th><strong>I状态\字符</strong></th> 
   <th>I<sub>0</sub></th> 
   <th>I<sub>1</sub></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>{S, A, B} <strong>求法：</strong> 表示开始符号，以及开始符号识别 n 个 ε 可以到达的状态集合。<strong>如本题中：</strong> 开始符号 S，通过识别 ε 可以到达的转态有 A, B，所以集合为 {S, A, B}</td> 
   <td>{A, B, C} <strong>求法：</strong> 表示改行最左端的状态集，识别最上端的符号可以到达的状态，以及这些状态识别 n 个 ε 可以到达的状态的集合。<strong>如本题中：</strong> 有 {S, A, B}，逐个判断 S 识别 0 弧没有可以到达的状态；A 识别 0 可以到达 A，B 识别 0 可以到达 C；现在已有 A, C 状态，又因为 A 状态识别 ε 可以到达 B，所以整个集合为 {A, B, C}</td> 
   <td>{A, B} <strong>求法：</strong> 同相邻左测表格求法。<strong>如本题中：</strong> 有 {S, A, B}，S 状态识别 1 没有可以到达的状态，A 识别 1 可以到达 A，B 识别 1 没有可以到达的状态。所以此时只有 A。又因为 A 状态识别 ε 可以到达 B，所以整个集合为 {A, B}</td> 
  </tr> 
  <tr> 
   <td>{A, B, C} <strong>求法：</strong> 这个为什么是 {A, B, C}？<strong>因为</strong> 相邻右上方表格为 {A, B, C} 为什么用相邻右上方表格的状态集？<strong>因为</strong> 它是初始态，仅识别 0 和 ε 就能到达的状态集。所以，可以将该状态集视为识别一条弧所到达的状态集。可以看做是下一状态，为起状态别名做准备。</td> 
   <td>{A, B, C} <strong>注：</strong> 有 A 就有 B</td> 
   <td>{A, B, T}</td> 
  </tr> 
  <tr> 
   <td>{A, B}</td> 
   <td>{A, B, C}</td> 
   <td>{A, B}</td> 
  </tr> 
  <tr> 
   <td>{A, B, T}</td> 
   <td>{A, B, C}</td> 
   <td>{A, B}</td> 
  </tr> 
 </tbody> 
</table>

对状态中间重命名，求新的状态转换矩阵：

（1）因为 S 是初态，重命名为 S’，也是终态

（2）设 \{A, B, C\} 为 A’

（3）设 \{A, B\} 为 B’

（4）因为 T 是终态，此时 \{A, B, T\} 不是相当于 A’ 识别 1 弧所到达的状态，T 是终态，\{A, B, T\} 也是终态，重命名为 T’

画出 NFA 状态转换图如下：

![在这里插入图片描述][20190621004319325.png]

#### 验证 ####

(0|1)\*01 正规式对应的正规集元素特点是：

*  以 0 或 1 的任意组合，任意数量为开头
 *  以 01 为结尾

当结尾为终结符时，可认为识别成功

[20190621004223453.png]: /images/20220109/c2eb074da5c7489dae9fa0d632960886.png
[20190621004319325.png]: /images/20220109/da61aeaaf9ce4102856873dda3042423.png