☰

是否可以在 {0,1} 上使用egrep这些对称表达式

tag-icon • tag-icon grep
是否可以在 {0,1} 上使用egrep这些对称表达式

目标是仅使用egrep来匹配表达式，其中n出现 0 后紧跟着n出现 1 并且 1 后面没有 0。

例如

01
000111
000000111111

但不是：

001
011
00011

ETC。

直观上，这似乎无法实现，因为可匹配的表达式不是固定长度的。但也许我错过了egrep 的一个可能对此有用的功能？

答案1

一些 CS 概念的快速概述：

  • 自动机接受属于“语言”的字符串，由“语法”生成。
  • 正则表达式（理论上）相当于（确定性或非确定性）有限自动机（DFA/NFA）。因此，给定一个像 的正则表达式0*1*，DFA 和 NFA 可以接受与该正则表达式匹配的字符串。
  • 有限自动机的功能严格来说不如下推自动机（掌上电脑）。 PDA 接受的语言类别是由以下生成的上下文无关语法（CFG）。
  • 您正在查看的字符串 - - 由 CFG 生成：（松散地，给定一个起始字符串，您可以在原始字符串的任一侧生成一个带有 和 的字符串，或者什么都不生成 - 所以它可以让您生成、等。 ）。0n1nS -> 0S1 | ε01010011

虽然 grep（扩展或其他）具有超出上述“正则表达式”的功能，例如反向引用，但我不相信任何这些功能都可以将其扩展到与 PDA 一样强大。

可以S -> 0S1 | ε通过使用来证明它不是正则的泵送引理，但我没有证据证明 grep 的功能能够（或无法）接受 CFG。然而，维基百科上的文章常用表达有这样的说法（粗体是我的）：

几乎所有现代正则表达式库中都有的许多功能提供了远远超过正则语言的表达能力。例如，许多实现允许使用括号对子表达式进行分组，并调用它们在同一表达式中匹配的值（反向引用）。这意味着，除其他外，模式可以匹配重复单词的字符串，例如“papa”或“WikiWiki”，在形式语言理论中称为方块。这些字符串的模式是(.+)\1。

方块的语言不规则，它也不是上下文无关的，由于泵引理。然而，正如许多现代工具所支持的那样，具有无限数量的反向引用的模式匹配仍然是上下文敏感的。[33]

[33]：Cezar Câmpeanu 和 Kai Salomaa，以及 Shen Yu（2003 年 12 月）。 “实用正则表达式的正式研究”。国际计算机科学基础杂志。 14（6）：1007-1018。 doi：10.1142/S012905410300214X。定理 3（第 9 页）

所以，我可以肯定地说它本身grep无法匹配。0n1n

相关内容