无限制文法

✍ dations ◷ 2025-04-04 11:18:35 #无限制文法

在形式语言理论中,无限制文法是对文法的产生式左右两侧都没有限制的形式文法。这是乔姆斯基层级中最一般性的文法类,它们可以识别任意的递归可枚举语言。

无限制文法是形式文法 G = ( N , Σ , P , S ) {displaystyle G=(N,Sigma ,P,S)} ,这里的 N {displaystyle N} 是非终结符的集合, Σ {displaystyle Sigma } 是终结符的集合,这里的 N {displaystyle N} Σ {displaystyle Sigma } 是无交集的(实际上这个限制不是必需的,因为无限制文法在非终结符和终结符之间不做真实区分,存在这个指定纯粹是为了使得你在尝试生成文法的句子形式的时候知道何时停止), P {displaystyle P} 是形如 α β {displaystyle alpha to beta } 的产生规则的集合,这里的 α {displaystyle alpha } β {displaystyle beta } 是在 N Σ {displaystyle Ncup Sigma } 中的符号的字符串而 α {displaystyle alpha } 是非空字符串, S N {displaystyle Sin N} 是特别指定的开始符号。如名称所暗含的,在无限制文法可以有什么类型的产生规则上没有真实限制。

可以证明无限制文法特征化了递归可枚举语言。这同于声称对于所有无限制文法 G {displaystyle G} 都存在某个图灵机有能力识别 L ( G ) {displaystyle L(G)} 反之亦然。给定一个无限制文法,这种图灵机足够简单构造为两磁带非确定图灵机。第一个磁带包含要被测试的输入字 w {displaystyle w} ,而机器使用第二个磁带生成来自 G {displaystyle G} 的句子形式。图灵机接着做如下事情:

容易看出这个图灵机将在最后步骤被执行任意次之后在第二个磁带上生成 G {displaystyle G} 的所有的句子形式,所以语言 L ( G ) {displaystyle L(G)} 必定是递归可枚举的。

相反构造也是可能的。给定某个图灵机,有可能建立一个无限制文法。

从无限制文法和图灵机的等价性上,给定一个字符串 s {displaystyle s} 是否属于某个无限制文法的语言的决定性问题一般是不可判定的。

给出一个语言的描述完全可能建立一个通用无限制文法有能力接受任何其他无限制文法的语言,如同有可能建立一个通用图灵机,所以在理论上有可能建造一个基于无限制文法的编程语言。

相关

  • 细胞焦亡细胞焦亡是一种细胞程序性死亡方式,是生物体的一种天然免疫反应。细胞不断胀大直至细胞膜破裂,释放大量的促炎症因子进而激发其他免疫细胞抵抗感染并导致组织炎症。细胞焦亡通
  • 航天科学name = 'Aero', description = '航空太空科技(航空航天科技)', content = {{ type = 'text', text = [=[本页面没有类似于NoteTA的数量限制。 请自行修改分类名。在NoteTA样板
  • 同性恋欺凌男同性恋欺凌(Gay bashing),或称男同性恋霸凌(Gay bullying),指的是对于男同性恋者群体进行口语或肢体方面的欺凌行为,但也能泛指对女同性恋、双性恋或跨性别者者。它可以作为名词,
  • 山东能源山东能源集团有限公司,简称山东能源集团(英语:Shandong Energy Group Company Limited),是山东省人民政府国有资产监督管理委员会监管的大型国有矿业集团,即山东省省管企业。于201
  • 尼克·达金尼克·达金(Nic Dakin,1955年7月10日-)是一位英格兰政治人物,他的党籍是工党。自2010年开始,他担任斯肯索普选区选出的英国下议院议员。他在2015年就任影子内阁的学校大臣。
  • 守夜人国家守夜人国家(night-watchman state)是一种国家形式,其以小政府为特点。在守夜人国家,政府的唯一角色就是透过军队、警察、法院来确保每位公民皆在遵守互不侵犯原则,以让他们免受侵
  • 山形健山形健(1978年—),是日本AV男优,出生于茨城县,于2011年引退。因相貌类似中国主持人毕福剑而受到中国网民的注意。山形健酷似中国大陆主持人毕福剑,因此他和长相酷似周杰伦的东尼大
  • 四川苏铁四川苏铁(学名:),又称南盘江苏铁、贵州苏铁,为苏铁科苏铁属的植物,是中国的特有植物。分布在中国大陆的四川峨眉山、雅安、乐山及福建南平等地,常生长在山谷溪边,目前尚未由人工引种
  • Hemiperfect数Hemiperfect数(hemiperfect number)是指一正整数的过剩指数为奇数除以2,过剩指数(abundancy index)就是除数函数(包括本身的所有正因数和)除以正整数后的结果。针对一大于2的奇数 ,
  • 1455年