Uniquely Parsable Accepting Grammar Systems

Carlos Martín-Vide (Research Group on Mathematical Linguistics, Rovira i Virgili University, Spain)

Victor Mitrana (University of Bucharest, Faculty of Mathematics, Romania)

Abstract: We extend the restrictions which induce unique parsability in Chomsky grammars to accepting grammar systems. It is shown that the accepting power of global RC-uniquely parsable accepting grammar systems equals the computational power of deterministic pushdown automata. More computational power, keeping the parsability without backtracking, is observed for local accepting grammar systems satisfying the prefix condition. We discuss a simple recognition algorithm for these systems.

Categories: F.4.2, F.4.3