Leftist Grammars and the Chomsky Hierarchy

Leftist grammars are 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. [13], where the accessibility problem for some general protection system was related to these grammars. This protection system was originally proposed in [4] and [15] in the context of Java virtual worlds. The accessibility problem is formulated in the form "Can object p gain (illegal) access to object q by a series of legal moves (as prescribed by the policy)?" The membership problem for leftist grammar is decidable [13], which implies decidability of the accessibility problem for the appropriate protection system. We study relationships between language classes defined by various types of leftist grammars and classes of the Chomsky hierarchy. We show that general leftist grammars can define languages which arenot context free, answering in the negative a question from [13]. Moreover, we study some restricted variants of leftist grammars and relate them to regular, deterministic context-free, and context-free languages.