- 主题:各位,有办法判断两个正则表达式是否具有包含关系么?
我想找一个可以直接拿来用的库。否则就得自己实现。如果很难或者实现出来判断不准,难到还要我自己去按照论文实现。这就有点不现实了。我现在还不确定这个判断是否可以作到,如果作到了是否适应面不多,比如稍微复杂点的就判断不准之类。。。
【 在 heideggerr 的大作中提到: 】
: GPT在这里做的就是一个搜索引擎而已。
--
FROM 117.133.52.*
有什么样的使用场景吗?
每一个正则表达式的可被匹配的字符串的集合,从某种角度来说应该是不可确定的,那么,两个不可确定的集合,怎么还能判断是否有交集呢?并且,还要把这个交集再次重新解释为一个用正则表达的子集?这应该就属于gpt ai的范畴了吧?
【 在 chunhui 的大作中提到: 】
: 比如查找字符串 abcdef 是包含 abc def 的。这是纯字符串。那么两个正则表达式有办法判断包含关系么?或者说是否可行?
--
FROM 223.198.169.*
我举的例子中就是包含关系。只不过是纯字符串不是正则而已。
你写一个宽泛的正则表达式肯定会包含一个严格的。。。
【 在 njer 的大作中提到: 】
: 有什么样的使用场景吗?
: 每一个正则表达式的可被匹配的字符串的集合,从某种角度来说应该是不可确定的,那么,两个不可确定的集合,怎么还能判断是否有交集呢?并且,还要把这个交集再次重新解释为一个用正则表达的子集?这应该就属于gpt ai的范畴了吧?
--
FROM 114.254.2.*
找本形式语言和自动机方面的经典教材看一下吧。我印象中判断两个自动机识别的语言是否等价似乎已经是相当难度/不可判定的问题了。具体记不清了,也许对正则语言可能有。这个涉及到非常基本的问题,建议还是先搞清楚理论再试,否则可能就是造永动机之类浪费时间了。
【 在 chunhui 的大作中提到: 】
: 我想找一个可以直接拿来用的库。否则就得自己实现。如果很难或者实现出来判断不准,难到还要我自己去按照论文实现。这就有点不现实了。我现在还不确定这个判断是否可以作到,如果作到了是否适应面不多,比如稍微复杂点的就判断不准之类。。。
:
--
FROM 218.16.203.*
有明确定义的办法 基本上是 nfa->dfa 然后从两个 dfa 生成一个补集的交集 然后判断这个交集是否存在任何合法输入: a = dfa(e1) ^ ~(dfa(e2)).
写作业的话难度不算太大,两三个人小组做一个月应该出来了。但是要做一个工业上实用的实现,难度比较大,因为这明显是一个 pspace 复杂度的问题,因为 nfa->dfa 的缘故。如果是想挑战自己一下,可以试试看。
这方面的知识其实不难,不过因为是非常老的话题,论文和书都比较干涩,而且有一些folklore的知识点,要捡起来还是得花不少功夫。
--
FROM 188.67.171.*
没研究过。估计有可能是的。
正则表达式 本质是一个 无穷的字符串集合, 两个无穷的字符串集合的笛卡尔乘积是无穷的。单纯用枚举的方法是半可判定的。
【 在 chunhui 的大作中提到: 】
: 这东西学完了细节都忘了。我搜了一下都说这个很难。gpt也说挺复杂。如果按你说的可以的话,那我就放心了,回去复习一下。
: 不过gpt说这是一个不可判定问题。。。真的假的。
--
FROM 154.17.19.*
是的,我就是担心这个问题可能根本就不是一个可以实现的问题,再或者只是学术上有方法但无法在实际工程中使用。
【 在 quene 的大作中提到: 】
: 找本形式语言和自动机方面的经典教材看一下吧。我印象中判断两个自动机识别的语言是否等价似乎已经是相当难度/不可判定的问题了。具体记不清了,也许对正则语言可能有。这个涉及到非常基本的问题,建议还是先搞清楚理论再试,否则可能就是造永动机之类浪费时间了。
--
FROM 125.34.113.*
我是想在实际的项目中用。但是看来可能性不大。就算我按这方法做出来也未必实用。
【 在 philbloo 的大作中提到: 】
: 有明确定义的办法 基本上是 nfa->dfa 然后从两个 dfa 生成一个补集的交集 然后判断这个交集是否存在任何合法输入: a = dfa(e1) ^ ~(dfa(e2)).
: 写作业的话难度不算太大,两三个人小组做一个月应该出来了。但是要做一个工业上实用的实现,难度比较大,因为这明显是一个 pspace 复杂度的问题,因为 nfa->dfa 的缘故。如果是想挑战自己一下,可以试试看。
: 这方面的知识其实不难,不过因为是非常老的话题,论文和书都比较干涩,而且有一些folklore的知识点,要捡起来还是得花不少功夫。
: ...................
--
FROM 125.34.113.*
我是遇到了一个问题想到了一个办法。但是依赖这个判断。。。所以这个办法看来不可行了。
【 在 a0123456789q 的大作中提到: 】
: 没研究过。估计有可能是的。
: 正则表达式 本质是一个 无穷的字符串集合, 两个无穷的字符串集合的笛卡尔乘积是无穷的。单纯用枚举的方法是半可判定的。
--
FROM 125.34.113.*
顺便说一句
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.*