大门|大门CS模拟2018 |第2组|问题50

设L（R）为正则表达式R表示的语言。设L（G）为上下文无关语法G生成的语言。设L（M）为图灵机M接受的语言。以下哪些决策问题是可判定的？

我 L（G）是否是确定性上下文无关语言？

二、 是否为L（G1）∩L（G2）是一种上下文无关语言，其中G1和G2是确定性语法？

三、 给定一个上下文无关语法G，L（G）=∑ ^∗ 为了一些字母∑？

四、 给定一个图灵机M和一个字符串w，是w吗∈ L（M）？ （A） 仅限III和IV （B） 仅限II和IV （C） 只有我和我 （D） 以上都没有 答复: （D） 说明： 所有这些都是无法确定的问题。选项（D）是正确的。 这个问题的小测验