4

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

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

提前致谢

4

1 回答 1

4

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

于 2013-02-06T19:08:34.450 回答