theory - 解释工作面试的上下文无关语法歧义

Question

我在参加工作面试，这是他们问我的问题，

下面这两个是模棱两可的吗？如果是，请提供一个字符串。如果不是，请证明为什么不是。

解决不了，想知道答案和未来的原因。

问题 1

S-->XaaaX
X-->aX | bX | e(epsilon)

问题2

S-->aaS | aaaS | a

同样，这不是硬件。

谢谢你。一个解释会有所帮助。

Answer 1

我们记得，当（且仅当）该文法的某些产生式具有多个可能的派生时，该文法是模棱两可的。

在问题 1 中，符号 S 扩展为 XaaaX，然后扩展符号 X 的可用替代方案包括 aX 和 epsilon (ε)。通常，符号 epsilon 表示一个空字符串。在 aX 中将 X 扩展为 epsilon 产生 a。所以至少有两种方法可以得到 aaaa。理查德麦肯纳，我会留给你找到他们。

在问题 2 中，符号 S 扩展为 aaS、aaaS 或 a。至少有两种方法可以得到 aaaaaa。我再一次留给你去寻找推导。

如果您愿意，您可以在此页面上写下您的推导。