说出来不怕大家笑话,用C写的,连写带debug花了整整两天,第三天在床上睡了一整天,醒的时候还是觉得很困很困。事实证明,人不能轻易写代码,不然会困死。

(青鲭姐姐看过我的代码,沉默好久。“为什么不用cpp呢?”……因为,还没有学完……废物是这样的,对吧)


下面浅浅记录一下思路,不是很具体:

  1. 一个结构体放转移函数,我分成front-原状态,ch-接收的字符,next-接受字符后能到达的状态三部分,第二个结构体放状态,并且标注是否为开始状态或者结束状态。
  2. 读入NFA的时候要注意getchar(),否则对应位置会变成回车或者别的什么奇怪的东西,然后你就再也改不好这份代码了。
  3. 偷懒所以规定只能接受0和1。
  4. 转移函数未必所有状态都对应到,所以加了一个判断,# -1 #表示停止输入,NFA创建完毕。
  5. 转换到DFA比较简单粗暴,另建了一个数组把某状态next里的东西全放进去,然后排序,删掉相同的状态再丢给DFA就行。
  6. 对应状态是否是开始或者结束直接进行一个遍历(提前记录好NFA的开始和结束状态)。
  7. 最后输出的时候可以考虑next为空就不输出,更符合表达习惯。

太久不写的结果就是debug的时候发现自己有一堆傻逼错误,包括但不限于strcat两个参数写反了printf("%c")偷懒复制粘贴结果忘记把0改成i导致数组反复赋值……以及死都搞不明白的getchar()到底该放在哪里。

起初还往结构体里扔了几个指针,随随便便就飞了,我当时想掐死用指针的自己 。后来发现有没有指针好像并不是很影响,干脆把指针删了。只要不用就不会有烦恼。