所有合法正则表达式的正则表达式

Question

这个问题在这里已经有了答案:





Is there a regular expression to detect a valid regular expression?

(9 个回答)


8年前关闭。




我很好奇是否有这样一个定义所有可能的正则表达式的正则表达式。由于 RE 中可能会出现转义字符，因此在另一个(例如验证器 RE)中表示此类字符会很棘手，因为 RE 主要用于描述字母数字字符序列。

我的问题可以类似地解释为是否有一个有限自动机能够决定一个有限自动机候选者是否为 FA。这是因为我们知道 FA 的设计方式可以排除给定的输入字符串与 FA 定义或未定义的模式相匹配。因此，如果我们能以某种方式将所有内容(FA 候选)定义为字符串，我们将能够定义一个 FA 来验证输入是否为 FA。但是，我不知道如何证明这一说法，如果您能帮助我如何证明这一点，我会很高兴。

提前致谢

Answer 1

为了能够确定 RE 是否“合法”，您需要能够“计算括号”以检查它们是否平衡，而使用 RE(或 FA)则无法做到这一点。