格雷巴赫标准式

✍ dations ◷ 2025-08-22 11:50:58 #格雷巴赫标准式

在计算机科学中,声称一个上下文无关文法是Greibach 标准式(范式)(GNF)的意味着所有的产生规则都有如下形式:

这里的 是非终结符,α 是终结符, 是不包括开始符号的非终结符的(可能为空)的序列, 是开始符号,而 是空串。

可观察出这种文法没有左递归。

所有上下文无关文法口可以被转换成等价的 Greibach 范式的文法。(某些定义不认可第二种形式的规则,在这种情况下能生成空串的上下文无关文法不能被如此转换。)这可以被用来证明所有上下文无关语言可以被非确定下推自动机所接受。

给定 GNF 的一个文法和长度为 的符合这个文法的一个可导出的字符串,任何自顶向下分析器将在深度 停机。

Greibach 范式得名于 Sheila Greibach。

请写出

的 Greibach 标准式


A¹→A²A²|0 A²→A¹A¹|1

A¹→A²A²|0 A²→A²A²A¹|0A¹|1

A¹→A²A²|0 A²→0A¹|1|0A¹B²|1B²B²→A²A¹|A²A¹B²

A¹→0A¹A²|1A²|0A¹B²A²|1B²A²|0A²→0A¹|1|0A¹B²|1B²B²→A²A¹|A²A¹B²

A¹→0A¹A²|1A²|0A¹B²A²|1B²A²|0A²→0A¹|1|0A¹B²1B²B²→0A¹A¹|0A¹B²A¹|1B²A¹|0A¹A¹B²|0A¹B²A¹B²|1B²A¹B²|1A¹|1A¹B²

相关

  • 食腐动物食腐动物是指主要靠进食腐肉维生的动物。如秃鹫、秃鹳、鬣狗、狼獾、豺等。 事实上绝大部分肉食性动物,都会在捕食的同时食腐(如狮子、科莫多龙)。另外亦有以腐木、腐植质维生
  • 临床免疫学人体解剖学 - 人体生理学 组织学 - 胚胎学 人体寄生虫学 - 免疫学 病理学 - 病理生理学 细胞学 - 营养学 流行病学 - 药理学 - 毒理学免疫学(英语:Immunology)是生物医学的一
  • 深圳研究院南开大学深圳研究院,简称南开大学深研院,于2000年8月成立,位于深圳市南山区科苑南路深圳虚拟大学园内。
  • 乌尔都文U+0600—U+06FF U+0750—U+077F U+FB50—U+FDFF乌尔都字母是用于乌尔都语的从右至左书写的字母。它是对演化自阿拉伯字母的波斯字母的修改。共有 38 个字母,乌尔都字母通常用
  • 校园暴力校园欺凌(英语:School bullying),又称校园暴力,指的是一种长时间持续的、并对个人在心理造成恐惧、身体和言语遭受恶意的攻击,且因为受害者与欺凌者之间的权力或体型等因素不对等,
  • 世界难民日每年6月20日,是世界难民日(La Journée mondiale des réfugiés / World Refugee Day)。世界难民日是联合国难民署(UNHCR)确定的一项纪念日。起初,它是非洲独有的纪念日(原名“非
  • 恽日初恽日初(?-?),字仲升,号逊菴,又号黍菴。武进人。著名画家恽寿平之父。崇祯癸酉(1633年)副榜,为复社士人,崇祯十六年(1643年)应诏上〈备边五策〉,不报。有民族气节。明亡后隐居天台山,组织武装
  • 怀俄明级战列舰怀俄明级战列舰是美国海军建造的一级无畏舰。该级的怀俄明号战列舰和阿肯色号战列舰均于1909年批准建造,1910年开工,1912年完工。怀俄明级是美国海军的第四级无畏舰,也是最后一级采用12英寸(305毫米)舰炮的战列舰。相比前型佛罗里达级战列舰(英语:Florida-class battleship),怀俄明级增加了一座双联装炮塔并改进了装甲。此外,怀俄明级还首次采用了防鱼雷隔舱。美国海军曾考虑配备14英寸(356毫米)舰炮,但由于担心延期交付、战舰排水量过大等问题而最终放弃。20世纪10年代初,怀俄明号
  • 李昕融 (歌手)李昕融(2010年3月26日-),中国大陆女歌手、出生于北京市、代表作有《你笑起来真好看》、《听我说谢谢你》、《把未来点亮》等。李昕融的父亲为李凯稠,是一位作曲家,母亲樊桐舟曾为演唱团体黑鸭子成员,所以李昕融很早就开始接触音乐。2013年,3岁的李昕融即发行首支单曲《宝贝宝贝》。从2017年起,李昕融开始亮相央视,并陆续发布了多首个人单曲。
  • 刘台拱刘台拱(1751年-1805年),字端临、一字江岭、一字子阶,江苏宝应人,清代学者。乾隆十六年(1751年)出生,幼不好戏,六岁时母朱氏卒,十五岁从乡里王雒学,见王予中、朱正泉书,遂笃志程朱之学,以《三礼》尤精研之。乾隆三十六年(1771年)江南乡试第八十九名。屡赴会试不第。端临早年居扬州时,与汪中、朱彬友善。在京期间,与京城重要学者如戴震、翁方纲、邵晋涵、程瑶田、王念孙等交游论学,“每发一义,诸老先生莫不折服,以为好学深思知其义者,莫先生若也”,从此扬名。后任镇江丹徒县训导,十七年身奉此职,未再迁官。嘉