计算两个无限正则表达式解决方案集是否不相交 [英] Calculate if two infinite regex solution sets don't intersect

问题描述

在计算两个任意正则表达式是否有任何重叠的解决方案(假设有可能).

In calculate if two arbitrary regular expressions have any overlapping solutions (assuming it's possible).

例如，这两个正则表达式可以通过蛮力证明没有交集，因为这两个解集是可计算的，因为它是有限的.

For example these two regular expressions can be shown to have no intersections by brute force because the two solution sets are calculable because it's finite.

^1(11){0,1000}$ ∩     ^(11){0,1000}$        = {}
{1,111, ..., ..111} ∩ {11,1111, ..., ...11} = {}
{}                                          = {}

但是将 {0,1000} 替换为 * 消除了暴力解决方案的可能性，因此必须创建更智能的算法.

But replacing the {0,1000} by * remove the possibility for a brute force solution, so a smarter algorithm must be created.

^1(11)*$ ∩ ^(11)*$ = {}
{1,^1(11)*$} ∩ {^(11)*$} = {}
{1,^1(11)*$} ∩ {11,^11(11)*$} = {}
{1,111,^111(11)*$} ∩ {11,^(11)*$} = {}
.....

在另一个 类似问题 一个 答案是计算交集正则表达式.那有可能吗?如果是这样，如何编写算法来做这样的事情?

In another similar question one answer was to calculate the intersection regex. Is that possible to do? If so how would one write an algorithm to do such a thing?

我认为这个问题可能是 停止问题的领域.罢工>

I think this problem might be domain of the halting problem.

我已使用公认的解决方案为示例问题创建 DFA.很容易看出如何在 M_3 的状态图上使用 BFS 或 DFS 来确定来自 M_3 的最终状态是否可达.

I've used the accepted solution to create the DFAs for the example problem. It's fairly easy to see how you can use a BFS or DFS on the graph of states for M_3 to determine if a final state from M_3 is reachable.

推荐答案

不在停机问题的范畴；判断正则语言的交集是否为空可以解决如下:

It is not in the domain of the halting problem; deciding whether the intersection of regular languages is empty or not can be solved as follows:

1. 为第一语言构建 DFA M1.
2. 为第二种语言构建一个 DFA M2.提示:Kleene 定理和幂集机器构造
3. 为 M1 与 M2 相交构造一个 DFA M3.提示:笛卡尔积机器构造
4. 判断L(M3)是否为空.提示:如果 M3 有 n 个状态，并且 M3 不接受任何长度不大于 n 的字符串，那么 L(M3) 为空……为什么?

这些事情中的每一件事都可以通过算法完成和/或检查.此外，自然地，一旦 DFA 识别出您的语言的交集，您就可以构建一个正则表达式来匹配该语言.如果你从一个正则表达式开始，你可以制作一个 DFA.这绝对是可计算的.

Each of those things can be algorithmically done and/or checked. Also, naturally, once you have a DFA recognizing the intersection of your languages, you can construct a regex to match the language. And if you start out with a regex, you can make a DFA. This is definitely computable.

因此，要构建笛卡尔积机器，您需要两个 DFA.令 M1 = (E, q0, Q1, A1, f1) 和 M2 = (E, q0', Q2, A2, f2).在这两种情况下，E 是输入字母表，q0 是起始状态，Q 是所有状态的集合，A 是接受状态的集合，f 是转移函数.构造 M3 在哪里...

So to build a Cartesian Product Machine, you need two DFAs. Let M1 = (E, q0, Q1, A1, f1) and M2 = (E, q0', Q2, A2, f2). In both cases, E is the input alphabet, q0 is the start state, Q is the set of all states, A is the set of accepting states, and f is the transition function. Construct M3 where...

1. E3 = E
2. Q3 = Q1 x Q2(有序对)
3. q0'' = (q0, q0')
4. A3 = {(x, y) |A1 中的 x 和 A2 中的 y}
5. f3(s, (x, y)) = (f1(s, x), f2(s, y))

如果我没有犯任何错误，L(M3) = L(M1) 与 L(M2) 相交.整洁吧?

Provided I didn't make any mistakes, L(M3) = L(M1) intersect L(M2). Neat, huh?

这篇关于计算两个无限正则表达式解决方案集是否不相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！