context-free-grammar - Σ* 是上下文无关语言吗

Question

Σ∗ 是上下文无关文法吗？因为我想知道我是否可以用它来证明如果“对于每种语言 A，如果 A 不是上下文无关的，那么 A 不是上下文无关的”。

Answer 1

语言 Σ* 不是上下文无关文法（CFG 是一组定义语言的规则；Σ* 是一种语言），但它是上下文无关语言。有很多方法可以看到这一点：

• 您可以为它定义一个 CFG。用产生式规则 S → aS 为每个字符 a ∈ Σ 创建一个简单的文法，再加上最后一条规则 S → ε 来停止递归。

• 你可以为它定义一个PDA。有一个正在接受的状态，并且在任何字符上都有一个循环回到自身，完全忽略堆栈。

• 你可以注意到它是正则的——Σ* 本身就是一个正则表达式——并且所有正则语言都是上下文无关的。

至于您是否可以使用它来证明该特定陈述的后续问题，我认为您在那里写的内容有误，因为所写的内容是暗示自己的同一陈述。如果您的意思是“如果一种语言不是上下文无关的，那么它就不是规则的”，这是正确的，并且是从最后一个要点的反义词得出的。