Left Transformation Languages
Hidetaka Tanaka · Publications of the Research Institute for Mathematical Sciences · 1981
A subfamily LFT of the family CS of context-sensitive languages is investigated.Elements of LFT are called left transformation languages.Any context-sensitive language is represented in the form h(Li OLf) where Li, Z^eLFT, h is a length-preserving homomorphism, and I/f is the mirror image of Z/ 2 .This fact implies that the "LBAproblem" is equivalent to the problem whether LFT can be accepted by deterministic linear bounded automata.It is remarkable that LFT is an intersection-closed AFL and the emptiness problem for LFT is effectively solvable.Also LFT is shown to have the quasi-prefix property, and we can see that LFT and the family CF of context-free languages are incomparable. § 1. Introduction