整体最小的DFA

2018-06-26 17:55:29

在为正则表达式创建DFA时，我注意到，即使分析，整个单词也会增加状态的数量，但它们看起来与具有较少状态的正则表达式类似。

例如，对我来说，（a | b）+看起来与（hello | world）+相同

如果我有一个匹配的字符串，很容易找到/用“b”代替“hello”，反之用a代替“world”。所以我的问题是，为什么不把“你好”和“世界”算作单一国家呢？

因为使用更简单的状态定义来实现DFA是非常简单的，代价是拥有更多的状态。您提出的建议对描述您希望DFA如何工作很好，并且与传统的DFA有着直接的对应关系。但它不允许你再说什么。

它与使用NFA类似：它们更容易设计和（可能）思考，但没有更多的权力，并且有一个明确的算法将它们转换成DFA（再次，以引入状态）。

可以将使用单字符转换的DFA作为正则表达式的“机器语言”（与正则表达式不同，以获得迂腐）。

链接地址: http://www.djcxy.com/p/74803.html