regex - 环视是否会影响正则表达式可以匹配哪些语言？

Question

现代正则表达式引擎中有一些功能可以让您匹配没有该功能就无法匹配的语言。例如，以下使用反向引用的正则表达式匹配由重复自身的单词组成的所有字符串的语言:(.+)\1 .这种语言不是常规语言，不能与不使用反向引用的正则表达式匹配。

环视是否也会影响正则表达式可以匹配哪些语言？即是否有任何语言可以使用其他方式无法匹配的环视进行匹配？如果是这样，这是否适用于所有类型的环视(消极或积极的前瞻或后视)或仅适用于其中一些？

Answer 1

正如其他答案所声称的那样，环视不会为正则表达式添加任何额外的功能。

我认为我们可以使用以下内容来展示这一点:

One Pebble 2-NFA (请参阅引用它的论文的引言部分)。

1-pebble 2NFA 不处理嵌套的前瞻，但是，我们可以使用多卵石 2NFA 的变体(参见下面的部分)。

简介

2-NFA 是一种非确定性有限自动机，它能够在其输入上向左或向右移动。

单卵石机器是机器可以在输入带上放置卵石(即用卵石标记特定输入符号)并根据当前输入位置是否有卵石进行可能不同的转换。

众所周知，One Pebble 2-NFA 具有与常规 DFA 相同的功能。

非嵌套前瞻

基本思路如下:

2NFA 允许我们通过在输入磁带中向前或向后移动来回溯(或“前向轨迹”)。因此，对于前瞻，我们可以对前瞻正则表达式进行匹配，然后在匹配前瞻表达式时回溯我们消耗的内容。为了准确知道何时停止回溯，我们使用卵石!我们在进入 dfa 进行前瞻之前放下鹅卵石，以标记回溯需要停止的位置。

因此，在通过 pebble 2NFA 运行我们的字符串结束时，我们知道我们是否匹配了先行表达式，并且剩下的输入(即剩下的要消耗的)正是匹配剩余部分所需的。

所以对于形式 u(?=v)w 的前瞻

我们有 u、v 和 w 的 DFA。

从 u 的 DFA 接受状态(是的，我们可以假设只有一个)，我们进行 e 转换到 v 的起始状态，用鹅卵石标记输入。

从 v 的接受状态，我们 e 转换到不断向左移动输入的状态，直到找到卵石，然后转换到 w 的起始状态。

从 v 的拒绝状态，我们 e 转换到一个不断向左移动直到找到鹅卵石的状态，然后转换到 u 的接受状态(即我们离开的地方)。

用于常规 NFA 的证明显示 r1 | r2 或 r* 等，为这些卵石 2nfas 结转。见 http://www.coli.uni-saarland.de/projects/milca/courses/coal/html/node41.html#regularlanguages.sec.regexptofsa有关如何将组件机器组合在一起为 r* 表达式等提供更大机器的更多信息。

上述 r* 等证明有效的原因是，当我们输入组件 nfas 进行重复时，回溯确保输入指针始终在正确的位置。此外，如果鹅卵石正在使用中，则它正在由其中一台超前组件机器进行处理。由于在没有完全回溯和取回卵石的情况下，没有从前瞻机器到前瞻机器的转换，因此只需要一台卵石机器。

例如，考虑 ([^a] | a(?=...b))*

和字符串 abbb。

我们有 abbb，它通过 peb2nfa 获取 a(?=...b)，最后我们处于状态:(bbb,matched)(即在输入 bbb 中剩余，并且它匹配了 'a'后跟'..b')。现在因为 *，我们回到开头(参见上面链接中的构造)，并输入 [^a] 的 dfa。匹配b，回到开头，再次输入[^a]两次，然后接受。

处理嵌套的前瞻

为了处理嵌套的前瞻，我们可以使用 k-pebble 2NFA 的受限版本，如下定义:Complexity Results for Two-Way and Multi-Pebble Automata and their Logics (见定义 4.1 和定理 4.2)。

一般来说，2 卵石自动机可以接受非正则集，但有以下限制，k-卵石自动机可以被证明是正则的(上面论文中的定理 4.2)。

如果鹅卵石是 P_1, P_2, ..., P_K

除非 P_i 已经在磁带上，否则不得放置 P_{i+1}，除非 P_{i+1} 不在磁带上，否则不得拾取 P_{i}。基本上，鹅卵石需要以 LIFO 方式使用。

在放置 P_{i+1} 的时间和拾取 P_{i} 或放置 P_{i+2} 的时间之间，自动机只能遍历位于 P_{i} 的当前位置之间的子词以及位于 P_{i+1} 方向的输入词的结尾。此外，在这个子词中，自动机只能充当带有 Pebble P_{i+1} 的 1-pebble 自动机。特别是不允许举起、放置甚至感知另一颗鹅卵石的存在。

所以如果 v 是深度 k 的嵌套前瞻表达式，那么 (?=v) 是深度 k+1 的嵌套前瞻表达式。当我们进入其中的前瞻机器时，我们确切地知道到目前为止必须放置多少鹅卵石，因此可以准确地确定要放置哪个鹅卵石，当我们退出该机器时，我们知道要提起哪个鹅卵石。通过放置卵石 t 进入深度 t 的所有机器，并通过移除卵石 t 退出(即我们返回到深度 t-1 机器的处理)。整机的任何运行看起来就像是树的递归dfs调用，可以满足多卵石机的上述两个限制。

现在，当您组合表达式时，对于 rr1，由于您进行了连接，因此 r1 的卵石编号必须按 r 的深度递增。对于 r* 和 r|r1，卵石编号保持不变。

因此，任何具有前瞻的表达式都可以转换为等效的多卵石机器，在卵石放置方面具有上述限制，因此是规则的。

结论

这基本上解决了弗朗西斯原始证明中的缺点:能够防止先行表达式消耗 future 匹配所需的任何内容。

由于后视只是有限字符串(不是真正的正则表达式)，我们可以先处理它们，然后再处理前瞻。

对于不完整的文章很抱歉，但完整的证明需要绘制大量数字。

在我看来它是正确的，但我会很高兴知道任何错误(我似乎喜欢:-))。