实验三有限自动机的构造与识别-白红宇

实验三有限自动机的构造与识别

阅读量：7055 次

发布时间：2019-06-28

本文共 2372 字，大约阅读时间需要 7 分钟。

一、实验目标

1、掌握有穷状态自动机的概念；

2、掌握有穷状态自动机的存储及表示方法；

3、掌握有穷状态自动机与正则式之间的关系。

二、实验要求

1、输入正规式；

2、构造该正规式的有穷状态自动机；

3. 以五元组形式输出。

三、算法

参见教材的转换规则。

练习：

² (a|b)^*abb

² l(l|d)^*

² 1(1010^*|1(010)^*1)^*0

四、完成算法设计、编码和调试工作，完成实验报告。

#include
     
      #include
      
       #include
       
        int main(){char p[30][30];char q[30][30];int line=0;int n;inti,j;int count=0;intk,t=0;int flag=0;intl,m=0;char VN[30]={
   '\0'};char VT[30]={
   '\0'};printf("规则数:");scanf("%d",&n);line=n;for(i=0;i<30;i++)for(j=0;j<30;j++)        {p[i][j]='\0';            q[i][j]='\0';        }printf("请输入文法:\n");for(i=0;i
        
         ='a'||(p[i][j]<='9'&&p[i][j]>='0'))                {flag=0;for(t=0;VN[t]!='\0';t++)                    {if(VN[t]==p[i][j])                        {flag=1;break;                        }                    }if(flag==0)                    {                        VN[l]=p[i][j];l++;                    }                }if(p[i][j]<='Z'&&p[i][j]>='A')                {flag=0;for(t=0;t<30&&(VT[t]!='\0');t++)                    {if(VT[t]==p[i][j])                        {flag=1;break;                        }                    }if(flag==0)                    {                        VT[m]=p[i][j];m++;                    }                }            }        }count=0;        k=0;for(i=0;i
         
          ='a')||(p[i][j]<='Z'&&p[i][j]>='A')||(p[i][j]<='9'&&p[i][j]>='0'))                {q[count][k]=p[i][j];k++;                }else                {count++;                    k=0;                }            }count++;            k=0;        }flag=0;for(i=0;i
          
           ='a')||(p[i][j]<='Z'&&p[i][j]>='A')||(p[i][j]<='9'&&p[i][j]>='0')) {q[count][k]=p[i][j];k++;j++; }if(p[i][j]=='l') {count++; k=0;j++; } } }count++; k=0; }printf("\n");printf("M:\n"); l=0;while(VN[l]!='\0') {printf("M(S,%c)={ ",VN[l]);for(i=0;i<30;i++) {for(j=4;j<30&&(q[i][j]!='\0');j++) { if(VN[l]==q[i][j]&&(q[i][j+1]=='\0')&&(q[i][j-1]=='='))printf("%c",q[i][0]); } }printf("}\t");l++; }printf("\n"); l=0;k=0;while(VT[k]!='\0') { l=0;while(VN[l]!='\0') {printf("M(%c,%c)={ ",VT[k],VN[l]);for(i=0;i<30;i++) {for(j=4;j<30&&(q[i][j]!='\0');j++) {if(VT[k]==q[i][j]&&VN[l]==q[i][j+1])printf("%c",q[i][0]); } }printf("}\t");l++; }k++;printf("\n"); }system("pause");}