来自语言问题的上下文无关语法

Question

我在尝试为以下语言制定上下文无关语法时遇到了一些问题：

L = { a^x b^y : y>=x, y-x is odd }

目前我有以下内容，但这并不完全有效

S -> aSb | Sb |epsilon

我该如何解决这种语言y-x is odd方面？这是我不确定该怎么做的一件事。

Answer 1

从你的语法开始：

S -> aSb | Sb |epsilon

这将生成 y>= x 的 a^x b^y。这非常接近，但正如您所指出的，未能通过"y - x 是奇数"测试。

我们如何解决这个问题？好吧，如果 y>= x 并且 y - x 是奇数，那么 y = x + z，其中 z 是某个正奇数。这是什么意思？这意味着

1. 你的第一个作品，S -> aSb，是完全可以的：我们需要一种方法来添加任意多个 A 并保持 B 的数量相同。

2. 你的第二部作品S -> bS有一个大问题：这允许你添加任意数量的B，但你必须添加奇数个B。

3. 你的第三部作品S -> epsilon有一个大问题：这允许你不再添加任何b，但零不是一个奇数。

为了解决这个问题，我们可以为b的奇数长度字符串的语言想出一个语法，并替换生产S -> aSb的RHS中的S。这将保证给你两个条件。b的奇数长度字符串的语法：

B -> b | bbB

结合您的语法并摆脱不良产品：

S -> aSb | B
B -> b | bbB

这应该可以做到。