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 you have read our privacy policy.