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

本文主要是介绍实验一、简单的词法设计——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];
 }
 

这篇关于实验一、简单的词法设计——DFA模拟程序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！