下面的算法需要对Regex作变换，从而改变括号的标号，因此，采用新的写法。Regex中的捕获组用一个足够大的和字母表不相交的变量集Γ中的变量x表示，变量的捕获写作(e)%x；变量的引用直接写作x。

没有%x的括号只指示优先级。

如：\((a^{\ast}) (a|b) \backslash 1 \Rightarrow (a^{\ast}) \%x (a|b) x\)

1概述

问题 1. 给定vsf regex u, v 判定\(L (u) \cap L (v)\)是否为空

关于这个问题，此前[1]的做法是把问题转换到SpLog，而[2]中对确定型的vsf的一种类似判定是通过TMFA完成的。下面给出的是一种通过直接在regex层面变换，最后转换为Word Equation求解的判定方法。

首先，观察到regex的几个性质：

引理 1. 如果一个regex中所有变量对应的子表达式都不含Star，那么此regex实际上定义了一个正规语言。

换言之，regex和传统正规表达式的区别其实不来自于逆引用本身，而是逆引用和Star同时作用的结果。

例 1. \(L ((a|b) \%x c x) = L (\operatorname{aca}|\operatorname{bca})\)

引理 2. 对一个regex，如果在其AST中，某个变量x的捕获和引用分属某alternation节点的两个子树，那么删除此引用不影响此regex的语言。

换言之，我们可以安全地假设变量的捕获和引用在每一个alternation的同一个析取支内。

引理 3. 删除没有引用的捕获和没有捕获的引用不改变语言

一个例子：

例 2. \(L ((a^{\ast}) \%x|x b) = L ((a^{\ast}) \%x| b) = L (a^{\ast} |b)\)

下面，非形式化地简述判定算法的基本思路：

1. 使用一种迭代过程，将regex u和v都变换为一种等价的范式。这种范式类似于析取范式，要求regex由一系列alternation组成。即\(a = b_1 |b_2 | \ldots |b_m\)，其中，每一个b中，alternation只在Star中出现。

2. 更进一步，要求将每一个析取支b化为\(e_1 e_2 \ldots e_n\)的形式。其中，每一个e如果是变量的捕获(e)%x，则e必定是一个Kleene Star。

3. 分别从u和v的范式中不确定地选择一个析取支\(b_u\)和\(b_v\)。

4. 通过一个简单的过程，将\(b_u\)和\(b_v\)分别转化为带正则约束的word equation。已知此理论是可判定的，因此使用一种已有的判定算法解之，即可判定VSF相交的非空性。

首先给出一个例子说明迭代过程是如何工作的：

例 3. 对regex \(( a^{\ast} (c|d) b^{\ast} | b^{\ast} (c|d)^{\ast} a^{\ast}) \%x (x|p)\)，首先展开所有不在Star和捕获中出现的alternation：

现在，alternation只出现在Star和x的捕获中，对变量x的捕获，通过变量重命名展开其顶层的alternation：

现在已经得到了析取形式的等价regex，但是还不满足捕获的表达式一定是Star。因此进一步展开concatenation：

这样就得到了原式的一个等价形式，由一系列alternation连接的表达式组成，每一个表达式中都只存在对Star的捕获。

下面是一个归约到word equation的例子：

例 4. 设变换后的范式有一个析取支是\(c^{\ast} ((a^{\ast} |b)^{\ast}) \%x d x\)。首先，找出所有捕获，记下对应的变量（这里是x），然后找出所有没有被捕获的Star，给每一个这样的Star分配一个变量名。比如，假设这里给\(c^{\ast}\)分配y。设w是一个特殊的表示输入串的变量。这样，此析取支被转换为：

2形式化

定义 1. vsf regex语法：

\(\alpha := \alpha_1 \alpha_2 | \alpha_1 + \alpha_2 | \beta^{\ast} | (\alpha) \%x|x|c| \varepsilon\)

\(\beta := \beta_1 \beta_2 | \beta_1 + \beta_2 | \beta^{\ast} |c| \varepsilon\)

对于一个输入的vsf regex，首先删除其所有语法上冗余的变量（即「左侧」没有捕获的变量），以及满足引理2或3条件的变量和捕获。将简化后的regex输入后续例程。

