grammar - Chomsky 范式中的 Kleene 闭包

Question

设n为任意终端。

考虑以下可能正确的 kleene 星在n上的表示：

N → n N | ε

（其中 ε 是空终端。）

维基百科说：

乔姆斯基范式中的每个语法都是上下文无关的，相反，每个上下文无关的语法都可以转换为乔姆斯基范式中的等效语法。

我看不出如何将上述语法转换为 CNF。

• 语法不是上下文无关的吗？
• 实际上有没有办法在 CNF 中表示它？

Answer 1

幸运的是，这可以用 CNF 编写。这是一种这样的语法：

S → ε | n | 不适用

N → n

A → n | 不适用

因此，该语言是上下文无关的。

希望这可以帮助！