大门|大门-CS-2007 |问题30

语言L={0 ^我 21 ^我 |我≥字母表{0,1,2}上的0}是： （A） 不是递归的 （B） 是递归的，是确定性的CFL。 （C） 是一种常规语言。 （D） 不是确定性CFL，而是CFL。 答复: （B） 说明： 让我们先 一种确定性下推自动机的设计 对于给定的语言。

• 对于“0”的每一次出现，我们在堆栈中推X。
• 出现“2”时，不执行堆栈操作。但是，自动机的状态改变了。
• 对于“1”的每一次出现，我们从堆栈中弹出X。
• 如果在Z末端 ₀ 则接受输入字符串

我们也 设计一台图灵机 对于给定的语言。

• 当输入字符串中出现“0”时，我们将其替换为X。然后，移动到最右角，用Y替换“1”。
• 我们回到最左边的“0”并重复上述过程。
• 当从输入字符串的开头向右遍历时，如果在X之后出现“2”，在“2”之后出现“Y”，则我们达到停止状态。

  因此，给定的语言是递归的。每种递归语言都是CFL。 因此，选项（B）就是答案。

  如果你在上面的帖子中发现任何错误，请在下面发表评论。

这个问题的小测验