编译原理不确定有穷自动机的确定化.

1、编译原理实验报告实验三 安徽大学计算机科学与技术学院 鉏飞祥E214140181， 实验名称不确定有穷自动机的确定化。2， 实验目的不确定有穷自动机的确定化。3， 实验原理1.NFA：一个不确定的有穷自动机M是一个五元组，M=(K,E,f,S,Z)其中a. K是一个有穷集，它的每个元素称为一个状态；b. E是一个有穷字母表，它的每个元素称为一个输入符号；c. f是一个从K×E*到K的子集的映像，即：K*E*->2k，其中2k表示K的幂集；d. S包含于K，是一个非空初态集；e. Z包含于K，是一个终态集。2.DFA：一个确定的有穷自动机M是一个五元组，M=(K,E,f,S,Z)

2、其中a. K是一个有穷集，它的每个元素称为一个状态；b. E是一个有穷字母表，它的每个元素称为一个输入符号；c. f是转换函数，是K×E->K上的映像，即，如f(ki,a)=kj(kiK,kjK)就意味着，当前状态为ki，输入字符为a时，将转换到下一状态kj，我们把kj称作ki的一个后继状态；d. SK，是唯一的一个初态；e. Z包含于K，是一个终态集，终态也称可接受状态或结束状态。 3，正规式正规式是一种表示正规集的工具，正规式是描述程序语言单词的表达式，对于字母表其上的正规式及其表示的正规集可以递归定义如下。 是一个正规式，它表示集合L()=。 若a是上的字符，则a是一个正

