# Can we describe any context-sensitive language by a grammar without left recursion?

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.