包含有序交替的正则表达式是否可以重写为仅使用无序交替？

Question

假设我有一个正则表达式语言支持文字,正面和负面的字符类,有序交替,贪婪的量词?,*以及+和nongreedy量词??,*?和+?.(这实际上是PCRE的一个子集,没有反向引用,环视断言或其他一些更高级的位.)用无序交替替换有序交替是否会降低这种形式主义的表达能力？

(无序交替---有时也称为"无序选择"---是L(S | T)= L(S)+ L(T),而有序交替是L(S | T)= L (S)+(L(T) - {a in L(T):a在L(S)中延伸一些b}}.具体地说,模式a|aa将匹配字符串a,aa如果交替是无序的,但仅a在交替时订购.)

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

如果在文献中考虑过这个问题,我会感谢任何人都可以提供的任何参考.我几乎没有关于扩展正则表达式形式主义的表达能力的任何理论工作(除了关于后向引用如何将你从常规语言转移到无上下文语法之外).

Answer 1

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

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

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