让我们看看，我有这段将 NFA 自动转换为 DFA 的代码；这是我编写的；我发现了一个“bug”；
printf()指令
这意味着像这样“printf("",X); ”以防止出现错误
没有要在屏幕上打印的字符，您可以使用任何您想要的参数；即使它没有值(value)。
问题是当您删除其中一条指令时，结果会颠倒(混合显示)
挑战是:详细解释这个错误!
该错误位于 NFAtoDFA() 函数第 69 和 75 行
这是代码:
#include <stdio.h>
#include <string.h>
#define max 50 //maximum number of symbols and states
#define true 1
#define false 0
#define epsilon '~'
char states [max]={'0','1','2','3','4','5','6','7','8','9','W'};
char initState='0';
char symbols[max]={epsilon,'a','b'};
char finalStates[max]={'W'};
char newSymbols[max]={'a','b'};
char newStates[max][max];
int nbrSymbols=3,nbrStates=11,nbrNewStates=0,nbrNewSymbols=0,nfaMaxLength=2,dfaMaxLength=0;
char NFA [max] [max] [max];
char DFA [max] [max] [max];
int mm ;
/** NDAtoDFA of the NFA */
void NDAtoDFA();
char *makeDFAstate (char state[],int c);
char *epClosure (char stat);
char *nextStates (char sta,char symb);
void add_no_rpt (char ss[],char aa[]);
int getCharIndex (char str[],char c);
int accepted (char str[],char toAccept[]) ;
int findDfaState (char str[]);
/*******************************/
/** flag = 0 | 1 */
/** keep ( 0 | 1 ) occurrences of char c in a string */
void del(char str[],char c,int flag);
/******************************/
/** printing Automates */
void shift(int b,int a);
void showNFA();
void showDFA();
int isFinalState(char state[]);
/******************************/
int main()
{
strcpy( NFA[0][0],"17");strcpy( NFA[1][0],"24");strcpy( NFA[2][1],"3");strcpy( NFA[3][0],"6");
strcpy( NFA[4][2],"5");strcpy( NFA[5][0],"6");strcpy( NFA[6][0],"17");strcpy( NFA[7][1],"8");
strcpy( NFA[8][2],"9");strcpy( NFA[9][2],"W");
NDAtoDFA();
}
/******************************************************/
/******************************************************/
void NDAtoDFA()
{
int i,j; char zz[max];
strcpy(newSymbols,symbols); del(newSymbols,epsilon,0);
nbrNewSymbols=strlen(newSymbols);
/** making the first state*/
strcpy(newStates[nbrNewStates++], epClosure(initState) );
/** */
printf("",mm); /** <=== */
for(i=0;i<nbrNewStates;i++)
{
for(j=0;j<nbrNewSymbols;j++)
{
strcpy(DFA[i][j],makeDFAstate(newStates[i],j));
printf("",mm); /** <=== */
if(findDfaState(DFA[i][j])==false) {strcpy(newStates[nbrNewStates++],DFA[i][j]);
if(strlen(DFA[i][j])>dfaMaxLength) dfaMaxLength=strlen(DFA[i][j]);//for printing DFA
}
}
}
showNFA();
printf("\n ");shift(dfaMaxLength,0); printf("[][][]");
printf("\n ");shift(dfaMaxLength,0); printf("|| ||");
printf("\n ");shift(dfaMaxLength,0); printf("|| ||");
printf("\n ");shift(dfaMaxLength,0); printf("|| ||");
printf("\n ");shift(dfaMaxLength,0); printf("|| ||");
printf("\n ");shift(dfaMaxLength,2);printf("[][] [][]");
printf("\n ");shift(dfaMaxLength,2);printf(" \\\\ //");
printf("\n ");shift(dfaMaxLength,2);printf(" \\\\ // ");
printf("\n ");shift(dfaMaxLength,2);printf(" \\\\// ");
printf("\n ");shift(dfaMaxLength,2);printf(" \\/ ");
showDFA();
}
/******************************************************/
/******************************************************/
void add_no_rpt(char ss[],char aa[])
{int i,j;char tt[1];
for (i=0;aa[i]!=0;i++) if(getCharIndex(ss,aa[i])==-1) {tt[0]=aa[i];tt[1]=0;strcat(ss,tt);}
}
/******************************************************/
/******************************************************/
void del(char str[],char c,int flag)
{
char * p,*barrier;
barrier=p=strchr(str,c);
if (flag==1)
{
barrier=p+1; //set the barrier after the first occurrence of c
p=strchr(barrier,c);
}
while (p!=NULL)
{
for (;*p!='\0';p++) *p=*(p+1);
p=strchr(barrier,c);
}
}
/******************************************************/
/******************************************************/
char* nextStates (char sta,char symb)
{ int i,j;
for(i=0;i<nbrStates ;i++) if(sta ==states [i]) break;
for(j=0;j<nbrSymbols;j++) if(symb==symbols[j]) break;
return NFA[i][j];
}
/******************************************************/
/******************************************************/
int accepted (char str[],char toAccept[])
{ int i;
for (i = 0 ; toAccept[i]!=0; i++)
{
if(toAccept[i]==' ') {del(toAccept,toAccept[i],0);if(i!=0) i--;}
if(getCharIndex(symbols,toAccept[i])!=-1 || getCharIndex(str,toAccept[i])==-1) {return false;}
}
return true;
}
/******************************************************/
/******************************************************/
int getCharIndex(char str[],char c)
{
int i;
for (i = 0 ; str[i]!=0; i++) if(str[i]==c) return i;
return -1;
}
/******************************************************/
/******************************************************/
void showNFA()
{int i,j;
printf("\nSYMBOLS: %s\n",symbols);
printf("STATES : %s\n",states);
printf("FINAL STATES : %s\n\n",finalStates);
puts("STATE TRANS.");
printf("\n ");shift(dfaMaxLength+2,4);printf("NFA | ");
for (i = 0; i < nbrSymbols; i++) {printf(" %c", symbols[i]);shift(nfaMaxLength+1,0);}
printf("\n ");shift(dfaMaxLength+2,0);printf("--------");
for (i = 0; i < nbrSymbols; i++) for(j=0;j<nfaMaxLength+3;j++) printf("-"); printf("\n");
for (i = 0; i < nbrStates; i++) {
shift(dfaMaxLength+3,0);
printf(" %c | ",states[i]);
for (j = 0; j < nbrSymbols; j++)
{
if(strcmp(NFA[i][j],"")==0) {printf(" -");shift(nfaMaxLength+1,strlen(NFA[i][j]));}
else {printf(" %s",NFA[i][j]);shift(nfaMaxLength+2,strlen(NFA[i][j]));}
}
printf("\n");
}
}
/******************************************************/
/******************************************************/
void shift(int b,int a)
{int i;
for (i = 0; i < (b-a); i++)printf(" ");
}
/******************************************************/
/******************************************************/
void showDFA()
{int i,j;
printf("\n\n ");shift(dfaMaxLength,5);printf("DFA |");shift(5,0);
for (i = 0; i < nbrNewSymbols; i++) {printf("%c", newSymbols[i]);shift(dfaMaxLength+5,0);}
printf("\n ");for(j=0;j<dfaMaxLength+6;j++)printf("-");
for (i = 0; i < nbrNewSymbols; i++)for(j=0;j<dfaMaxLength+4;j++)printf("-"); printf("\n");
for (i = 0; i<nbrNewStates; i++) {
if (isFinalState(newStates[i])==true)
if (i==0) printf(" <-> ");
else printf(" <-- ");
else
if (i==0) printf(" --> ");
else printf(" ");
printf("{%s}",newStates[i]);shift(dfaMaxLength,strlen(newStates[i]));printf(" |");
for (j = 0; j < nbrNewSymbols; j++)
printf(" {%s} ",DFA[i][j]);
printf("\n");
}
}
/******************************************************/
/******************************************************/
char*epClosure(char stat)
{ int i,j;char zz[max];
zz[0] = stat; zz[1]=0;
for (i=0;zz[i]!=0;i++) add_no_rpt(zz,nextStates(zz[i],epsilon));
return zz;
}
/******************************************************/
/******************************************************/
int findDfaState(char str[])
{
int i;
for(i=0;i<nbrNewStates;i++)
{
if (accepted(newStates[i],str)==true && strlen(str)==strlen(newStates[i])) return true;
}
return false;
}
/******************************************************/
/******************************************************/
int isFinalState(char state[])
{
int i;
for(i=0;state[i]!=0;i++) if (strchr(finalStates,state[i])!=NULL) return true;
return false;
}
/******************************************************/
/******************************************************/
char *makeDFAstate(char state[],int c)
{
int i,j;char kk[max],yy[max];
for (i=0;state[i]!=0;i++)
{
add_no_rpt(kk,nextStates(state[i],newSymbols[c]));
j=strlen(kk)-1;
add_no_rpt(kk,epClosure(kk[j]));
}
return kk;
}
玩得开心!
最佳答案
您有 2 个函数 epClosure 和 makeDFAstate，它们将地址返回到局部变量。这是未定义的行为，并且可能是导致您出现问题的原因。
要解决这个问题，可以为变量动态分配内存(使用malloc)，或者采用一个地址作为参数写入，例如void epClosure(char stat, char* buf)。您可能还想传递缓冲区的大小，以确保您不会写入超过它的内容。
关于你能解释一下吗，挑战？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34190250/