grammar - 关于语法，什么时候允许使用 eplison 生产规则？

Question

我试图理解一个关于语法和生产规则的概念。

根据有关此主题的大多数材料：

1) Epsilon 产生式规则仅在它们没有出现在任何其他产生式规则的 RHS 上时才被允许。

但是，采用语法：

G = { T,N,P,S }

在哪里：

T = {a,b}
N = {S,S1}
S = {S}
P { 
    S -> aSb
    S -> ab
    S1 -> SS1
    S1 -> E         //Please note, using E to represent Epsilon.
  }

其中，语法的语言是：

L(G) = { a^n, b^n | n >= 1 }

在这种情况下，存在包含 Epsilon 的产生式规则（从 S1 派生），但 S1 也构成另一个产生式规则 (S1 -> SS1) 的 RHS 的一部分。

这不违反第1点吗？

Answer 1

您的声明：

仅当 Epsilon 产生式规则未出现在任何其他产生式规则的 RHS 上时，才允许使用它们。

最好表述为

如果非终端没有出现在任何生产规则的右侧，则该非终端可能具有 epsilon 生产规则。

在乔姆斯基的原始层次结构中，除类型 0（无限制）语法外，所有的 epsilon 产生式都被禁止。如果所有的 epsilon 产生式都被禁止，那么语法就不可能产生空字符串。我相信这不是乔姆斯基关心的问题。因此，只要开始符号本身不出现在任何产生式的右侧，大多数现代公式都允许开始符号的右侧为空。

碰巧的是，对 epsilon 产生式的限制比必要的要强一些。在上下文无关文法和常规文法（乔姆斯基类型 2 和类型 3 文法）的情况下，总是可以创建一个没有 epsilon 产生式的弱等价文法（如果文法可以产生单个产生式S → ε，则可能除外空字符串。）还可以删除许多其他使语法分析复杂化的异常：无法到达的符号、非生产性符号和循环产生式。所有这些消除组合的结果是“适当的上下文无关语法”。

因此，大多数现代的上下文无关文法公式并不要求右手边是非空的。

你的语法G = { T , N , S , P }

• T = { a , b }
• N = { S , S ₁ }
• S = { S }
• P {
    S → a S b
    S → a b
    S ₁ → S S ₁
    S ₁ → ε
  }

包含一个无法到达的符号S ₁。我们可以很容易地消除它，产生等价的语法G' = { T , N' , S , P' }：

• N' = { S }
• P' {
    S → a S b
    S → a b
  }

G'不包含任何 epsilon 产生式（但即使有，它们也可能被消除）。