JUCS - Journal of Universal Computer Science 6(9): 850-860, doi: 10.3217/jucs-006-09-0850
Uniquely Parsable Accepting Grammar Systems
expand article infoCarlos Martín-Vide‡, Victor Mitrana§
‡ Research Group on Mathematical Linguistics, Rovira i Virgili University, Tarragona, Spain§ University of Bucharest, Faculty of Mathematics, Bucharest, Romania

Corresponding author: Carlos Martín-Vide ( cmv@astor.urv.es )

© Carlos Martín-Vide, Victor Mitrana.
This article is freely available under the J.UCS Open Content License.
Citation: Martín-Vide C, Mitrana V (2000) Uniquely Parsable Accepting Grammar Systems. JUCS - Journal of Universal Computer Science 6(9): 850-860. https://doi.org/10.3217/jucs-006-09-0850
Open Access
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.