On left recursive context-free grammars

128 Views Asked by At

Definition Context-free grammar $G$ is said to be left-recursive, if there exists such non-terminal symbol $A$, that one can derive from it a word $A\alpha$, where $\alpha$ is a word over unified terminal and non-terminal alphabets.

Given $G$ with terminal alphabet $\{a, b, c\}$, non-terminal alphabet $\{S, R, T\}$ and rules:
$\ \ \ \ S \to aR$
$\ \ \ \ R \to bRT \ | \ \varepsilon$
$\ \ \ \ T \to cSR \ | \ \varepsilon$
am I right in assuming $G$ is not left recursive, as any word derivable from any non-terminal is either empty or starts with a terminal symbol?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, you are correct. Any sentence derivable from any non-terminal starts with a terminal, except for the empty sentence. So there is no left-recursion.