本文涉及在编译原理课程学习过程中的一些解题技巧和方法
一、根据正规表达式构造对应的DFA
1.整体思路：
- 首先根据正规表达式画出相应的NFA状态图
-
根据NFA状态图构建状态转化表：
当前状态 输入0 输入1 注意：从初始状态X开始，要将输入0和输入1两列中的所有集合都作为当前状态求各自在输入0和输入1之后对应的状态集合，直到出现在右边两列的集合全部作为当前状态出现在最左边一列。
-
对状态转化表重命名:
- 对于出现在状态转化表中的所有集合（只要集合中的元素不完全相同）进行重新命名
- 根据重命名之后的状态转化表画出新的状态图即就是DFA
- 对于DFA进行最小化处理：
- 先将所有状态划归成终结符集和非终结符集
- 根据输入$I_1$和$I_0$对上述集合进行拆分：
- 当集合中的不同元素经过同一个输入得到的新状态不在同一个集合时：将输出不同的对应元素拆分成不同的集合；而将对于同一个输入得到相同输出（输出属于同一个集合）的元素划归到同一个集合中。
- 新得到的集合（集合之间的元素具有等价性）就是最终DFA中的一个状态。
2.示例：
注意：在最小化的过程中，如果有新的集合产生，则要重复进行划分操作，直到根据不同输入产生的划分结果保持不变时才可以说划分完成，得到最小化的DFA。
二、左右线性文法的相互转化
1.整体思路：根据给定的文法绘制状态图，对于终态引入新的标志表示，从新的标志出发，反向得出被转化文法（对于原来文法的初态，若有表达式，则保留；若无表达式，则删除）
2.示例：
