外观是否影响正则表达式可以匹配哪些语言？

Question

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

外观是否也会影响正则表达式可以匹配的语言？即是否有任何语言可以使用无法匹配的外观匹配？如果是这样,对于所有类型的环视(负面或正向前瞻或后观)或仅仅针对其中一些而言,这是真的吗？

Answer 1

你问的问题的答案是,是否可以用常规表达式识别比常规语言更大的语言类型,而不是通过外观增强.

证明相对简单,但是将包含外观的正则表达式转换为一个的算法很麻烦.

首先:请注意,您总是可以否定正则表达式(通过有限字母表).给定一个识别表达式生成的语言的有限状态自动机,您可以简单地将所有接受状态交换为非接受状态,以获得能够准确识别该语言否定的FSA,其中有一系列等效正则表达式.

第二:因为正定语言(以及正则表达式)在否定时被关闭,所以它们也在交叉点下闭合,因为A交叉B = neg(neg(A)union neg(B))de Morgan定律.换句话说,给定两个正则表达式,您可以找到另一个匹配两者的正则表达式.

这允许您模拟环视表达式.例如,u(？= v)w仅匹配将匹配uv和uw的表达式.

对于负向前瞻,你需要等价于集合理论A\B的正则表达式,它只是A的交叉(neg B)或等价的neg(neg(A)union B).因此,对于任何正则表达式r和s,您可以找到一个正则表达式rs,它匹配那些匹配r但不匹配s的表达式.在负前瞻性术语中:u(？!v)w仅匹配与uw-uv匹配的表达式.

外观有用的原因有两个.

首先,因为正则表达式的否定可能导致更不整洁的东西.例如q(?!u)=q($|[^u]).

其次,正则表达式不仅仅匹配表达式,它们还消耗字符串中的字符 - 或者至少我们喜欢考虑它们.例如在python中我关心.start()和.end(),因此当然:

>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4

第三,我认为这是一个非常重要的原因,对正则表达式的否定并不能很好地解决连接问题.neg(a)neg(b)与neg(ab)不同,这意味着你无法将环境转换为你找到它的上下文 - 你必须处理整个字符串.我想这会让人们不愉快地工作并打破人们对正则表达的直觉.

我希望我已经回答了你的理论问题(深夜,如果我不清楚,请原谅我).我同意评论员的意见,他说这确实有实际应用.当我试图刮掉一些非常复杂的网页时,我遇到了同样的问题.

编辑

我为不清楚而道歉:我不相信你可以通过结构归纳给出正则表达式的规律性证明+我的u(？!v)w例子就是那个,一个例子,一个简单的例子在那.结构归纳不起作用的原因是因为外观以非组合的方式表现 - 我试图对上面的否定做出这一点.我怀疑任何直接的正式证据都会有很多混乱的细节.我试图想出一个简单的方法来展示它,但不能想出一个我的头顶.

为了说明使用Josh的第一个例子^([^a]|(?=..b))*$相当于7州DFSA,所有州都接受:

A - (a) -> B - (a) -> C --- (a) --------> D 
?          |           \                  |
|          (not a)       \               (b)
|          |              \               | 
|          v                \             v
(b)        E - (a) -> F      \-(not(a)--> G  
|            <- (b) - /                   |
|          |                              |
|         (not a)                         |
|          |                              |
|          v                              |
\--------- H <-------------------(b)-----/

仅A状态的正则表达式如下所示:

^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$

换句话说,通过消除外观来获得的任何正则表达式通常会更长,更麻烦.

回应Josh的评论 - 是的,我确实认为证明等效性的最直接方式是通过FSA.使这个更加混乱的原因是构建FSA的通常方法是通过一个非确定性的机器 - 它更容易表达u | v,就像用u和v机器构造的机器一样,epsilon过渡到它们中的两个.当然,这相当于确定性机器,但存在指数性爆炸的风险.而通过确定性机器更容易做出否定.

一般证据将涉及获取两台机器的笛卡尔积,并选择您希望在每个要插入外观的点保留的状态.上面的例子说明了我在某种程度上的意思.

对于不提供建筑而道歉.

进一步编辑: 我发现了一篇博文,其中介绍了一种用常规表达式生成DFA的算法,该表达式增加了外观.它很整洁,因为作者以明显的方式扩展了带有"标记的epsilon过渡"的NFA-e的概念,然后解释了如何将这样的自动机转换为DFA.

我认为这样的事情会是一种方法,但我很高兴有人写了它.在我身边想出一些如此整洁的东西.

Answer 2

正如其他答案所声称的那样,外观不会给正则表达式增加任何额外的功能.

我想我们可以使用以下内容显示:

一个卵石2-NFA(参见论文引言部分).

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

介绍

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

一台鹅卵石机器是机器可以在输入带上放置卵石的地方(即用卵石标记特定的输入符号),并根据当前输入位置是否有卵石进行不同的过渡.

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

非嵌套的Lookaheads

基本思路如下:

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

因此,在通过卵石2NFA运行我们的字符串结束时,我们知道我们是否匹配前瞻表达式,左边的输入(即剩下的东西)正是匹配剩余的所需要的.

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

我们有u,v和w的DFA.

从接受状态(是的,我们可以假设只有一个)为你的DFA,我们进行电子转换到v的开始状态,用鹅卵石标记输入.

从v的接受状态,我们e-transtion到一个状态,它继续向左移动输入,直到它找到一个卵石,然后转换到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*etc的上述证明工作的原因是,当我们输入组件nfas进行重复时,回溯确保输入指针始终位于正确的位置.此外,如果正在使用鹅卵石,那么它将由一个先行组件机器处理.由于没有从前瞻机器到先行机器的过渡,没有完全回溯并回到鹅卵石,所以只需要一台鹅卵石机器.

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

和字符串abbb.

我们有abbb通过peb2nfa进行(？= ... b),在结束时我们处于状态:( bbb,匹配)(即在输入bbb中保留,并且它匹配'a'然后是'..b').现在因为*,我们回到开头(参见上面链接中的结构),然后输入[^ a]的dfa.匹配b,回到开头,再次输入[^ a]两次,然后接受.

处理嵌套的Lookaheads

为了处理嵌套的前瞻,我们可以使用这里定义的k-pebble 2NFA的受限版本:双向和多卵石自动机及其逻辑的复杂性结果(参见定义4.1和定理4.2).

一般来说,2个卵石自动机可以接受非规则集,但是由于以下限制,k-pebble自动机可以显示为常规(上文中的定理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-1机器的处理).整个机器的任何运行看起来都像一个树的递归dfs调用,并且可以满足多鹅卵石机的上述两个限制.

现在当你组合表达式时,对于rr1,因为你连续,r1的卵石数必须增加r的深度.对于r*和r | r1,卵石编号保持不变.

因此,任何具有前瞻的表达式都可以转换为等效的多卵石机器,并且在卵石放置中具有上述限制,因此是常规的.

结论

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

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

对于不完整的写作表示抱歉,但完整的证据将涉及绘制大量数据.

它看起来对我来说,但我会很高兴知道任何错误(我似乎喜欢:-)).

