实现NFA到DFA的转化（C语言）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了实现NFA到DFA的转化（C语言），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1916字，纯文字阅读大概需要3分钟。

内容图文

简单记录一下，自动机课上的一个实验，用C语言实现NFA到DFA的转化，使用的是子集构造法。
子集构造法相信大家都会，直接甩代码。
先是把NFA和DAF的转移表存储在数据结构里，这里用了二维字符数组，先是定义了一个struct onechar,用来当作转移表的一格，这让我这个程序简单了不少，但是局限性是真的多。所以程序的状态只能使用当个字符表示，且设置的最大状态集数量是20。

typedef struct onechar
{
	char block[MAX_NUM];//用于存储一个20个字符的字符数组
}onechar;

后面的函数调用其实有点混乱，功能分配很奇怪。
子集构造法被我写成了字符匹配算法，以下是主要函数。解释我直接写在注释里好了。

void switch_NFAtoDFA(onechar** NFA_chart, onechar** DFA_chart, char* NFA_status, onechar* DFA_status)
{
	int i = 0, j = 0, n = 0, flag = 1;//NFA与DFA转移表的第一行是相同的，num是DFA的状态集数量
	DFA_status[0].block[0] = NFA_status[0];
	DFA_status[0].block[1] = '\0';
	while (n != num)
	{
		switch1(NFA_chart, DFA_chart, NFA_status, DFA_status[n].block, n);/*这个函数把DFA的新得到的状态去匹配NFA的转移表，从而得到DFA的一行*/
		//以下的几个for循环是把新得到的一行中的状态与DFA的状态集对比，看是否有新状态
		for (i = 0; i < chars_num; i++)
		{
			for (j = 0; j < num; j++)//n,表示已经求完第n个状态的转移函数
			{
				if (strcmp(DFA_chart[n][i].block, DFA_status[j].block) == 0)//不匹配说明是新状态(所有不匹配才可以)
				{
					flag = 0;//已存在的状态
				}
			}
			if (flag == 1 && DFA_chart[n][i].block[0] != '#')//新状态当然要放在DFA状态集里了
			{
				strcpy(DFA_status[num].block, DFA_chart[n][i].block);
				num++;
			}
			flag = 1;
		}
		n++;
	｝
}

这里是我最后发现的bug，程序会把状态一样但是字符顺序不一样的状态写成两个状态，如pqr和prq，后来发现只要排下序就好了。

for (i = 0; i < j - 1; i++)//冒泡排序，防止出现pqr,rpq是不同状态
	{
		for (k = 0; k < j - 1; k++)
		{
			if (s[k] > s[k + 1])
			{
				char tmp = s[k];
				s[k] = s[k + 1];
				s[k + 1] = tmp;
			}
		}
	}

就简单写到这里把，本人很懒，但是直接甩代码实在不太好，就稍微写几个字，刚开始写博客记录，思维有些混乱很抱歉。附上完整代码，大家一起互相学习。
NFA转DFA完整代码在gitee上https://gitee.com/zqiusen/c_collect/tree/master/NFA-DFA

内容总结

以上是互联网集市为您收集整理的实现NFA到DFA的转化（C语言）全部内容，希望文章能够帮你解决实现NFA到DFA的转化（C语言）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端