语言 0^n1^n 可以表示为正则文法吗？

can the language 0^n1^n be expressed as a regular grammar?

首先：我不学习计算机科学，只是对形式语言感兴趣。

我知道这种语言不规则，因为有限状态机无法计算 b 之前的 a 的数量（它需要一个堆栈）and/or 因为您不能将其表达为正则表达式，但是下面不就是定义上述语言的正则文法吗？

S -> 0S | 1S | epsilon

还是因为 epsilon 而不算数？

不，定义您的语言的上下文无关语法是

S -> 0S1 | epsilon

您实际上可以构建树，例如使用字符串 000111

S -> 0S1 -> 00S11 -> 000S111 -> 000epsilon111 -> 000111

注意语法和正则表达式的定义。你提供的语法不起作用，因为它不能保证你有相同数量的 0 和 1。自己测试一下，例如，使用字符串 00011，它不是该语言的一部分，但它可以被您的语法识别。