有穷自动机如何实现？

有穷自动机，或有穷状态的机器，是描述（或“机器”）特定类型算法的数学方法。特别地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。当然有穷做袭激自动机与正则表达式之间有着很密切的关系，在下一节中大家将会看到如何从正则表达式中构造有穷自动机。但在学习有穷自禅烂动机之前，先看一个说明的示例。通过下面的正则表达式可在程序设计语言中给出标识符模式的一般定义（假设已定义了letter 和digit）：identifier = letter ( letter | digit ) *它代表以一个字母开头且其后为任意字母和/ 或数字序列的串。

有穷自动机通过标明数字1 和2 的圆圈表示的是状态（state），它们表示其中记录已被发现的模式的数量在识别过程中的位置。带有箭头的线代表由记录一个状态向另一个状态的转换（transition），该转换依赖纯袜于所标字符的匹配。有穷自动机又分为确定型的有穷自动机（DFA）与非确定型的有穷自动机（NFA）两种。http://www.douban.com/note/74804011/

#include"stdio.h"

#include"string.h"

char a[20][10]

char Vn[26]

char Vt[64]

int M=0 //Vn下标

int N=0 //Vt下标

int m=0

int flag=-1 //又穷状态自动机是确定与非确定的标志

void initial() //初始拿带化

{

for(int b=0b<26b++)

Vn[b]='#'

for(int c=0c<64c++)

Vt[c]='#'

for(int d=0d<20d++)

for(int e=0e<10e++)

a[d][e]='#'

}

void group()//判断终结符号与非终结符

{

for(int k=0a[k][0]!='e'k++)

{

for(int f=0a[k][f]!='\0'f++)

{

if((a[k][f]>='A')&&(a[k][f]<='Z'))

{

for(int x=0x<=M&&M<=27x++)

if(Vn[x]==a[k][f])

break

if((x-1)==M)

{

Vn[M]=a[k][f]

M++

}

}

else

{

for(int y=0y<=N&&N<=20y++)

{

if(a[k][f]==':'||a[k][f]=='=')

break

else

{

if(Vt[y]==a[k][f])

break

}

}

if((y-1)==N)

{

Vt[N]=a[k][f]

N++

}

}

}

}

}

void input() //输入文法

{

for(int i=0i<10i++)

a[m][i]='#'

scanf("%s",a[m])

while(strcmp(a[m],"end"))

{

if((a[m][0]>='A')&&(a[m][0]<='Z')) //判断是否为正则文法

{

int h=4

if((a[m][h]>='A')&&(a[m][h]<='Z'))//U::=WT

{

if((a[m][h+1]<'A')||(a[m][h+1]>'Z'))

{

if(a[m][h+2]!='\0')

{

printf("此规则不是正则文法的规则，请重新输入\n")

input()

break

}

}

else

{

printf("此规则不是正则文法的规则，请重新输入\n")

input()

break

}

}

else

{

if(a[m][h+1]!='\0')//U::=T

{

printf("此规则不是正则文法的规则，请重新输入\n")

input()

break

}

}

}

m++

scanf("%s",a[m])

}

}

void recongnise() //判消裂芦断是确定还是源隐非确定

{

for(int i=0a[i][0]!='e'i++)

{

for(int j=i+1a[j][0]!='e'j++)

{

int n=4

if(a[i][n]==a[j][n])

n++

if(a[i][n]==a[j][n])

break

}

int h=4

if(a[i][h]==a[j][h])

h++

if(a[i][h]==a[j][h]) //U::=T

{

printf("此文法对应的有穷状态自动机是非确定的\n\n")

flag=0

break

}

}

if(a[i][0]=='e') //U::=WT

{

printf("此文法对应的有穷状态自动机是确定的\n\n")

flag=1

}

}

void output() //输出文法相应的有穷状态自动机

{

if(flag==0)

{

printf("NFA N=({")

for(int i=0Vn[i]!='#'i++)

printf("%c,",Vn[i])

printf("S},{")

for(int j=0Vt[j]!='#'j++)

printf("%c,",Vt[j])

printf("},M',{S},{%c})\n",Vn[0])

printf("其中M':\n")

for(int x=0Vn[x]!='#'x++)

{

for(int y=0Vt[y]!='#'y++)

{

printf("M'(%c,%c)=",Vn[x],Vt[y])

for(int z=0a[z][0]!='e'z++)

if(a[z][4]==Vn[x])

if(a[z][5]==Vt[y])

printf("%c",a[z][0])

if(a[z][0]=='e')

printf("\t")

}

printf("\n")

}

for(int u=0Vt[u]!='#'u++)

{

printf("M'(S,%c)=",Vt[u])

for(int k=0a[k][0]!='e'k++)

if(a[k][4]==Vt[u])

printf("%c",a[k][0])

if(a[k][0]=='e')

printf("\t")

}

}

if(flag==1)

{

printf("DFA N=({")

for(int b=0Vn[b]!='#'b++)

printf("%c,",Vn[b])

printf("S},{")

for(int c=0Vt[c]!='#'c++)

printf("%c,",Vt[c])

printf("},M',S,{%c})\n",Vn[0])

printf("其中M':\n")

for(int p=0Vn[p]!='#'p++)

{

for(int q=0Vt[q]!='#'q++)

for(int r=0a[r][0]!='#'r++)

if(a[r][4]==Vn[p])

if(a[r][5]==Vt[q])

printf("M'(%c,%c)=%c\t",Vn[p],Vt[q],a[r][0])

printf("\n")

}

for(int d=0Vt[d]!='#'d++)

{

for(int e=0a[e][0]!='e'e++)

if(a[e][4]==Vt[d])

printf("M'(S,%c)=%c\t",Vt[d],a[e][0])

}

}

}

void main()

{

initial()

printf("请输入文法:\n")

input()

group()

printf("\n")

recongnise()

output()

printf("\n")

}

输入的是形如U::=T和U::=WT这种类型的正则文法，没有U::=TW这种文法的输入。这个程序基本上齐全，如果输入的文法不是正则文法，会给出提示重新输入的。祝君好运，记得给分哦！！！！这可是花了一周才写出来的，而且输出的状态自动机是按非终结符号的顺序输出的，而不是按文法的顺序输出，绝对达标。

---