定义 2. 称vsf regex a是伪析取范式，如果a为\(a_1 + \cdots + a_n\)的形式，且每个\(a_i\)中，alternation只在捕获或star中出现。

定义 3. 定义作用于vsf regex u的算子T如下：

• 如果\(u = e_1 + e_2\)，则\(T (u) = T (e_1) + T (e_2)\)

• 如果\(u = e_1 e_2\)

  假设\(T (e_1) = \Sigma^n_1 s_i, T (e_2) = \Sigma^m_1 t_j\)。定义Q为u中所有同时出现引用和捕获的变量集，\(\Gamma_i\)为\(s_i\)中被捕获的变量集，\(S_{i j} = s_i \circ t_j [\varepsilon / Q - \Gamma_i]\)，其中\([x / y]\)表示y替换为x。

  则有\(T (u) = \Sigma_i \Sigma_j S_{i j}\)

• 否则\(T (u) = u\)

引理 4. 如果u是被简化后的vsf regex，v=T(u)一定满足如下性质：

1. v是伪析取范式

2. 对任意变量x，每一个析取支内最多出现一次x的捕获

3. 对任意变量x，如果x的捕获在u中出现，且v的一个析取支内出现x的引用，则必定也出现x的捕获，且在引用之前出现。

证明. 对u应用结构归纳法。

• 基础情况比较简单，容易验证。

• 当\(u = e_1 + e_2\)，由归纳条件可知\(T (e_1) 、T (e_2)\)都是伪析取范式，所以T(u)也是。

  考虑条件2，对任意变量x，由归纳条件知\(T (e_1) 、T (e_2)\)内最多出现1次x的捕获，由于T(u)的析取支就是二者的析取支的并，所以T(u)也满足条件2。

  考虑条件3，如果x的捕获在u中出现，分两种情况：如果捕获是在\(e_1\)中出现，则若v的一个析取支内有x，根据简化规则，此析取支必然来自\(\)\(T (e_1)\)，则由归纳条件知3成立；如果捕获是在\(e_2\)中出现，则若v的一个析取支内有x，根据简化规则，此析取支必然来自\(T (e_2)\)，同样地，由归纳条件知3成立。

• 当\(u = e_1 e_2\),由归纳条件知\(T (e_1) 、T (e_2)\)中都不含alternation的自由出现.因为T(u)是\(T (e_1) 、T (e_2)\)析取支的组合，所以也必然不含alternation的自由出现。

  考虑条件2，由条件2的归纳条件知，对任意变量x，每一个s和t中都最多有一个x的捕获。由于输入的u中同一个变量只有一个捕获，所以s和t不可能同时有捕获，所以v的析取支中也最多有一个捕获。

  考虑条件3，假设x的捕获在u中出现。

  如果出现在\(e_1\)中，且v中一个析取支有x的引用，那么存在i，j使得\(S_{\operatorname{ij}}\)中有x的引用。如果此引用是在\(s_i\)中，则有归纳条件可知3成立，如果此引用是在\(t_j [\varepsilon / Q - \Gamma_i]\)中，那么x必然在\(\Gamma_i\)中，从而x必然在s中被捕获，因此3成立。

  如果出现在\(e_2\)中，且v中一个析取支有x的引用，那么同样存在i，j使得\(S_{\operatorname{ij}}\)中有x的引用。此时根据归纳条件即可知3成立。

得到伪析取范式u后，u中可能含有同一个变量的多次捕获，但这些捕获一定在不同的析取支内。因此，之后先要对所有变量进行一次换名，保持捕获的唯一性。具体做法略。

定义 4. 称u是析取范式，如果u是伪析取范式，且每个析取支都形如\(e_1 e_2 \ldots e_n\)，对其中每个e，如果\(e = (e') \%x\)，则\(e'\)一定是Kleene Star。

引理 5. 经过上述的几个步骤，vsf regex被变换为析取范式，且变换后依然是vsf的。

证明. 变换后是析取范式从算法的结束条件即可知；而上述的几步都不改变Star内部的结构，因此vsf性质保持。关键在于算法一定终止：

对每个析取支，每次迭代都将其中的一个捕获的表达式简化一层，同时捕获数量最多加一。因此，算法的迭代次数只取决于所有捕获的表达式的语法树中非Star节点的最大层数。（复杂度待分析）

总判定算法：

参考文献