0

我有一个关于为该语言设计下推自动机的问题：

L = { w in {a, b}* : 2n_a(w) <= n_b(w) <= 3n_a(w) }

换句话说，'s in 的数量是b'sw数量的2 倍和's 数量a的3 倍之间a。

我对这个问题感到困惑：我知道（希望如此！）当 's 的数量分别b等于 's 数量的两倍a或 's 数量的 3 倍时，如何设计 PDA 以接受该语言a。

这种语言似乎是它们的交集，但我认为没有一种简单的方法可以使用这些交集来创建 PDA。我们如何结合数字可以介于两个值之间的事实。

任何帮助深表感谢...

PS如果您还可以提供上下文无关的语法（以及解释），那也将非常有帮助。

PPS：另外，如果有人可以提供一个链接以某种方式展示如何逐步构建无上下文语法，我真的需要它。（我找到了正则表达式的正则文法的链接，但是对于上下文无关文法，当我尝试跟踪变量并看到一个变量转到自身，或者转到另一个变量时，该变量又返回到初始变量，我真的很困惑。）

4

1 回答 1

0

你需要让你的 PDA 让每个 a 推动两个 b 或三个 b。例如，一个包含 3 个 a 和 8 个 b 的字符串：第一个 a 推动 3 个 b，第二个 a 推动 3 个 b，第三个 a 推动 2 个 b。

我认为这个 CFG 涵盖了所有情况：S -> aB|Ba|EOS B -> SbSbS|SbSbSbS

这意味着对于每个 a，有两个 b 或三个 b。

https://www.youtube.com/watch?v=AbbZVvQkees 这是 PDA 的一个很棒的 youtube 频道。

于 2014-06-10T18:32:17.640 回答