#include<stdio.h>
#include <ctype.h>
#define ok 1
#define error 0
#define MAXREGLUARLONG 40
#define MAXSTATELONG 40
#define MAXCAHRSLONG 40
typedef int state;
int iCurrentState=0; //初態以1開始
int iPreState=0;
int iLastForkState=0;
int iForkState=0;
int iMaxState=0;
char cRegluarSting[MAXREGLUARLONG]; //輸入的正規式字符串
char cCharSet[MAXCAHRSLONG]; //字符集
int iStateMatrix[MAXSTATELONG][MAXCAHRSLONG]; //狀態轉換矩陣
state vStoreRegluarSting()//把字符串讀入一個緩沖區中
{
scanf("%s",cRegluarSting);
return ok;
}
state vPreProcessRegluarSting()
//對字符串進行預處理,去掉字符串里面的對分析不產生影響
{
int i=0;
while(cRegluarSting[i]!='\0')
{
if(cRegluarSting[i]=='*')
{
int j=i+1;
while(cRegluarSting[j-1]!='\0')
{
cRegluarSting[j-1]=cRegluarSting[j++];
}
}
i++;
}
return ok;
}
void vConstructStateMatrix(char cChar,int istate)//構造狀態轉換矩陣
{
int i;
for(i=0;cCharSet[i]!='\0';i++)
if(cChar==cCharSet[i])
break;
cCharSet[i]=cChar;
iStateMatrix[iPreState][i]=istate;
}
void vAanalyseRegluarSting()//對字符串進行從左到右的分析與處理
{
int i=0;
for(i=0;cRegluarSting[i]!=0;i++)
{
if(cRegluarSting[i]=='(') //NFA出現開始分叉情況
{
int iTheFirstl=0;
int iCharNumBeforl=0;
iForkState=iCurrentState;
while(cRegluarSting[i]!=')')
{
i++;
if(isalpha(cRegluarSting[i]))
{
if(cRegluarSting[i+1]==')')
iCurrentState=iLastForkState;
else
iCurrentState++;
iCharNumBeforl++; vConstructStateMatrix(cRegluarSting[i],iCurrentState);
iPreState=iCurrentState;
if(iCurrentState>iMaxState)
iMaxState=iCurrentState;
}
if(cRegluarSting[i]=='|')
{
iPreState=iForkState;
if(iTheFirstl==0)
{
iLastForkState=iCurrentState;
iTheFirstl++;
}
if(iCharNumBeforl==1&&cRegluarSting[i+2]=='|')
iCurrentState=iForkState;
iCharNumBeforl=0;
}
if(cRegluarSting[i]==')')
{
iPreState=iForkState=iLastForkState;
iCurrentState=iMaxState;
}
}
}
else
{
if(isalpha(cRegluarSting[i]))
{
iCurrentState++; vConstructStateMatrix(cRegluarSting[i],iCurrentState);
iPreState=iCurrentState;
if(iCurrentState>iMaxState)
iMaxState=iCurrentState;
}
}
}
}
void vPrintfStateProjectFunction()
{
int icCharSetPointer;
int iPreStatePointer;
for
(iPreStatePointer=0;iPreStatePointer<MAXSTATELONG;iPreStatePointer++)
for(icCharSetPointer=0;icCharSetPointer<MAXSTATELONG;icCharSetPointer++)
if(iStateMatrix[iPreStatePointer][icCharSetPointer]>0) printf("&(%d,%c)=%d\n",iPreStatePointer,cCharSet[icCharSetPointer],iStateMatrix[iPreStatePointer][icCharSetPointer]);
}
void vPrintfNfa()//輸出NFA
{
int iStateNumble;
int i=0;
printf("NFA的形式為:(S,$,&,S0,F)\n\n以下為NFA的具體集合內容:\n\n");
printf("字符集$為:{");
while(cCharSet[i]!=0)
if(cCharSet[i+1]==0)
printf("%c",cCharSet[i++]);
else
printf("%c,",cCharSet[i++]);
printf("}\n");
printf("\n狀態集S為:{");
for (i=0;i<=iMaxState;i++) {
if(i==iMaxState)
printf("%d",i);
else
printf("%d,",i);
}
printf("}\n\n");
vPrintfStateProjectFunction();
printf("\n初態集S0為:{0}\n\n");
printf("終態集F為:{%d}",iMaxState);
}
void main()
{
vStoreRegluarSting();
vPreProcessRegluarSting();
vAanalyseRegluarSting();
vPrintfNfa();
}

轉載于:https://www.cnblogs.com/xinmingwang/p/5051808.html

總結

以上是生活随笔為你收集整理的1118 实验三 有限自动机的构造与识别的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。