1Regex语言性质

此处某Regex的语言是指能被其接受的字符串的集合，即不将接受时Regex中捕获组的值考虑为语言的一部分。因此暂时不用关心贪婪匹配的问题。Regex的语言有如下性质：

引理 1. (泵引理) 对任意Regex a, 存在常数N, 使得任意被a接受的且长度大于N的字符串w都满足：

1. 存在m>0使得\(w = x_0 y x_1 y \ldots x_m\)

2. \(| x_0 y | \leqslant N\)

3. \(| y | > 1\)

4. 对任意正数j，\(x_0 y^j x_1 y^j \ldots x_m\)也被a接受

引理 2. Regex的语言对交、补、逆同态映射不封闭，对并、同态映射封闭

定理 3. Regex的语言是上下文有关语言的真子集

定理 4. Regex的语言和上下文无关语言不可比

以上证明见[1]。

给定字符串w判断是否可被Regex a接受，即Regex语言的成员问题是可判定的。但是Aho[3]证明了：

定理 5. Regex的判定问题是NPC的

此外还有：

定理 6. 对于Regex a和b，\(L (a) \cap L (b) = \emptyset\)是不可判定的

定理 7. 如果限制在Regex中，Kleene stars不含变量绑定或引用，则Regex语言的交是否为空是可判定的。

2RefWord语言模型

RefWord是关于Regex的形式语言模型。

定义 8. (refword) 设\(\Sigma\)是某字母表，\(\Sigma\)上的refword是字母表\(\Sigma \cup \Gamma\)上的字符串，其中\(\Gamma = \{ [_x,]_x, x|x \in V \}\),V为一组和\(\Sigma\)不相交的变量集。定义字符串\([_x u]_x\)是变量x的一次引用，u是此引用的内容。一个引用是纯的，如果其内容不含引用和变量。变量x的一次出现是无定义的，如果在x左侧没有x的引用（即在语法树的先序遍历中，x在其引用的子表达式之前）。x的出现如果是有定义的，称其指向其左侧最近的x的引用。

定义 9. (解引用) 设w是\(\Sigma\)上的refword，D(w)是w的解引用，定义为如下对w的操作结果：

1. 删除w中所有无定义的变量x

2. 如果w中有引用，转3，否则结束。

3. 将w中所有的纯引用，和指向此引用的变量出现替换为引用的内容，转2。

定理 10. D(w)是良定义的。对任意refword w，D(w)总存在且惟一，且D(w)是\(\Sigma\)上的字符串。

定义 11. (ref-regular language) 一组\(\Sigma\)上的refword的集合L称为\(\Sigma\)上的ref-language，如果存在有限集\(\Gamma\)使得L\(\subseteq (\Sigma \cup \Gamma)^{\ast}\)。如果L是正规语言，则称为regular ref-language。

语言L称为是ref-regular语言，如果L是某个regular ref-language的解引用。称ref-regular的语言类为ref-REG

定理 12. L(Regex)=ref-REG

3自动机模型

MFA是关于Regex的自动机模型：

定义 13. (MFA) 带k个缓冲区的有限状态自动机M是五元组\((Q, \Sigma, \delta, q_0, F)\)。除下列条件外，定义与FA相同：\(\delta ：Q \times (\Sigma \cup \{ \varepsilon \} \cup \{ 1, 2, \ldots, k \}) \rightarrow P (Q \times \{ o, c, \diamond \}^k)\)。

M的格局定义为\((q, w, (u_1, r_1), \ldots, (u_k, r_k))\)，其中q和w为当前状态和剩余输入串，\(u_i\)是\(\Sigma\)上的字符串，\(r_i \in \{ O, C \}\)，其中O和C分别表示缓冲区处于打开和关闭状态。

给定缓冲区状态r和指令\(s \in \{ o, c, \diamond \}\)，定义：

如果格局\(c = (q, w, (u_1, r_1), \ldots, (u_k, r_k))\),\(c' = (q', w', (u'_1, r'_1), \ldots, (u'_k, r'_k))\)，则\(c \vdash c'\)当且仅当\((q', s_1, s_2, \ldots, s_k) \in \delta (q, b)\)，\(w = v w'\),并且或者\(v = b\)且\(b \in (\Sigma \cup \{ \varepsilon \})\),或者\(v = u_b, r_b = C\)且\(b \in \{ 1, 2, \ldots, k \}\).此时，\(r_i'\)如上定义，且对所有缓冲区都有：

输入串w能被M接受，当且仅当初始格局\((q_0, w, (\varepsilon, C), \ldots, (\varepsilon, C)) \vdash^{\ast} (q, \varepsilon, (u_1, r_1), \ldots, (u_k, r_k))\)，其中q是终止状态。定义M的语言为能被M接受的字符串集合。

定理 14. L(MFA)=L(Regex)=ref-REG

定义 15. MFA M是伪确定型MFA，如果其转移关系\(\delta\)是函数。

注意 16. 对任意MFA M，都能通过子集构造法构建一个等价的伪确定型MFA。

定义 17. MFA M是确定型MFA，或DMFA，如果M是伪确定型MFA，且满足对任意状态q，如果\(| \cup_{i = 1}^k \delta (q, i) | + | \delta (q, b) | \leqslant 1\)。直观地说，如果一个状态有对缓冲区i的读取，则此状态没有对其它缓冲区的读取，且没有读取输入字符的转移；反之亦然。

定理 18. \(L (\operatorname{DMFA}) \subset L (\operatorname{MFA})\)

定理 19. L(DMFA)对交、并、补不封闭。

以上证明见[4]

3.1TMFA

MFA不一定是完备的。TMFA是在MFA的基础上增加陷门状态trap，并规定在缓冲区匹配失败后进入trap，trap只有自环转移。

引理 20. \(L (\operatorname{TMFA}) = L (\operatorname{MFA})\)

DTMFA的定义和DMFA相比也有改变，最大的不同是允许空转移。DTMFA的性质也和DMFA不同

引理 21. \(L (\operatorname{DTMFA})\)对补封闭

定理 22. k个缓冲区n状态的DTMFA可以在\(O (n^2 + k | w |)\)内判定

4确定型Regex

确定型Regex的严格定义见[2]

定义 23. 将Regex a转换为对应的RefWord正则表达式之后，应用Glushkov NFA构造法。如果构造出的FA是DFA，则称Regex a是确定的。

定理 24. \(L (\operatorname{DRX}) \subset L (\operatorname{DTMFA}^{\operatorname{rej}}) \subset L (\operatorname{DTMFA})\)

定理 25. \(\operatorname{DRX}和正规语言不可比\)

定理 26. 有k个变量和n-k个终止符的DRX \(\alpha\)可以在\(O (| \Sigma | | \alpha | n + k | \omega |)\)内判定

定理 27. DRX对交、并、补、拼接不封闭

定理6和7对DRX同样适用。

参考文献