你能解释一下吗，挑战？

Question

让我们看看，我有这段将 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;
    }

玩得开心!

Answer 1

您有 2 个函数 epClosure 和 makeDFAstate，它们将地址返回到局部变量。这是未定义的行为，并且可能是导致您出现问题的原因。

要解决这个问题，可以为变量动态分配内存(使用malloc)，或者采用一个地址作为参数写入，例如void epClosure(char stat, char* buf)。您可能还想传递缓冲区的大小，以确保您不会写入超过它的内容。