1

我正在学习形式语言和自动机理论，我有一个关于书中没有回答的问题的问题。问题是：

这种语言是上下文无关的、常规的还是上下文相关的？

L= {a n w w R b n | w 是 ( a+b )*, w R是 w 的倒数并且 n>=0 }

我认为这种语言是上下文相关的，因为它至少需要两个堆栈才能接受。

有人可以对此发表评论吗？

谢谢。

4

1 回答 1

1

语言 a n w w R b n是上下文无关语言。我们可以为这种语言编写上下文无关语法。

S -->  aSb | R
R -->  aRa | bRb | ^

^是空符号

PDA：用于语言 a n w w R b n

  • 推送前缀字符串an
  • 推 w
  • 弹出w同时将每个符号与符号匹配wR
  • 弹出所有a推入堆栈并匹配b后缀bn

注意：我们在通过 PDA 处理语言字符串 a n w w R b n时，我们不知道前缀an 在哪里结束，然后在w开始之前在哪里结束，wR因此对于这种语言，我们无法绘制 PDA 的确定性模型，尽管非确定性 PDA 是可能的. 重要的是非确定性 PDA 类别与确定性 PDA 类别不同，这意味着范围确定性上下文无关语言不等于非确定性上下文无关语言。（实际上确定性是非确定性 CFL 的子集）

于 2013-04-08T17:49:04.340 回答