- 主题:各位，有办法判断两个正则表达式是否具有包含关系么？
有明确定义的办法 基本上是 nfa->dfa 然后从两个 dfa 生成一个补集的交集 然后判断这个交集是否存在任何合法输入： a = dfa(e1) ^ ~(dfa(e2)).
写作业的话难度不算太大，两三个人小组做一个月应该出来了。但是要做一个工业上实用的实现，难度比较大，因为这明显是一个 pspace 复杂度的问题，因为 nfa->dfa 的缘故。如果是想挑战自己一下，可以试试看。
这方面的知识其实不难，不过因为是非常老的话题，论文和书都比较干涩，而且有一些folklore的知识点，要捡起来还是得花不少功夫。
--
FROM 188.67.171.*
顺便说一句
Brzozowski的minimize dfa的算法非常漂亮
事实上可以跳过nfa 直接生成dfa 并且是最小dfa
不仅这个结果漂亮 这个算法本身也非常cute
在cs理论里是一个罕见的cute的例子 绝大多数cs用的算法都很dull
Canonical regular expressions and minimal state graphs for definite events.
这篇论文
【 在 chunhui 的大作中提到: 】
: 我是想在实际的项目中用。但是看来可能性不大。就算我按这方法做出来也未必实用。
--
FROM 85.76.108.*
我记得（很多年前了）有人写过这个算法的cpp实现
我也写过一次 只是没开源
这个算法还有一个优点是很容易写complement 也就是~ 的逻辑 因为你可以直接在RE上做 negation。而这正是你需要的特性
当然所有的re的实现 难点都是过早的.* 一下子就把空间扩大到指数级了 不过这是re的内在属性 没辙
cs的理论核心是复杂度 复杂度的研究工具是language 和Turing machine，复杂度研究的主线就是发现各种lang之间的同构
所以 趁这个机会看看研究lang和automaton论文没什么不行的 古典cs论文的好处是门槛比较低 不需要准备就可以直接上手
【 在 chunhui 的大作中提到: 】
: 先收藏了。感觉得想其他办法解决了，难道为了这个办法，我还要研究一下学术问题？有点不可行。
--
FROM 85.76.108.*