computer-science - 特定语言的上下文相关语法

Question

如何构建生成这种语言的语法？构造一个生成 L 的文法：

L = {a^n b^m c^k|k>n, k>m}

我相信我的作品应该遵循以下原则：

S-> ABCC
A-> a|aBC|BC
B-> b|bBC
C-> c|Cc
CB->BC

我们的想法是从 2 c 开始并始终保持一个 c，然后使用 C->c|Cc ad 尽可能多的 c。我的 C 产品如何记住 m 和 n 的数字。

Answer 1

一个选项如下：生成一个字符串，其中每次生成 ac时，您要么

• 不产生其他任何东西，
• 生成一个a与之配对，
• 生成一个b与之配对，或
• 生成一个a和一个b与之配对。

这从这里开始：

S → X

X → c | MXc | Xc

M → A | 乙| AB

公元前 → 公元前

ab → ab

学士 → 学士

（请注意，这是部分不完整的）。在这里，X 扩展为字符串一侧的一系列c'，这些 ' 在字符串的另一侧与As 和Bs 配对。As 和s 的产生B是为了确保在扩展之前将它们重新排序为正确的顺序。

这不考虑的一种情况是，如果您有一个形式为 a ⁿ c ^n+k的字符串会发生什么，但这可以按如下方式修复：

S → X | 是

X → c | MXc | Xc

M → A | 乙| AB

公元前 → 公元前

ab → ab

学士 → 学士

Y → aYc | Yc | C

希望这可以帮助！