Answer 3

我同意其他帖子看起来是常规的(这意味着它没有为正则表达式添加任何基本功能),但我有一个论点,它比我见过的其他更简单的IMO.

我将通过提供DFA构造来证明环视是常规的.当且仅当语言具有可识别它的DFA时,该语言才是常规语言.请注意,Perl实际上并不在内部使用DFA(有关详细信息,请参阅此文章:http://swtch.com/~rsc/regexp/regexp1.html),但我们为证明目的构建了DFA.

为正则表达式构造DFA的传统方法是首先使用Thompson算法构建NFA.由于两个正则表达式的片段r1和r2,汤普森的算法提供建筑用级联(r1r2),交替(r1|r2)和重复(r1*)的正则表达式.这允许您逐位构建NFA,以识别原始正则表达式.有关详细信息,请参阅上面的文章.

为了表明正面和负面的前瞻是常规的,我将提供一个结构用于连接u正面或负面前瞻的正则表达式:(?=v)或(?!v).只有连接才需要特殊处理; 通常的交替和重复结构工作正常.

u(？= v)和u(？!v)的构造是:

换句话说,将现有NFA的每个最终状态连接u到接受状态和 NFA v,但修改如下.该功能f(v)定义为:

• 我们aa(v)是上NFA的功能v改变每一个接受状态为"反接受国家".抗接受状态被定义为使所述匹配如果失败的状态下任何通过NFA路径在该状态下对于给定的字符串结尾s,即使通过不同的路径v为s在接受状态结束.
• 让我们loop(v)成为NFA上的一个函数,v它可以在任何接受状态上添加自转换.换句话说,一旦路径通向接受状态,无论接下来是什么输入,该路径都可以永远保持在接受状态.
• 对于负向前瞻,f(v) = aa(loop(v)).
• 对于积极的向前看,f(v) = aa(neg(v)).

为了提供一个直观的例子,我将使用正则表达式(b|a(?:.b))+,这是我在弗朗西斯证明的评论中提出的正则表达式的略微简化版本.如果我们将我的结构与传统的Thompson结构一起使用,我们最终得到:

的es为小量转变(转换可以采取,而不消耗任何输入)和抗接受状态被标记有一个X.在图的左半部分,您可以看到以下表示形式(a|b)+:any a或b将图形置于接受状态,但也允许转换回到开始状态,以便我们可以再次执行此操作.但请注意,每次我们匹配时,a我们也会输入图表的右半部分,我们处于反接受状态,直到我们匹配"any"后跟a b.

这不是传统的NFA,因为传统的NFA没有反接受状态.但是,我们可以使用传统的NFA-> DFA算法将其转换为传统的DFA.该算法像往常一样工作,我们通过使我们的DFA状态对应于我们可能处于的NFA状态的子集来模拟NFA的多次运行.一个转折点是我们稍微增加了用于确定DFA状态是否为接受(最终)状态.在传统算法中,如果任何 NFA状态是接受状态,则DFA状态是接受状态.我们对此进行了修改,以便DFA状态是一个接受状态,当且仅当:

• = 1 NFA状态是接受状态,并且

• 0 NFA州是反接受州.

该算法将为我们提供一个DFA,可以通过前瞻识别正则表达式.因此,前瞻是常规的.请注意,lookbehind需要单独的证明.