In this video clip the teacher presents a grammar $A \rightarrow A \alpha | \beta$ and after providing the parse tree explains that the regular expression for the language generated is represented as $\beta \alpha ^*$.

Why isn't it $\alpha ^* \beta$ instead? Isn't the grammar left-recursive into terminal $\alpha$ and once terminal $\beta$ is reached the string ends?


Try some derivations:

  • $A\Rightarrow \beta$
  • $A\Rightarrow A\alpha\Rightarrow \beta \alpha$
  • $A\Rightarrow A\alpha\Rightarrow A\alpha\alpha\Rightarrow \beta \alpha\alpha$

The pattern is clear: starting from $A$, we'll generate strings of the form $\beta\alpha\dotsc\alpha$, in other words, $\beta\alpha^*$. Since at any stage we have $A$ on the left of the sentential form, we'll eventually generate strings with $\beta$ on the left.

If the grammar had been $A\rightarrow \alpha A\mid \beta$, then we'd derive strings of the form $\alpha^*\beta$.

  • $\begingroup$ Ok I get it now. Because we continue to derive the $A$ until we reach $\beta$ and terminate the derivation, so $A$ cannot derive to $\alpha$ without further recursion. I was reviewing a note from a while back and had forgotten that. Thanks. $\endgroup$
    – Dave
    Dec 3 '16 at 18:43

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.