LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata

摘要

The paper introduces a subfamily of synchronized alternating pushdown automata, deterministic synchronized alternating pushdown automata, and a subfamily of conjunctive grammars, LR(0) conjunctive grammars. It is shown that deterministic synchronized alternating pushdown automata and LR(0) conjunctive grammars have the same recognition/generation power, analogously to the classical equivalence between acceptance by empty stack of deterministic pushdown automata and LR(0) grammars. These models form the theoretical basis for efficient linear time parsing of a subfamily of conjunctive languages which properly includes the classical LR(0) languages.