3、规式，它所表示的正规集L(a)=a。 若正规式r和s分别表示正规集L(r)、L(s)，则（a）r|s是正规式，表示集合L(r)L(s)；（b）r·s是正规式，表示集合L(r)L(s)；（c）r*是正规式，表示集合(L(r)*；（d）(r)是正规式，表示集合L(r)。仅由有限次地使用上述三个步骤定义的表达式才是上的正规式。运算符“|”、“·”、“*”分别称为“或”、“连接”和“闭包”。在正规式的书写中，连接运算符“·”可省略。运算符的优先级从高到低顺序排列为：“*”、“·”、“|”。运算符“|”表示“或”、并集。“*”表示*之前括号里的内容出现0次或多次。

4、若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规集U和V记作U=V。4. 实验思路1.状态集合I的空闭包closure（I），定义为一个状态集。 算法：遍历I集合中的每一个元素，对于每一元素遍历所有的边，若该元素在NFA中连接到空边，则获取空边另一端的元素，判断元素是否在I中，若不在I中，则加入I，直到遍历结束。2.确定化算法：A 找到NFA的开始符S，对开始符求closure（S），并创建集合T并T（0）=closure（S）B 找到T中未被标记的集合T1，若未找到，C 对T1中，每一元素，执行函数FD 执行步骤B函数F：A 对于T1中的每一元素a，找到每一元素在NFA同一类型的

5、边所对应的元素c，把所有的c都放在集合C中，对于C求C=closure（C）。判断C是否在T中，若不在，则把C加入T。，记录T1->C的边，B 执行A，知道把所有不同类型的边遍历为止。3.构造DFAa.对于集合In，选出集合In的每一I，在I中选出一个元素代表该集合，构造新的DFA5. 实验小结 实验算法清晰，简单，只要是对于每一集合反复求closure闭包比较麻烦。程序循环，判断，标志位特别多。很容易出错。对于程序的内存管理更要小心，不要内存越界。同时，我用的code blocks 编译器问题很大。当程序代码超过一定量、内存分配的数目和空间比较多的时候，对于内存的管理就会出现难以预料的

6、错误。比如在程序开头分配了一段内存，在程序的末尾要使用该内存给其他变量赋值时，就会导致程序崩溃。6. 实验截图课本P58图4.4输入输出附件#include<stdio.h>#include<malloc.h>#include<string.h>char nfa254;    struct list            char a20;  

7、0;      int  b;         char c;         int a_n;         struct list t20;    int 

8、;n; /*number of NFA edage*/int main()    printf("鉏飞祥E21414018n");    int cg=3;    printf("请输入每条边和节点n例如：1a8表示0从1边到8，*代表空边以/结束输出n");    void closure(int n); 

9、   char u20;    int  ed204;    int n_ed=0;    n=0;    int n_t=0;/*number of T */    int i=0;    int k=1;  

10、;  int j;    while(1)            scanf("%s",nfai);        if(nfai0='/')            brea

11、k;        i+;         n+;        t0.a0=nfa00;    for(i=0;i<n;i+)            if(nfai0=nfa00)&

12、#160;                   if(nfai1='*')                          

13、0; t0.ak=nfai2;                k+;                            t0.a_n=k;

14、0;   t0.ak='0'    n_t+;    t0.b=0;    closure(0);    char temp;    for(i=0;i<n_t;i+)        for(j=0;j+)    &#

15、160;               if(ti.aj='0')                break;        for(k=j+1;k+)   

16、0;        if(ti.ak='0')            break;        if(ti.ak<ti.aj)              &

17、#160;     temp=ti.ak;            ti.ak=ti.aj;            ti.aj=temp;              

18、60;         int u_i;    int nn=n_t;    while(1)            u_i=0;        int bo=0;   

19、     int t_i;        for(t_i=0;t_i<n_t;t_i+)/*judge over*/                    if(tt_i.b=0)     &#

20、160;                      tt_i.b=1;                bo+;         &

21、#160;      break;                            if(bo=0)            break

22、;        char a='a'           int cc=cg; /*有几条不同的边*/        while(cc-)            

23、        u_i=0;        for(i=0;i<tt_i.a_n;i+)                    for(j=0;j<n;j+)      

24、;                      if(tt_i.ai=nfaj0)                    if(nfaj1=a)   &

25、#160;                            int b1=0;                int ii; 

26、;               for(ii=0;ii<u_i;ii+)                               

27、     if(uii=nfaj2)                        b1=1;                  

28、              if(b1=0)                    uu_i=nfaj2;             

29、;       u_i+;                                          

30、  uu_i='0'        int i,j,k;    for(i=0;i<u_i;i+)        for(j=0;j<n;j+)                

31、60;   if(ui=nfaj0)                if(nfaj1='*')                         

32、   int b1=0;                int ii;                for(ii=0;ii<u_i;ii+)       

33、;                             if(uii=nfaj2)                  

34、0;     b1=1;                                if(b1=0)          

35、60;                     uu_i=nfaj2;                u_i+;          

36、;                                  uu_i='0'        char temp;  

37、0;     for(i=0;i<u_i;i+)            for(j=i+1;j<u_i;j+)                    if(uj<ui)   

38、0;                        temp=uj;                uj=ui;       &#

39、160;        ui=temp;                            bo=0;        for(i=0;i<n_t;i+

40、)                    if(strcmp(u,ti.a)=0)                          

41、60; bo+;                 edn_ed0=nn-1;            edn_ed1=(int)a;            edn_ed2=i;

42、60;           n_ed+;                break;                    

43、60;       if(bo=0)            if(u_i!=0)                    strcpy(tn_t.a,u);    

44、0;       tn_t.b=0;            tn_t.a_n=u_i;            edn_ed0=nn-1;            edn_e

45、d1=(int)a;            edn_ed2=n_t;            n_ed+;            n_t+;        

46、60;       a+;                 nn+;        for(i=0;i<n_t;i+)            ti.c=t

47、i.ai;            printf("用 %c  代表 %sn",ti.c,ti.a);     for(i=0;i<n_ed;i+)                  &

48、#160; printf("%c-%c-%cn",tedi0.c,edi1,tedi2.c);        void closure(int nn)    int i,j,k;    int ii,jj;    for(i=0;i<tnn.a_n;i+)        for(j=0;j<n;j+)                    if(t