Leftist Grammars and the Chomsky Hierarchy

摘要

Leftist grammars can be characterized in terms of rules of the form a → ba and cd → d, without distinction between terminals and nonterminals. They were introduced by Motwani et. al., where the accessibility problem for some general protection system was related to the membership problem of these grammars. This protection system was originally proposed in [3,10] in the context of Java virtual worlds. We show that the set of languages defined by general leftist grammars is not included in CFL, answering in negative a question from [9]. Moreover, we relate some restricted but naturally defined variants of leftist grammars to the language classes of the Chomsky hierarchy.