正则表达式匹配两个正则表达式之间的交集？

发布时间：2020-12-14 06:24:38 所属栏目：百科来源：网络整理

导读：给定几个正则表达式,我们可以编写一个等于它们交集的正则表达式吗？例如,给定两个正则表达式c [a-z] [a-z]和[a-z] [aeiou] t,它们的交集包含cat和cut以及可能更多.我们怎样才能为它们的交集写一个正则表达式？谢谢. 先行示例易于使用,但从技术上讲不再是常

给定几个正则表达式,我们可以编写一个等于它们交集的正则表达式吗？

例如,给定两个正则表达式c [a-z] [a-z]和[a-z] [aeiou] t,它们的交集包含cat和cut以及可能更多.我们怎样才能为它们的交集写一个正则表达式？

谢谢.

先行示例易于使用,但从技术上讲不再是常规语言.但是,可以采用两种常规语言的交集,并且这种补语是常规的.

首先请注意,正则表达式可以转换为NFA;它们都是表达常规语言的方式.

其次,根据德莫根定律,

因此,这些是计算两个RegEx的交集的步骤：

>将两个RegEx转换为NFA.
>计算两个NFA的补充.
>计算两个补语的并集.
>计算该联盟的补充.
>将生成的NFA转换为RegEx.

一些来源：

>联盟和RegEx到NFA：http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_06.pdf
> NFA至RegEx：http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf
> NFA的补充：https://cs.stackexchange.com/questions/13282/complement-of-non-deterministic-finite-automata

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!