In Context free languages, is it okay to substitute multiple same variables at the same time?

Question

Let's say we have the following context free grammar:

$S \rightarrow a \\ S \rightarrow SS$

And we do the following two "derivations" for the same string:

aaa: $S \rightarrow SS \rightarrow SSS \rightarrow aaa$

aaa: $S \rightarrow SS \rightarrow SSS \rightarrow aSS \rightarrow aaS \rightarrow aaa$

The difference between the two derivation is that: in first derivation we just replaced multiple same variables at once, whilst in the second derivation we replaced multiple same variables one by one

Are these two different derivations? or just one derivation? Because their parse trees would look different. Which one should i stick to?

Answer 1

It is possible, though it is often denoted with a $^*$ to indicate that there is a sequence of replacement instead of just one replacement:

$$S\Rightarrow SS \Rightarrow SSS \Rightarrow^* aaa$$

Note that I am using a $\Rightarrow$ symbol instead of a $\to$ one to distinguish derivations of strings from production rules.

Sure, parse trees could look different, but that is also the case when doing one replacement at a time: in your second derivation, the replacement $SS\Rightarrow SSS$ could be interpreted as "the first $S$ is replaced with $SS$" or as "the second $S$ is replaced with $SS$". This would lead to two different parse trees.

One can lift ambiguity of derivation (but not necessarily ambiguity of grammar) by considering only leftmost or rightmost derivations.