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

一、实验目标

1、掌握有穷状态自动机的概念；
2、掌握有穷状态自动机的存储及表示方法；
3、掌握有穷状态自动机与正则式之间的关系。

二、实验要求

1、输入正规式；

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

3. 以五元组形式输出。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #define N 100
  4 char r[N];
  5 int s,t;
  6 int q=1;
  7 struct f{
  8     char r;
  9     int  a;
 10     int  b;
 11 };
 12 typedef struct f F;
 13 
 14 F f[50];
 15 int n=0;
 16 
 17 main()
 18 {   char ch;
 19     int p=0;
 20     int j;
 21 
 22       printf("
请输入正规式(以'#'结束): ");
 23       do
 24       {
 25           ch=getchar();
 26           r[p++]=ch;
 27       }while (ch!='#');
 28 
 29       r2nfa(r,0,p-1,0,1);
 30 
 31       printf("
nfa的分列过程如下：");
 32       for (j=0;j<n;j++)
 33       {
 34            printf("
 f(%d, %c)=%d 
",f[j].a,f[j].r,f[j].b);
 35       }
 36 
 37       system("pause");
 38 
 39 
 40   }
 41 
 42 
 43 r2nfa(char r[],int s,int t,int a,int b)
 44 {   int i;
 45 
 46     if (t-s==1)
 47     {
 48         f[n].a=a;
 49         f[n].r=r[s];
 50         f[n].b=b;
 51         n++;
 52     }
 53     else
 54     {
 55         i=lowest(r,s,t);
 56 
 57         if (r[i]=='|')
 58         {
 59             r2nfa(r,s,i,a,b);
 60             r2nfa(r,i+1,t,a,b);
 61         }
 62 
 63         else if (r[i]=='.')
 64         {
 65             q++;
 66             r2nfa(r,s,i,a,q);
 67             r2nfa(r,i+1,t,q,b);
 68         }
 69 
 70         else
 71         {
 72             q++;
 73 
 74             f[n].a=a;
 75             f[n].r='~';
 76             f[n].b=q;
 77             n++;
 78 
 79             f[n].a=q;
 80             f[n].r='~';
 81             f[n].b=b;
 82             n++;
 83 
 84             r2nfa(r,s,t-1,q,q);
 85         }
 86     }
 87 }
 88 
 89 int lowest(char r[],int s,int t)
 90 {   int i,j;
 91     int priority=5;
 92 
 93     for (j=s;(j<t);j++)
 94     {
 95         switch(r[j])
 96         {
 97             case '|':
 98                 if (priority>1)
 99                     {
100                         i=j;
101                         priority=1;
102                     }
103                 break;
104              case '.':
105                  if (priority>2)
106                     {
107                         i=j;
108                         priority=2;
109                     }
110                 break;
111              case '*':
112                   if (priority>3)
113                     {
114                         i=j;
115                         priority=3;
116                         }
117                 break;
118              default:  ;
119         }
120     }
121     return i;
122 }

自动机nfa

状态0（初态）->状态1（终态）的过程

运行结果如图所示：

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

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