005
04.04.2005, 20:31 Uhr
rejo
|
Hallo hab da ein Fehler den ich irgendwie nicht verstehe bzw. es lösen kann.
Es ist so...
wenn man bei init_NFA_table() das auskommentierte lässt und alles andere weglässt dann gehts! aber jetzt hab ich ne eingabe geschrieben und die tabelle bleibt bis zum funktionsaufruf von nfa_to_dfa gleich,.. dann in der funktion hohlt er von der tabelle etwas was garnicht drinn steht... =( kann mir jemand helfen.
| C++: |
#include <stdio.h>
#include <string.h>
#include "hilfschirm.cpp"
#include <conio.h>
#include <stdlib.h>
#define STATES 10
#define SYMBOLS 5
int N_symbols;
int NFA_states;
char *NFAtab[STATES][SYMBOLS];
char *NFA_finals;
int DFA_states;
int DFAtab[STATES][SYMBOLS];
char DFA_finals[STATES];
char statename[STATES][STATES];
void put_dfa_table(int tab[][SYMBOLS], int nstate, int nsymbol, char *finals)
{
int i, j;
printf(" | ");
for (i = 0; i < nsymbol; i++) printf(" %c ", 'a'+i);
printf("\n---+--");
for (i = 0; i < nsymbol; i++) printf("---");
printf("\n");
for (i = 0; i < nstate; i++)
{
printf(" %c | ", 'A'+i);
for (j = 0; j < nsymbol; j++)
printf(" %c ", 'A'+tab[i][j]);
printf("\n");
}
printf("Start state = A\nFinal states = %s\n", finals);
}
void put_table(int nsymbol, int nstate)
{
int i;
printf(" | ");
for (i = 0; i < nsymbol; i++) printf(" %c ", 'a'+i);
printf("\n---+--");
for (i = 0; i < nsymbol; i++) printf("---");
printf("\n");
for (i = 0; i < nstate; i++)
{
printf(" %c | \n", 'A'+i);
}
}
void init_NFA_table()
{
/*NFAtab[0][0] = "01"; NFAtab[0][1] = "0";
NFAtab[1][0] = "2"; NFAtab[1][1] = "";
NFAtab[2][0] = "3"; NFAtab[2][1] = "";
NFAtab[3][0] = ""; NFAtab[3][1] = "4";
NFAtab[4][0] = "45"; NFAtab[4][1] = "4";
NFAtab[5][0] = "6"; NFAtab[5][1] = "";
NFAtab[6][0] = ""; NFAtab[6][1] = "";
NFA_states = 7;
DFA_states = 0;
N_symbols = 2;
NFA_finals = "36";*/
int i, check, j, k, p = 0;
char temp[STATES], temp2[2*STATES][STATES];
for(i = 0; i < STATES; i++)
{
temp[i] = '\0';
}
for(i = 0; i < (2*STATES); i++)
for(j = 0; j < STATES; j++)
temp2[i][j] = '\0';
do
{
printf("Enter number of NFA states: ");
scanf("%s", temp);
for(i = 0; temp[i] != '\0'; i++)
{
if(isdigit(temp[i]))
check = 1;
else
check = 0;
}
NFA_states = atoi(temp);
}while((check == 0 && printf("Error - Enter a number\n")) || ((NFA_states < 1 || NFA_states > 10) && printf("Error - Out of range (1 - 10)\nfd")));
for(i = 0; i < STATES; i++)
temp[i] = '\0';
do
{
printf("Enter number of symbols: ");
scanf("%s", temp);
for(i = 0; temp[i] != '\0'; i++)
{
if(isdigit(temp[i]))
check = 1;
else
check = 0;
}
N_symbols = atoi(temp);
}while((check == 0 && printf("Error - Enter a number\n")) || ((N_symbols < 1 || N_symbols > 5) && printf("Error - Out of range (1 - 5)\nfd")));
for(i = 0; i < STATES; i++)
{
temp[i] = '\0';
}
do
{
printf("Enter NFA final states: ");
scanf("%s", temp);
for(i = 0; temp[i] != '\0'; i++)
{
if(isalpha(temp[i]))
check = 1;
else
check = 0;
}
}while(check == 0 && printf("Error - Enter a character\n"));
NFA_finals = temp;
for(i = 0; i < STATES; i++)
temp[i] = '\0';
clrscr();
put_table(N_symbols,NFA_states);
for(j = 1; j <= NFA_states; j++)
{
for(k = 1; k <= N_symbols; k++)
{
switch(k)
{
case 1: gotoxy(k+6,j+2); break;
case 2: gotoxy(k+6+2,j+2); break;
case 3: gotoxy(k+6+4,j+2); break;
case 4: gotoxy(k+6+6,j+2); break;
case 5: gotoxy(k+6+8,j+2); break;
}
printf("x");
gotoxy(0,20);
do
{
printf("Enter states (e.g.:\"AB\"): ");
scanf("%s", temp);
for(i = 0; temp[i] != '\0'; i++)
{
if(isalpha(temp[i]))
check = 1;
else
check = 0;
}
}while(check == 0 && printf("Error - Enter a characters\n"));
for(i = 0; i < STATES && temp[i] != '\0'; i++)
{
switch(toupper(temp[i]))
{
case 'A': strcat(temp2[p],"0"); break;
case 'B': strcat(temp2[p],"1"); break;
case 'C': strcat(temp2[p],"2"); break;
case 'D': strcat(temp2[p],"3"); break;
case 'E': strcat(temp2[p],"4"); break;
case 'F': strcat(temp2[p],"5"); break;
case 'G': strcat(temp2[p],"6"); break;
case 'H': strcat(temp2[p],"7"); break;
case 'I': strcat(temp2[p],"8"); break;
case 'J': strcat(temp2[p],"9"); break;
default: strcat(temp2[p],"\0");
}
}
NFAtab[j-1][k-1] = temp2[p];
p++;
}
}
}
void string_merge(char *s, char *t)
{
char temp2[STATES];
char *r = temp2;
char *p = s;
while (*p && *t)
{
if (*p == *t)
{
*r++ = *p++;
t++;
}
else if (*p < *t)
*r++ = *p++;
else
*r++ = *t++;
}
*r = '\0';
if (*p) strcat(r, p);
else if (*t) strcat(r, t);
strcpy(s, temp2);
}
void get_next_state(char *nextstates, char *cur_states, char *nfa[STATES][SYMBOLS], int symbol)
{
int c;
char temp[STATES];
temp[0] = '\0';
for (c = 0; c < strlen(cur_states); c++)
string_merge(temp, nfa[cur_states[c]-'0'][symbol]);
strcpy(nextstates, temp);
}
int state_index(char *state, char state_name[][STATES], int *pn)
{
int k;
for (k = 0; k < *pn; k++)
{
if (!strcmp(state, state_name[k]))
return k;
}
strcpy(state_name[k], state);
return (*pn)++;
}
int nfa_to_dfa(char *nfa[STATES][SYMBOLS], int n_nfa, int n_sym, int dfa[][SYMBOLS])
{
int i = 0;
int n = 1;
char nextstate[STATES];
int j;
strcpy(statename[0], "0");
for (i = 0; i < n; i++)
{
for (j = 0; j < n_sym; j++)
{
get_next_state(nextstate, statename[i], nfa, j);
dfa[i][j] = state_index(nextstate, statename, &n);
}
}
return n;
}
void get_DFA_finals(char *dfinal, char *nfinal, char state[][STATES], int dfa_s)
{
int i, j, k=0, n=strlen(nfinal);
for (i = 0; i < dfa_s; i++)
{
for (j = 0; j < n; j++)
{
if (strchr(statename[i], nfinal[j]))
{
dfinal[k++] = 'A'+i;
break;
}
}
}
dfinal[k] = '\0';
}
/*void syntaxcheck(char word[],int dfa[][SYMBOLS],char *dfinal)
{
int i, j, cur_state;
printf("\nWord: %s",word);
for(i = 0; i < strlen(word); i++)
{
for(j = 0; j < STATES && dfinal[j] != '\0'; j++)
{
if(word[i] == 'a')
}
}
}*/
int main()
{
init_NFA_table();
DFA_states = nfa_to_dfa(NFAtab, NFA_states, N_symbols, DFAtab);
get_DFA_finals(DFA_finals,NFA_finals,statename,DFA_states);
put_dfa_table(DFAtab, DFA_states, N_symbols,DFA_finals);
//syntaxcheck("abaca",DFAtab,DFA_finals);
return 0;
}
|
|
