#include<string.h>

#include<stdio.h>

#include<stdlib.h>

int main()

{

char p[30][30];//存放文法

char q[30][30];

int line=0;

int n;

int i,j;

int count=0;

int k,t=0;

int flag=0;

int l,m=0;

char VN[30]={'\0'};//存放非终结符号

char VT[30]={'\0'};//存放终结符号

printf("请输入规则个数");

scanf("%d",&n);

line=n;

for(i=0;i<30;i++)//给字符串数组p,q全部赋值为'\0'

for(j=0;j<30;j++)

{

p[i][j]='\0';

q[i][j]='\0';

}

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

for(i=0;i<line;i++)

{

scanf("%s",p[i]);

}

//把字符分为终结符和非终结符

l=0;

m=0;

for(i=0;i<line;i++)

{

for(j=0;j<30&&(p[i][j]!='\0');j++)

{

//非终结符放入数组VN中

if(p[i][j]<='z'&&p[i][j]>='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++;

}

}

//终结符放在数组VT中

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++;

}

}

}

}

//把规则右部分分离，放入数组q中

count=0;

k=0;

for(i=0;i<line;i++)

{

for(j=4;j<30&&(p[i][j]!='\0');j++)

{

if((p[i][j]<='z'&&p[i][j]>='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;

}

//判断是确定的还是非确定的有穷状态自动机，并进行前半部分打印

//判断依据：q数组中每一行字符串是否相同

flag=0;

for(i=0;i<count;i++)

{

for(j=i+1;j<count;j++)

{

if(strcmp(q[i],q[j])==0)

{

flag=1;

break;

}

}

}

if(flag==1)

{

printf("是非确定的有穷状态自动机，即NFA\n\n");

printf("构造的有穷状态自动机为:\n");

printf("NFA N=(K,E(总和的意思),M,{S},{Z})\n");

}

else

{

printf("是确定的有穷状态自动机，即DFA\n\n\n");

printf("构造的有穷状态自动机为:\n");

printf("DFA N=(K,E(总和的意思),M,{S},{Z})\n");

}

printf("其中，\nK={S");

for(i=0;i<30&&(VT!='\0');i++)

{

printf(",%c",VT[i]);

}

printf("}\n");

printf("E={");

for(i=0;i<30&&(VN[i]!='\0');i++)

{

printf("%c ",VN[i]);

}

printf("}\n");

//分离文法

k=0;

count=0;

for(i=0;i<line;i++)

{

j=4;

while(p[i][j]!='\0')

{

if(k<4)

{

q[count][k]=p[i][k];

k++;

}

else

{

if((p[i][j]<='z'&&p[i][j]>='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");

//打印M后部分

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");

}