你如何规范有限状态机？

Question

这不是一个家庭作业问题.我正在看这个系列讲座而且很好奇.

Answer 1

由于所有非确定性FSM都具有相应的确定性FSM,因此对1和2的答案应该相同.

如果您想了解更多信息,请获取Michael Sipser撰写的"计算理论导论",这是一本非常好的书,可以学习这些东西.Sipser知道他谈论什么以及如何很好地沟通.

Answer 2

一些非正式的答案给你的想法,详细的证据读了一本关于Automata的好书,例如这个或其他答案中提到的那些.而且我很确定您可以找到回答所有问题的在线资料.

该过程是消除重复状态(或合并等效状态).您知道状态和转换是生成字符串的关键.基本上,重复的状态无助于使语言生成更大或更少.该算法从始终具有生成lamda(空字符串)的能力的最终状态开始,并递归地更新指示状态的生成能力的表,并最终合并那些没有区别的状态.

NFA的规范化DFA使用不同的NFA状态集合作为DFA的状态,例如,{state0} - (1) - > {state1,state2}来删除非确定性部分,没有办法避免国家爆炸,DFA必须这样做才能代表语言.

我记得最好的一个是O(NLogN)在西安大略大学教授的一些论文中重复使用信息,并怀疑是否存在更好的信息.我相信经典的是O(N ^ 2).

是.获取最小的一个,通过访问字符串来编码状态(一个字符串可以从开始状态到达状态,这几乎就是状态的真实"名称"),并验证转换映射.可能有更好的方法,但bigO上没有太大的区别.

Answer 3

如果给你一些确定性的FSM,那么你可以在O(n ²)中使用一个非常简单的算法找到一个等价的,最小的FSM ; Hopcroft的算法在O(n log n)中完成.在这里你可以找到两者的描述.您可以通过最小化它们并检查它们是否相同来检查A和B是否相同.
如果给你一些不确定的FSM,那么找到一个等价的,最小的是PSPACE-complete.换句话说,没有好的算法是已知的,并且推测它不存在.检查两个非确定性自动机的等价性也是PSPACE完成的.所以,除非有一个非常不可能的突破,你应该将自动机转换为确定性的(这需要很长时间),然后执行检查.
您可以将非确定性FSM转换为具有指数状态的确定性FSM.这是不可避免的.练习(不难!):使用具有n个状态的非确定性FSM识别由末尾的第n个字母为"a"的单词组成的语言,并且使用小于2 的确定性FSM 无法识别ⁿ州.在一般情况下,指数界限不能被破坏.