正则文法

Question

在规则为S->aS/aSbS/ε的常规语法中，执行以下步骤是可以接受的：

我是否必须在每一步中替换每一个S，或者我可以替换两个S中的一个？在这里: aSbS我可以做aSb (遵循规则S->ε)，如果不能，我应该用相同的规则替换所有S吗？(aSbS)-> a(aS)b(aS) (遵循规则(S->aS) )或I可以执行(aSbS->a(aS)b(aSbS))。

ps。我用括号表示我替换了哪一个S

Answer 1

在形式语法中，派生步骤包括将规则左侧的单个实例替换为该规则的右侧。在上下文无关语法的情况下，左侧是单个非终端，因此派生步骤包括用可能的相应右侧之一替换非终端的单个实例。

您永远不会同时执行两个替换，而且每个派生步骤都独立于每个其他派生步骤，因此在上下文无关语法中，无法表达这样的约束:两个非终端需要替换为相同的右侧。(实际上，您也不能用上下文敏感的语法直接表示这个约束，但是可以通过使用标记来达到这种效果。)

普通语法是上下文无关文法的子集，其中包括非终端的每个右侧都有表单aC，或者每个包含非终端的右侧都有表单Ba。(这直接来自你链接的维基百科页面。)您的语法不是规则语法，因为规则S → aSbS在右侧隐藏了两个非终端，这不是规则形式中的任何一个。