如果G是上下文无关语言，那么L(G) = (sigma) *是可判定的还是不可判定的？

Question

如果G是上下文无关语言，那么L(G) = (sigma) *是可判定的还是不可判定的？我从哪里得到这个问题的来源是，答案是undecidable...but，我认为它是可决定的，因为:由于sigma *是无限的(如果我错了，请纠正我)，并且上下文无关语言的无穷性是可决定的，所以上述是无限上下文无关语言，我认为它是可决定的……

Answer 1

你的论点的问题是有很多无限的语言-所有的字符串，偶数长度的字符串，回文，重复字符串，等等。也许可以说CFG的语言是无限的，而不能准确地说出它是哪种无限语言。有无数种语言与所有字符串的语言相同，只是它们缺少一个字符串。或者两个字符串。或者三个。

来自维基百科：

CFG是否生成所有字符串的问题可以证明是简化的，这个问题来自于确定图灵机是否接受特定输入的众所周知的不可判定问题(

问题)。该简化使用了计算历史的概念，即描述图灵机的整个计算的字符串。可以构造一个CFG，它生成不接受特定图灵机在特定输入上的计算历史的所有字符串，因此，只有当机器不接受该输入时，它才会接受所有字符串。