1

我需要生成明确的语法来访问语言L= { a^i b^j c^k | i, j, k ≥ 0 , i = j or i = k }

我已经拥有的是：

S : X | Y
X : TC
T : aTb | ԑ
C : cC | ԑ
Y : aYc | F
F : bF | ԑ

但是这种语法是模棱两可的，它可以通过两种不同的方式识别 a,b,c 数量相等的字符串。有没有更好的建议让它明确？

4

2 回答 2

1 
S : X | Y | Z
X : aXb | ԑ
Y : aYc | F
Z : Zc | X | ԑ
F : Fb | ԑ

以上规则较少并产生正确的字符串，但我承认它仍然模棱两可。

问题中的语言 L 的语法可以分为两个子语法，产生以下字符串：a^i b^i c^j和a^i b^j c^j这两者的交集将导致这种表达式：a^i b^i c^i。可以证明，如果两个语法的交集产生这种表达式，则该语法本质上是模棱两可的：http ://en.wikipedia.org/wiki/Ambiguous_grammar#Inherently_ambiguous_languages

于 2014-06-02T08:30:28.420 回答
0

我认为这个主题将帮助您将歧义语法转换为明确的 并从语法中消除歧义

于 2014-06-02T08:33:42.763 回答