In a CFG, we might have :$A \rightarrow AA$ and $A \rightarrow a$ where $a$ is a terminal and $A$ is a variable.
Then if we apply the first rule, and then the second , do we get $aa$ or either $aA$ or $Aa$ ?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
A single substitution is one application of one rule. So the rule $A\to AA$ means "Pick any single $A$ in the string and replace it with $AA$" and "$A\to a$" means "Pick any single $A$ and replace it with $a$." Substitutions are done one at a time, and there's no way to write a rule that says "Replace every $X$ with $Y$, or replace them all with $Z$."
If you start with $A$ and apply the first rule, you certainly get $AA$, since there's no other choice. But there are two ways of applying $A\to a$ to $AA$: you could pick the first or second $A$ to replace with $a$.
Indeed, there are two ways to apply $A\to AA$ to the string $AA$. However, replacing either the first or second $A$ with $AA$ gives the string $AAA$.