grammar - 形式语法去除单元生产

Question

假设我有 2 个产品 X 和 Y。

X-> AL|BL|X,

Y-> CK|DK|X。

我想不可能减少 X 的单位产量，但 Y 是这种情况吗？

标签： grammarcontext-free-grammar

Answer 1

您可以删除单位生产 X → X，因为它没有效果 - 在任何派生中扩展 X → X 都可以通过使用其他 X 生产之一来删除和替换。

完成此操作后，您可以通过将 Y → X 替换为 Y → ω 来删除 Y 的所有单位产品，以获得每个剩余的产品 X → ω。