[SOLVED] 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?

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?

Imagine we have a Context Free Grammer, CFG, as follows:

S -> a ...(1)

S -> SS ...(2)

And i derive a string in the specified language as follows:

S ..start state

SS ..using (2)

aS ...using (1) <- is this valid, like only applying the subsititution rule on 1 variable instead of all same variables?

So my question is if i were to apply rule (1) on "SS", do i have the option to apply (1) to only 1 S of the "SS" or do i have to apply to both of them?

Solution

You can apply the rule to only one S, or as many as you like. Here is a slightly more complicated example that maybe better illustrates the idea:

S -> a       (1)
S -> b       (2)
S -> SS      (3)

So, what strings are in this language? Here are the first few strings with derivations:

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
...

Anyway, we find that the grammar generates all non-empty strings of a's and b's, including those with mixed up a's and b's. If we had to replace all S's with the same rule, we would get a much, much smaller language, if we'd get a (non-empty) language at all.