Paper Info
Title
State Grammars with Stores.
Abstract
State grammars are context-free grammars where the productions have states associated with them, and a production can only be applied to a nonterminal if the current state matches the state in the production. Once states are added to grammars, it is natural to add various stores, similar to machine models. With such extensions, productions can only be applied if both the state and the value read from each store matches between the current sentential form and the production. Here, generative capacity results are presented for different derivation modes, with and without additional stores. In particular, with the standard derivation relation, it is shown that adding reversal-bounded counters does not increase the capacity, and states are enough. Also, state grammars with reversal-bounded counters that operate using leftmost derivations are shown to coincide with languages accepted by one-way machines with a pushdown and reversal-bounded counters, and these are surprisingly shown to be strictly weaker than state grammars with the standard derivation relation (and no counters). The complexity of the emptiness problem involving state grammars with reversal-bounded counters is also studied.
Year
DOI
Venue
2018
10.1016/j.tcs.2019.06.024
Theoretical Computer Science
Keywords
Field
DocType
Grammars,Reversal-bounded counters,Automata models,Matrix grammars,Emptiness problem,P,NP,NP-completeness
Rule-based machine translation,Terminal and nonterminal symbols,Decision problem,Computer science,Theoretical computer science,Machine models,Formal grammar,Generative grammar
Conference
Volume
ISSN
Citations 
798
0304-3975
1
PageRank 
References 
Authors
0.36
8
2
Name
Order
Citations
PageRank
Oscar H. Ibarra13235741.44
Ian McQuillan29724.72