TOC问题：上下文无关语法设计

Question

我想为

定义的语言设计 CFG

L= { w | {a,b,c}* 其中 w= a^i b^j c^k 且 i+j>k }

i+j=k 的情况很容易，但是我无法弄清楚 i+j>k 的情况如何。

Answer 1

我们可以从 i + j = k 的语法开始：

S := aSc | T
T := bSc | e

如果我们想要 i + j > k，我们需要至少一个额外的 a 或至少一个额外的 a。我们可以依次假设每一个并将它们组合成一个语法：

A := aW
W := aW | aWc | X
X := bX | bXc | e

B := aB | aBc | Y
Y := bZ
Z := bZ | bZc | e

S := A | B

S 的产生式不确定地在保证额外的 a 或额外的 b 之间进行选择。 A/W/X保证至少有一个额外的a，并允许任意数量的额外a和b。 B/Y/Z 保证至少有一个额外的 b，并允许任意数量的额外 a 和 b。

A/Y 需要额外的符号。 W/X/B/Z 保证 a+b 至少与 c 一样多。