☰

是否可以在 {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

相關內容