大门|大门-CS-2017（第二组）|问题48

请考虑下列语言。 L _1. ={a ^P |p是质数} L _2. ={a ^N B ^M C ^2米 |n>=0，m>=0} L _3. ={a ^N B ^N C ²ⁿ |n>=0} L _4. ={a ^N B ^N |n>=1}

以下哪项是正确的？ 我 L _1. 是上下文无关但不规则的。 二、 L _2. 不是上下文无关的。 三、 L _3. 不是上下文无关的，而是递归的。 四、 L _4. 是与上下文无关的。 （A） 一、 仅限II和IV

（B） 仅限II和III

（C） 只有我和IV

（D） 仅限III和IV

答复: （D） 说明： L1既不是常规语言，也不是上下文无关语言，而是上下文敏感语言。

L2是上下文无关的，推任意数量的a，然后对于每个b，弹出两个c，直到所有b都结束，这可以通过使用一个堆栈来完成。

L3不是上下文无关的，因为我们不确定何时弹出b并按下a，因为它是三个连续终端之间的比较。

显然，L4是确定性上下文无关的，因为我们确信会首先将a推入堆栈，看到b时，我们肯定会弹出a。

声明三和声明四是正确的，选项（D）是正确的。

这个问题的小测验