The main question: is it possible to avoid left recursion in a context-sensitive grammar (see example below), i.e., if for any context-sensitive language $L$, there exists some context-sensitive grammar $G$ such that $L = L(G)$ and $G$ is left-recursion free?

Any reference on this matter would be a big help. Or, a sketch of a proof (counterexample, just an idea, or gut feeling) on yes / no / undecidable / known open problem... Or, is there any (maximal) subclass of CSLs that can be described by left-recursion-free CSGs?

After days of reading papers and textbooks, I have not found even a definition of left-recursive nonterminal/grammar for CSGs. I consider it as an extension of this notion in context-free grammars. In this sense, in the grammar (describing just the empty language) $$(\{S, B, C, X, Y\}, \{\mathtt{a}\}, \{S \to \mathtt{a}SBC, CB \to XB, XB \to XY, XY \to XC, XC \to BC\}, S)$$ the nonterminal symbol $X$ is left-recursive because $XB \Rightarrow XY$ is possible.

I already know that there exists one-sided normal form such that any CSG can be converted into an equivalent CSG with rules of the form $B \to \mathtt{a}$, $B \to XY$, or $BC \to XC$ (right context only, similar to Penttonen normal form). This, however, does not avoid indirect left recursion. There is also a strict subclass of CSLs called acyclic CSLs which is generated by acyclic CSGs with acyclic context-free core (in $\alpha A \beta \to \alpha \gamma \beta$, the $A \to \gamma$ is the context-free core). While this seems to be an argument for the no answer to my original question, I still do not see it as a proof that there cannot exist a CSG for some non-acyclic CSL without left recursion.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.