无限制文法

✍ dations ◷ 2025-04-02 17:57:29 #无限制文法

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

无限制文法是形式文法 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} 是否属于某个无限制文法的语言的决定性问题一般是不可判定的。

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

相关

  • 武汉市金银潭医院武汉市金银潭医院是一家位于中华人民共和国湖北省武汉市东西湖区的一家公立医院,是武汉市卫生健康委员会直属单位,三级甲等专科医院。武汉市金银潭医院是湖北省和武汉市突发公
  • 王室颂歌颂歌是由英文的anthem翻译过来的,原本是指以英文写成的宗教性文章中的诗歌,后来衍生为有颂扬意思的歌曲,通常做为一群人的团体符号。如national anthem,意思为颂扬国家的歌曲,即
  • 藩侯藩侯(德语:Markgraf),另译边境伯,是神圣罗马帝国爵位的一种。藩侯的历史可追溯到查理曼时期。查理曼曾将一些边境的重要地区设立设立“马克(英语:March (territory))”(边区,德语:Mark),
  • 初岛坐标:35°2′23.41″N 139°10′14.47″E / 35.0398361°N 139.1706861°E / 35.0398361; 139.1706861初岛是位于日本伊豆半岛东方相模滩里的一座小岛,行政上隶属于静冈县热海
  • 1999年7月逝世人物列表1999年逝世人物列表:1月 - 2月 - 3月 - 4月 - 5月 - 6月 - 7月 - 8月 - 9月 - 10月 - 11月 - 12月下面是1999年7月逝世的知名人士列表:
  • 山杰·李拉·班沙里山杰·李拉·班沙里(英语:Sanjay Leela Bhansali,1963年2月24日-)是一名印度著名电影导演、编剧和制片人。他主要活跃于宝莱坞电影界,曾四度获得印度国家电影奖和十个印度电影观众
  • 大伴旅人大伴旅人(665年-731年,おおとも の たびと,Ōtomo no Tabito)是日本奈良时代初期的政治家、歌人。父亲是大伴安麻吕,母亲是巨势郎女。儿子中包括有名的大伴家持。一样知名的万叶歌
  • 刘名峯刘名峯,又名皮特,台湾MV导演,相信音乐演唱会部门必应创造影像导演。
  • 韩子勇韩子勇(1962年8月-),河南汝南人,中国作家,学者,现任中国艺术研究院院长、党委书记,中国非物质文化遗产保护中心主任,中央文史研究馆特约研究员。曾获第二届鲁迅文学奖全国优秀文学理论评论奖。
  • 章攀桂章攀桂(1736年-1804年),字淮树,安徽桐城人。乾隆年间,官甘肃知县,终官江苏松太兵备道。多才多艺,精于风水,“每为亲戚交友择地,贫者助之财以葬”。章攀桂曾为于敏中金坛里第营造花园。于敏中收受贿赂事发后,攀桂受到牵连,被革职。晚年居江宁,著有《选择正宗》。