NFA를 DFA로 바꾸기

목차

1. NFA를 DFA로 바꾸기

2. R(E)를 NFA로 바꾸기

본문내용

bol들에 대해 nextstate 계산을 한다.
그리고 nextstate가 스트링이므로 statename의 index를 DFA에 넣는다. */
⑶ 실행창
2. R(E)를 NFA로 바꾸기
⑴ 상태 전이표
0
1
q0
q1
q0
q1
q2
q1
q2
q3
q3
q3
q3
q3
⑵ C 프로그래밍 소스
// R(E) to NFA
#include
#include
#define SIZE 50
#define TERM 2
#define GRAM 4
#define SYMB 2
#define GRTE GRAM*TERM
struct nfa
{
char state[SYMB+2];
char symb[SYMB];
char start;
char final;
char func[GRTE][3];
} nfa;
struct regular_grammer
{
char symb[SYMB];
char term[TERM];
char start;
char func[GRAM][3];
} rg;
void INPT_RG(void);
void INPT_RG(void)
{
rg.symb[0]='A';
rg.symb[1]='B';
rg.term[0]='0';
rg.term[1]='1';
rg.start='A';
rg.func[0][0]='A';
rg.func[0][1]='0';
rg.func[0][2]='B';
rg.func[1][0]='A';
rg.func[1][1]='1';
rg.func[1][2]='A';
rg.func[2][0]='B';
rg.func[2][1]='0';
rg.func[2][2]=' ';
rg.func[3][0]='B';
rg.func[3][1]='1';
rg.func[3][2]='B';
}
void main()
{
char input[SIZE]={' '};
char str=' ';
int i,j;
INPT_RG();
for(i=0;i {
nfa.state[i]=rg.symb[i];
nfa.symb[i]=rg.term[i];
}
nfa.state[SYMB]='C';
nfa.state[SYMB+1]='D';
nfa.final='C';
nfa.start=rg.start;
for(i=0;i {
for(j=0;j {
nfa.func[i+j][1]=nfa.symb[j];
}
}
for (i=0;i {
if(rg.func[i][2]==' ')
nfa.func[i][2]=nfa.final;
for(j=0;j<3;j++)
{
if(rg.func[i][j]==rg.start)
nfa.func[i][j]=nfa.start;
if(rg.func[i][j]==rg.symb[1])
nfa.func[i][j]=nfa.state[1];
}
}
for (i=0;i<2;i++)
{
nfa.func[GRAM+i][0]='C';
nfa.func[GRAM+i][2]='D';
}
for (i=2;i<4;i++)
{
nfa.func[GRAM+i][0]='D';
nfa.func[GRAM+i][2]='D';
}
printf("State Transition Table\n");
printf("state");
for(i=0;i {
printf("\t%c",nfa.symb[i]);
}
printf("\n------------------------");
for(i=0;i {
printf("\n %c |", nfa.func[i][0]);
for(j=0;j {
printf("\t%c", nfa.func[i+j][2]);
}
}
printf("\n");
}
⑶ 실행창

키워드

nfa,   dfa,   변환,   오토마타,   프로그래밍,   소스