编译原理实验报告 实验名称 不确定有限状态自动机的确定化 实验时间 院系 计算机科学与技术学院 班级 学号 姓名 1 .试验目的 输入： 非确定有限（穷）状态自动机。 输出： 确定化的有限（穷）状态自动机 2 .实验原理 一个确定的有限自动机（DFA）M 可以定义为一个五元组，M＝（K，∑，F，S，Z），其中： （1） K 是一个有穷非空集，集合中的每个元素称为一个状态； （2） ∑是一个有穷字母表，∑中的每个元素称为一个输入符号； （3） F 是一个从K×∑→K 的单值转换函数，即 F（R，a）＝Q，（R，Q∈K）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q 称为状态R 的后继状态； （4） S∈K，是惟一的初态； （5） ZK，是一个终态集。 由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。 对于 DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M 所接受。若 M 的初态结点同时又是终态结点，则称ε可为M 所接受（或识别），DFA M 所能接受的全部字符串（字）组成的集合记作 L（M）。 一个不确定有限自动机（NFA）M 可以定义为一个五元组，M＝（K，∑，F，S，Z），其中： （1） k 是一个有穷非空集，集合中的每个元素称为一个状态； （2） ∑是一个有穷字母表，∑中的每个元素称为一个输入符号； （3） F 是一个从K×∑→K 的子集的转换函数； （4） SK，是一个非空的初态集； （5） ZK，是一个终态集。 由定义可见，不确定有限自动机NFA 与确定有限自动机DFA 的主要区别是： （1）NFA 的初始状态S 为一个状态集，即允许有多个初始状态； （2）NFA 中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即 DFA 中的F 是单值函数，而 NFA 中的F 是多值函数。 因此，可以将确定有限自动机DFA 看作是不确定有限自动机NFA 的特例。和 DFA 一样，NFA 也可以用矩阵和状态转换图来表示。 对于 NFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记（ε除外）连接形成的字符串可为M 所接受。NFA M 所能接受的全部字符串（字）组成的集合记作 L（M）。 由于 DFA 是NFA 的特例，所以能被 DFA 所接受的符号串必能被 NFA 所接受。 设 M1和 M2...
