# Difference between a cyclic and a left-recursive context-free grammar?

I am currently reading a paper indicating that a cyclic CFG and a left-recursive CFG are different things:

The original purpose of the LC transform is to allow simulation of left-corner parsing by top-down parsing, but it also eliminates left recursion from any noncyclic CFG. (from page 5 of http://research.microsoft.com/pubs/68869/naacl2k-proc-rev.pdf)

Note the second part of this quote:

it also eliminates left recursion from any noncyclic CFG.

I though that a cyclic grammar and a left-recursive grammar go hand in hand? What's the difference?

Thanks for any hint on this!

## 1 Answer

A context-free grammar is cyclic if there exists a non-terminal $A$ and a derivation in one or more steps $A\Rightarrow^+ A$. It is left-recursive if there exists a non-terminal $A$, a mixed sequence of terminals and non-terminals $\gamma$, and a derivation in one or more steps $A\Rightarrow^+ A\gamma$.

Hence cyclic implies left-recursive, but the converse does not hold. Note that a cyclic grammar can have infinitely many parses for a single terminal string---that might be problematic---, while there is little interest in having cycles in the applications I know (natural language processing and programming languages syntax), thus they are usually removed.

• Thank you for the clarification! Do you have a trustworthy source for that? I was told by others and have meanwhile seen it mentioned on Wikipedia, but I could need some "real" reference for a paper. Thanks :-) Edit: Harrison'sIntroduction to Formal Language Theory has a definition of it (or more precisely of cycle-free, which is simply the negotiation) – stefan.at.wpf Aug 14 '13 at 15:39