7

假设我有一种正则表达式语言，支持文字、正负字符类、有序交替、贪婪量词?、*和+，以及非贪婪量词??、*?和+?。（这本质上是 PCRE 的一个子集，没有反向引用、环视断言或其他一些更高级的位。）用无序交替替换有序交替会降低这种形式主义的表达能力吗？

（无序交替——有时也称为“无序选择”——满足 L(S|T) = L(S) + L(T)，而有序交替满足 L(S|T) = L (S) + (L(T) - { a in L(T) : a extends some b in L(S) }). 具体来说，如果交替是无序的，模式a|aa将匹配字符串a，aa但前提a是交替已订购。）

换句话说，给定一个包含有序交替的模式 S，该模式是否可以重写为不包含有序交替（但可能是无序交替）的等效模式 T？

如果文献中已经考虑过这个问题，我将不胜感激任何人都可以提供的任何参考资料。我几乎没有找到关于扩展正则表达式形式的表达能力的理论工作（除了关于反向引用如何将你从常规语言转移到无上下文语法的常见事情之外）。

4

2 回答 2

1

在http://swtch.com/~rsc/regexp/regexp3.html [“正则表达式是否匹配字符串的子字符串？如果是，在哪里？”] 有必要在“DFA”中引入优先级的概念（我怀疑，您需要阅读整个系列才能理解，但有问题的“DFA”是从“动态”的 NFA 图扩展而来的）以处理有序的交替。虽然这只是对权威的呼吁，而不是证明，但我认为可以公平地说，如果 russ cox 不能做到（将有序交替作为纯粹的 DFA 表达），那么没有人知道如何去做。

于 2011-07-23T22:15:57.410 回答
-1

我没有检查任何文献，但我认为您可以为有序交替构造一个 DFA，从而证明它不会通过以下方式增加任何表达能力：

  1. 假设我们有正则表达式x||y其中x和y是正则表达式和|| 表示无序交替。如果是这样，我们可以构造 DFA 接受x和y。我们将标记那些DFA_x和DFA_y
  2. 我们将通过连接DFA_x和DFA_y分阶段构造x||y的 DFA
  3. 对于DFA_x中对应于某个字符串a 的每条路径（路径我的意思是图形意义上的路径没有遍历和边缘两次，所以a是DFA_“a*”中的路径，但aa不是）...
    • 对于字母 s 中的每个符号
      • 如果DFA_y 使用as（也就是说，如果在as 上运行，DFA_y不会提前停止，但它可能不一定接受）并且DFA_x不这样做，并且DFA_x不接受 as 的任何前缀，则创建从状态DFA_x在消耗a后结束的转换到状态DFA_y在消费后结束
  4. 最终 DFA 的接受状态是两个输入 DFA 的所有接受状态。起始状态是DFA_x的起始状态。

直观地说，它在输出 DFA 中创建了两个区域。其中一个对应于交替的第一个参数，另一个对应于第二个。只要交替的第一个参数可能匹配，我们就留在第一部分。当遇到一个确定第一个参数不匹配的符号时，如果可能的话，我们此时切换到第二部分。如果这种方法是错误的，请发表评论。

于 2011-07-21T21:32:27.163 回答