1
$\begingroup$

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$ ?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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