在上下文无关语法中，我们是否在替换过程中替换所有变量？或者我们可以将替换规则仅应用于相同类型的变量吗？
In Context Free Grammer, do we replace all variable during a substitution? or can we apply substitution rule to only of the variable of same type?
假设我们有一个Context Free Grammer，CFG，如下：
S -> a ...(1)
S -> SS ...(2)
然后我推导出指定语言的字符串如下：
S ..开始状态
SS ..使用 (2)
aS ...使用 (1) <- 这是否有效，例如仅对 1 个变量而不是所有相同变量应用替换规则？
所以我的问题是，如果我要对“SS”应用规则 (1)，我是否可以选择仅将 (1) 应用到“SS”的 1 个 S，还是我必须对两者都应用其中？
您可以仅将规则应用于一个 S，也可以根据需要对多个 S 应用。这是一个稍微复杂一点的例子，也许能更好地说明这个想法：
S -> a (1)
S -> b (2)
S -> SS (3)
那么，这种语言中的字符串是什么？这是前几个带有推导的字符串：
a: S -> a
b: S -> b
aa: S -> SS -> aS -> aa
S -> SS -> Sa -> aa
ab: S -> SS -> aS -> ab
S -> SS -> Sb -> as
ba: S -> SS -> bS -> ba
S -> SS -> Sa -> ba
bb: S -> SS -> bS -> bb
S -> SS -> Sb -> bb
aaa: S -> SS -> aS -> aSS -> aaS -> aaa
S -> SS -> aS -> aSS -> aSa -> aaa
S -> SS -> Sa -> SSa -> aSa -> aaa
S -> SS -> Sa -> SSa -> Saa -> aaa
aab
...
总之，我们发现语法生成了所有non-empty个a和b的字符串，包括那些a和b混合的字符串。如果我们必须用相同的规则替换所有 S，我们将得到一种小得多的语言，如果我们得到一种 (non-empty) 语言的话。
假设我们有一个Context Free Grammer，CFG，如下：
S -> a ...(1)
S -> SS ...(2)
然后我推导出指定语言的字符串如下：
S ..开始状态
SS ..使用 (2)
aS ...使用 (1) <- 这是否有效，例如仅对 1 个变量而不是所有相同变量应用替换规则？
所以我的问题是，如果我要对“SS”应用规则 (1)，我是否可以选择仅将 (1) 应用到“SS”的 1 个 S，还是我必须对两者都应用其中？
您可以仅将规则应用于一个 S，也可以根据需要对多个 S 应用。这是一个稍微复杂一点的例子，也许能更好地说明这个想法：
S -> a (1)
S -> b (2)
S -> SS (3)
那么，这种语言中的字符串是什么？这是前几个带有推导的字符串：
a: S -> a
b: S -> b
aa: S -> SS -> aS -> aa
S -> SS -> Sa -> aa
ab: S -> SS -> aS -> ab
S -> SS -> Sb -> as
ba: S -> SS -> bS -> ba
S -> SS -> Sa -> ba
bb: S -> SS -> bS -> bb
S -> SS -> Sb -> bb
aaa: S -> SS -> aS -> aSS -> aaS -> aaa
S -> SS -> aS -> aSS -> aSa -> aaa
S -> SS -> Sa -> SSa -> aSa -> aaa
S -> SS -> Sa -> SSa -> Saa -> aaa
aab
...
总之，我们发现语法生成了所有non-empty个a和b的字符串，包括那些a和b混合的字符串。如果我们必须用相同的规则替换所有 S，我们将得到一种小得多的语言，如果我们得到一种 (non-empty) 语言的话。