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

Question

我很好奇是否有这样一个正则表达式，它定义了所有可能的正则表达式。由于存在可能出现在RE中的转义字符，因此在另一个RE中表示这些字符将是棘手的，因为RE主要用于描述字母数字字符序列。

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

提前感谢

Answer 1

为了能够判断RE是否“合法”，您需要能够“计算括号”以检查它们是否平衡，这是RE (或FA)无法做到的。