内容发布更新时间 : 2024/5/30 11:57:40星期一 下面是文章的全部内容请认真阅读。
实验二
实验名称：不确定有穷状态自动机的确定化 实验目的：输入：非确定有穷状态自动机NFA 输出：确定化的有穷状态自动机DFA 实验原理：
a.一个确定的有限自动机（DFA）M可以定义为一个五元组，M＝（K，∑，f，S，Z），其中：
（1） K是一个有穷非空集，集合中的每个元素称为一个状态； （2） ∑是一个有穷字母表，∑中的每个元素称为一个输入符号； （3） f是一个从K×∑→K上的映像，即f（P，a）＝Q，（P，Q∈K）表示当前状态为P，如果输入字符a，则转到状态Q，状态Q称为状态P的后继状态；
（4） S∈K，是惟一的初态； （5） Z
b. 一个不确定有限自动机（NFA）M可以定义为一个五元组，M＝（K，∑，f，S，Z），其中：
（1） k是一个有穷非空集，集合中的每个元素称为一个状态； （2） ∑是一个有穷字母表，∑中的每个元素称为一个输入符号； （3） f是一个从K×∑→K的子集的映像； （4） S（5） Z
K，是一个非空的初态集； K，是一个终态集。 K，是一个终态集。
C.在有穷自动机理论中，有这样的定理：设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机；使用子集法的算法实现将NFA转换成接受同种语言的DFA。 实验思路：
(1)若NFA的全部初态为S1，S2，…，Sn，则令DFA的初态为：
S＝[S1，S2，…，Sn]，
其中方括号用来表示若干个状态构成的某一状态。
(2)设DFA的状态集K中有一状态为[Si，Si+1，…，Sj]，若对某符号a∈∑，在NFA中有F（{ Si，Si+1，…，Sj }，a）={ Si’，Si+1’，…，Sk’ } 则令F（{ Si，Si+1，…，Sj }，a）={ Si’，Si+1’，…，Sk’ }为DFA的一个转换函数。若[ Si’，Si+1’，…，Sk‘ ]不在K中，则将其作为新的状态加入到K中。
(3)重复第2步，直到K中不再有新的状态加入为止。
(4)上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表∑。
(5)DFA中凡是含有NFA终态的状态都是DFA的终态。
对于上述NFA确定化算法——子集法，还可以采用另一种操作性更强的描述方式，下面我们给出其详细描述。首先给出两个相关定义。
假设I是NFA M状态集K的一个子集（即I∈K），则定义ε-closure（I）为：
(1)若Q∈I，则Q∈ε-closure（I）；
(2)若Q∈I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’∈ε-closure（I）。
状态集ε-closure（I）称为状态I的ε闭包。
假设NFA M＝（K，∑，F，S，Z），若I∈K，a∈∑，则定义Ia＝ε-closure（J），其中J是所有从ε-closure（I）出发，经过一条a弧而到达的状态集。
NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。 实验小结： 附件：
a.实验代码：#include
typedef struct byInfo{ char ch;// int index; }byInfo;
//节点信息数据结构 typedef struct nfaNode{