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?


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

  • $\begingroup$ Ah, thank you it makes sense, one more question: When we substitute a single variable it counts as 1 substitution, but when we substitute multiple instances of the same variable at once, is it counted 1 substitution or do we say that number of substitutions are equal to "number of multiple instances replaced at once" $\endgroup$ Jan 20, 2023 at 7:06
  • 1
    $\begingroup$ No, that counts as that many substitutions, not one. $\endgroup$
    – Nathaniel
    Jan 20, 2023 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.