实验一、简单的词法设计——DFA模拟程序

利用有穷确定自动机M=(
K有穷状态集,
Σ输入字母表,
f转换函数，从状态s出发，沿着标记为a的边所能到达的状态
S,开始状态，S属于K
Z，接收状态，Z是K的子集
）行为模拟程序算法，来对于任意给定的串，若属于该语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”
K当前状态:=S开始状态；
C当前的输入符号:=getchar返回输入串的下一个符号;
while c<>eof do
{K当前状态:=f(K,c)从状态K出发，沿着标记为c的边所能到达的状态;
c当前的输入符号:=getchar返回输入串的下一个符号; };
if K is in Z接收状态 then return (‘yes’)
else return (‘no’)

 #include<stdio.h>   // 转换表大小   #define M 255  #define N 255    // 状态集个数   #define KNUM 4  // 字母表个数  #define LNUM 2  //接受集个数  #define ZNUM 1     // 状态集  char K[KNUM] = {'S', 'U', 'V', 'Q'};  // 字符集  char C[LNUM] = {'a', 'b'};  // 开始状态  char S = 'S';  // 接收状态  char Z[1] = {'Q'};  // 状态转换表  char table[M][N];  // 输入字符串   char str[255];  //输入指针   char *p;    // DFA算法  void DFA(char *p);   // 返回输入串x的下一个符号  char nextChar();  // f(K,c)转换函数   char f(char K, char c);    int main()  {  	printf(请输入待检验的字符串:);  	while(scanf(%s,str) != EOF) 	{ 		p = str; 		DFA(str); 		printf(请输入待检验的字符串:); 	} 	return 0;  }    void DFA(char *p)  {  	  	char K = S;  	char c = nextChar();  	int i = 0;  	while(c != '\0')  	{  		K = f(K,c);  		c = nextChar(); 	} 	// 判断K是否在接收状态Z中  	for(int i = 0; i < ZNUM; i++) 	{ 		if(K == Z[i]) 		{ 			printf(yes\n); 			return; 		} 	} 	printf(no\n);  }    char nextChar()  {  	return *p++;  }    char f(char K, char c)  {  	for(int i=0;i<KNUM;i++) 		for(int j=0;j<LNUM;j++) 			table[i][j]=-1; 	table['S']['a'] = 'U'; 	table['S']['b'] = 'V'; 	table['U']['a'] = 'Q'; 	table['U']['b'] = 'V'; 	table['V']['a'] = 'U'; 	table['V']['b'] = 'Q'; 	table['Q']['a'] = 'Q'; 	table['Q']['b'] = 'Q'; 	 	return table[K][c];  }