gotchaMinor
Why does this grammar derive into $\beta \alpha ^*$ instead of $\alpha ^* \beta$?
Viewed 0 times
thisalphawhyderiveintobetainsteadgrammardoes
Problem
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?
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?
Solution
Try some derivations:
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$.
- $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$.
Context
StackExchange Computer Science Q#66884, answer score: 4
Revisions (0)
No revisions yet.