论文标题
商店的州语法
State Grammars with Stores
论文作者
论文摘要
州语法是无上下文的语法，其中制作与它们相关的状态是无上下文的语法，并且只有在当前状态与生产中的状态相匹配时，只有生产才能应用于非终端。一旦将状态添加到语法中，很自然地添加类似于机器模型的各种商店。通过这样的扩展，只有在当前句子表单和生产之间匹配的状态和从每个商店匹配的状态和价值时，才能应用制作。在这里，为不同的衍生模式提供了生成能力结果，有或没有其他商店。特别是，通过标准推导关系，可以表明添加相反的计数器不会增加容量，并且状态足够。此外，证明使用最左边的派生运行的具有逆转的计数器的状态语法与单向机器所接受的语言相吻合，并具有下降和逆转式的计数器，并且出人意料地证明，这些语言比与标准衍生关系的状态语法更弱（并且没有标准的衍生关系）。还研究了涉及与国家语法具有逆转计数器的空虚问题的复杂性。
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.
