Subclasses of Linear Context—Free Languages and Homomorphic Characterizations of Languages
Satoshi Okawa, Sadaki Hirose · Systems and Computers in Japan · 1991
Abstract This paper defines the right‐longer (left‐longer) linear grammars with the property for every production rule as natural variants of even linear grammars defined The relation is investigated among the language classes generated by those grammars, regular grammars, and linear context‐free grammars. Also investigated are the closure properties under some basic set operations. Finally, new homomorphic characterizations are given as follows. For every recursively enumerable language L, we can find two languages L1, L2 from each pair of those language classes except a pair of even linear languages and a homomorphism h such that L=h(L1L2). For the remainder pair, a result that h(L1L2) is linear context‐free is obtained.