...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Finite turns and the regular closure of linear context-free languages
【24h】

Finite turns and the regular closure of linear context-free languages

机译：有限的转弯和线性无上下文语言的常规封闭

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Turn bounded pushdown automata with different conditions for beginning a new turn are investigated. Their relationships with closures of the linear context-free languages under regular operations are studied. For example, automata with an unbounded number of turns that have to empty their pushdown store up to the initial symbol in order to start a new turn are characterized by the regular closure of the linear languages. Automata that additionally have to re-enter the initial state are (almost) characterized by the Kleene star closure of the linear languages. For both a bounded and an unbounded number of turns, requiring to empty the pushdown store is a strictly stronger condition than requiring to re-enter the initial state. Several new language families are obtained which form a double-stranded hierarchy. Closure properties of these families under AFL operations are derived. The regular closure of the linear languages share the strong closure properties of the context-free languages, i.e., the family is a full AFL. Interestingly, three natural new language families are not closed under intersection with regular languages and inverse homomorphism. Finally, an algorithm is presented parsing languages from the new families in quadratic time. 0 2007 Elsevier B.V. All rights reserved.
机译：为了开始新的转弯，研究了具有不同条件的转弯边界下推自动机。研究了它们与常规操作下线性上下文无关语言的闭包的关系。例如，具有无限转数的自动机必须清空其下推存储直到初始符号才能开始新的转轮，其特征在于线性语言的规则关闭。额外必须重新进入初始状态的自动机（几乎）以线性语言的Kleene星型闭合为特征。对于有界转弯和无界转弯，与要求重新进入初始状态相比，要求清空下推存储区是严格更严格的条件。获得了几种新的语言家族，它们构成了双链体系。推导了在AFL操作下这些族的封闭属性。线性语言的常规闭包具有上下文无关语言的强大闭包特性，即该族是完整的AFL。有趣的是，三个自然的新语言族在与常规语言相交和同态逆的情况下并没有封闭。最后，提出了一种算法，可以在二次时间内解析来自新族的语言。 0 2007 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号