不收缩文法

✍ dations ◷ 2025-11-13 17:11:39 #不收缩文法

在形式语言理论中,文法是不收缩的(或单调的),如果所有它的产生规则都有如下形式

就是说,没有规则会减少被重写的字符串的大小。

它是本质不收缩的,如果可有一个例外,也就是,规则

这里的 S 是开始符号而 ε 是空串。

这个文法生成语言 { a n b n c n : n 1 } {displaystyle {a^{n}b^{n}c^{n}:ngeq 1}} ,它不是上下文无关的。

还有给语言 { a n b n c n d n : n 1 } {displaystyle {a^{n}b^{n}c^{n}d^{n}:ngeq 1}} 的(更加复杂)的不收缩文法。

有容易的过程把任何不收缩文法转换成 Kuroda范式。

已知把任何不收缩文法变换成上下文有关文法或反之的过程。

所以,不收缩文法,Kuroda 范式的文法,和上下文有关文法有同样的表达能力。

更精确地说,不收缩文法精确的描述不包含空串的上下文有关语言,而本质不收缩文法精确的描述上下文有关语言的集合。

相关

  • 薄透镜薄透镜,在光学中,是指透镜的厚度(穿过光轴的两个镜子表面的距离)与焦距的长度比较时,可以被忽略不计的透镜。厚度不能被忽略的透镜称为厚透镜。薄透镜有两个球面组成,第一曲面的曲
  • 苏格兰电视台苏格兰电视台(STV)是苏格兰的一家电视台。苏格兰电视台现在持有两张独立电视台(ITV)的执照,分别是苏格兰北部和中部的执照,之前这两种执照分别由格兰扁电视台(Grampian Television,
  • 农业机械化农业机械化是指运用先进适用的农业机械装备农业,改善农业生产经营条件,不断提高农业的生产技术水准和经济效益、生态效益的过程。指在农业中能模仿人的某种活动,具备特定生产技
  • 爱知县第14区爱知县第14区是日本众议院的选区,设立于1994年。北海道 13 | 山形县 4 | 静冈县 9 | 岛根县 3 | 大分县 4福井县 3 | 山梨县 3 | 德岛县 3 | 高知县 3 | 佐贺县 3青森县 4 |
  • 艺术监督艺术监督(英语:Artistic directors)是在艺术组织中担任执行者的职位,负责管理该组织的相关艺术工作。在芭蕾舞中,艺术监督是负责人的职位,必须训练舞者和节目制作。多数是退休的舞
  • 黄金计程车《黄金计程车》(英语:)是东森综合台首播的益智节目,是由赵正平、梁赫群、郭书瑶(瑶瑶)共同主持,2009年4月22日开播,首播时间为台湾时间每星期三22时。2009年6月瑶瑶约满离开,因此于20
  • 秦河胜秦河胜(日语:秦 河勝/はた の かわかつ ),生卒年不详,飞鸟时代日本秦氏领袖,冠位为大花上。他是飞鸟时代人物,是圣德太子宠臣。他负责建设广隆寺,他本来是官奴后来负责管理财政。他
  • 王琎 (明朝)王琎(?-?),字器之,山东行省青州府莒州日照县(今山东省日照市)人,明朝政治人物。洪武年间,担任教授,后因坐事谪远方。末年,因举荐授任宁波知府。率领宁波学生四更起读书,并摧毁境内淫祠,生
  • 桃子岭站桃子岭站是位于湖北宜都市桃子岭村的一个铁路车站,邮政编码443313。车站建于1978年,有焦柳铁路经过该站,现仅办理货运业务,不办理客运业务。车站距离月山站764公里,隶属武汉铁路
  • 1910-1911年东北鼠疫1910-1911年东北鼠疫是发生在1910年10月末至1911年4月中旬的清朝的一场鼠疫,属于人类历史上第三次鼠疫大流行的重大疫情,这次鼠疫波及69个县,共死亡6万余人。东北鼠疫来源于患有鼠疫的土拨鼠。1910年夏,俄罗斯帝国境内西伯利亚出现由土拨鼠(旱獭属)引发的鼠疫,而此时有华工前往西伯利亚捕杀土拨鼠制作皮毛。1910年9月16日,在俄罗斯帝国的达乌里亚发现了首例患者。10月初数名华工染病身亡,俄方于是驱逐染疫华工,其中两名被逐华工到了满洲里。1910年10月25日,满洲里一家客栈爆发鼠疫并出现死亡