在无上下文的语法中，我们在替换过程中是否替换所有变量？还是我们只能将替代规则仅适用于同一类型的变量？

Question

想象一下，我们有一个免费的语言语法，CFG，如下：

S-＆GT; A ...（1）

S-＆GT; ）

中得出一个字符串，如下：

，我在指定的语言

2

ss ... （ 在1个变量上而不是所有相同变量上的施加规则？

因此，我的问题是我是否要在“ SS”上应用规则（1），我是否可以选择（1）将（1）应用于“ SS”的1秒钟，还是我必须对两个s申请？

Answer 1

您只能将规则应用于一个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
...

无论如何，我们发现语法会产生A和B的所有非空字符串，包括那些混合A和B的弦。如果我们必须用相同的规则替换所有S，那么如果我们有一种（非空）的语言，我们将获得更小得多的语言。