计算如果两个无穷的正则表达式的解集不相交 [英] Calculate if two infinite regex solution sets don't intersect

问题描述

在计算，如果任意两个正规的前pressions有任何重叠的解决方案（假定这是可能的）。

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

例如两个正前pressions可以证明没有交集用蛮力，因为这两个方案组合是可计算的，因为它是有限的。

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)*$} = {}
.....

在另一个类似的问题一个<一个href="http://stackoverflow.com/questions/489095/how-to-determine-if-a-regex-is-orthogonal-to-another-regex/489226#489226">answer是计算交点正则表达式。这是可能做到？如果是的话如何将一个写一个算法做这样的事？

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?

<打击>我觉得这个问题可能是href="http://en.wikipedia.org/wiki/Halting_problem" rel="nofollow">停机问题的

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

编辑：

我用接受的解决方案创建的DFA的例子问题。这也很容易就看你怎么可以使用状态的图形中的BFS或DFS为 M_3 来确定是否从最终状态 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为第二语言。 提示：克林定理和发电机组机械制造的
3. 构造一个DFA M3为M1 M2相交。 提示：笛卡尔乘积机械制造的
4. 确定L（M3）是否为空。 提示：如果M3有n个国家和M3不接受长度不大于N的任何条件，则L（M3）是空的。为什么的
？

1. Construct a DFA M1 for the first language.
2. Construct a DFA M2 for the second language. Hint: Kleene's Theorem and Power Set machine construction
3. Construct a DFA M3 for M1 intersect M2. Hint: Cartesian Product Machine construction
4. Determine whether L(M3) is empty. Hint: If M3 has n states, and M3 doesn't accept any strings of length no greater than n, then L(M3) is empty... why?

每个那些事情可以做算法和/或检查。此外，自然，一旦你有一个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。让M 1 =（E，Q0，Q1，A1为f1）和M2 =（E，Q0'，Q 2，A 2，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）|的X A1和y在A2}
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屋！