4

如果我们用 operator *、|concatenation .（为了清楚起见，我们简单地省略了）、括号(和)来自一些字母的一些字母Sigma来描述正则表达式，那么描述正则表达式的语言本身就是正则表达式吗？在我看来不，因为我们有括号这一事实意味着没有有限状态机可以识别输入，所以它必须是一种上下文无关的语言。

注意题外话

我坚持我的立场，即这个问题与编程有关，因为我是在考虑编写正则表达式识别器时提出这个问题的。如果有人想要实现这样的事情，那么很快就会意识到您实际上需要一个上下文无关的解析器来解析正则表达式，这个问题将回答这个问题。此外，答案和问题并不是“非常理论化”，因为有限自动机的主题被认为是 1 年级和 2 年级本科生材料，因此将其放在理论计算机科学 Stackexchange 中将是一种矫枉过正。

4

1 回答 1

4

不，这不正常。考虑到单独使用平衡括号的语言甚至不是规则的。使用平衡括号语言的泵引理的矛盾证明也适用于正则表达式的语言。

不过它是无上下文的，而且很容易用无上下文的语法来描述：

S -> SS
S -> S|S
S -> S*
S -> (S)
S -> a
S -> b
S -> c
S -> ...     // Continue for all terminals in the alphabet, and
S -> epsilon // The empty string
于 2014-05-12T00:49:18.563 回答