...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On strongly context-free languages
【24h】

On strongly context-free languages

机译：使用无上下文的强语言

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

摘要

We investigate the context-free languages whose complements are also context-free. We call them strongly context-free languages. The family of strongly linear languages is similarly defined. After examining the closure properties of the family of strongly context-free languages, we prove that any slender context-free language is strongly linear. We then show that there are languages of a bounded complexity in terms of the number of non-terminals or productions necessary to generate them, whereas the complexity of their complements is arbitrarily large. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 18]
机译：我们研究了上下文无关的语言，它们的补充语也没有上下文。我们称它们为无上下文相关的语言。类似地定义了强线性语言族。在检查了强上下文无关语言家族的闭包特性之后，我们证明了任何细长的上下文无关语言都是强线性的。然后，我们表明，就生成非终止符或生成它们所必需的非终止词或生成词的数量而言，存在某种复杂性有限的语言，而其补语的复杂度则任意大。 （C）2000 Elsevier Science B.V.保留所有权利。 [参考：18]

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号