鄂登引理

✍ dations ◷ 2025-01-12 06:52:06 #鄂登引理

在形式语言理论中，Ogden引理提供了在上下文无关语言的泵引理上灵活性的扩展。

Ogden 引理声称如果语言是上下文无关的，则存在某个数 > 0 (这里的可以是也可以不是抽吸长度)，使得对于中任何长度至少字符串，和“标记” 或更多个中的位置的所有方式，可以被写为

带有字符串 , , , 和，使得有至少一个标记了的位置，有最多个标记了的位置，而

Ogden 引理可以在上下文无关语言的泵引理不充分的情况下，被用来证明特定语言不是上下文无关的。一个例子是语言 ${displaystyle {a^{i}b^{j}c^{k}d^{l}:i=0 {text{或}} j=k=l}}$ ${displaystyle {a^{i}b^{j}c^{k}d^{l}:i=0 {text{或}} j=k=l}}$ 。

观察到在所有位置都被标记了的时候，这个引理等价于上下文无关语言的泵引理。

相关

深圳体育馆深圳体育馆位于深圳市福田区笋岗西路2006号，与深圳体育场、深圳游泳跳水馆和网羽中心同属于深圳市体育中心。1983年开始规划兴建，1985年底建成投入试运营，1987年竣工，但在竣工之
泰德·卡辛斯基西奥多·约翰·“泰德”·卡辛斯基（英语：Theodore John "Ted" Kaczynski，1942年5月22日－）。美国数学家、无政府主义者、国内恐怖主义者，绰号“大学航空炸弹客”（Unabomber）。为了对
1号阿肯色州州道1号阿肯色州州道（英语：Arkansas Highway 1，AR1，Ark. 1，Hwy. 1）是位于阿肯色州东部的一条南北走向的州级公路，长159.88英里（257.30千米），南起迪沙县麦吉接278号美国国道，北至密苏里州边
坎库里亚坎库里亚（Kankuria），是印度西孟加拉邦Murshidabad县的一个城镇。总人口27372（2001年）。该地2001年总人口27372人，其中男性13643人，女性13729人；0—6岁人口6256人，其中男3148人，女3108
醒吾科技大学醒吾学校财团法人醒吾科技大学（英语：Hsing Wu University），简称醒吾科大，是一所位于台湾地区新北市林口区的科技大学，由顾怀祖先生创立于1965年，原名为醒吾商业专科学校，2000年8月改
30秒上火星30秒上火星（英文：Thirty Seconds to Mars 或 30 Seconds to Mars）是一支来自美国加利福尼亚州洛杉矶，于1998年创立的摇滚乐队。乐队现成员包括兄弟杰瑞德·莱托(主唱、吉他、贝斯、键盘)与香农·莱托(鼓、打击乐器)。在其历史发展过程中，该乐队经历了一系列的成员变更。该乐队的首张专辑 (2002年)，由制作人Bob Ezrin参与制作并在发行后获得了相当正面的评价，但它在商业上的成就却很有限。通过释出第二张专辑 (2005年)，该乐队在世界范围拥有了名声。这张专辑
耶律迪烈耶律迪烈（1026年－1092年）或作耶律敌烈，字撒懒，辽朝宗室，为耶律吼五世孙。好学问，工于文章。重熙末年，补任牌印郎君、兼知起居注。清宁元年（1055年），同知永州事，镇压反乱有功，转任北面林牙承旨。清宁九年（1063年），耶律重元之乱，他参与平定叛乱，因功遥领临海军节度使。清宁十年（1064年），转任武安州观察使。咸雍五年（1069年），累进长宁宫使。管理户部司乾州钱帛负债，确立出纳方法，官民双方都称便益。太康四年（1078年），任南院大王。任期结束，部民要求留任，为同知南京留守事。生病后，皇帝命他
源文本源文本（英文：source text），又称为源语文本、原文本、原文、源语语篇、源文、源文文本等，是指信息、概念或思想所源自的文字（有时为口头形式）。在文字翻译领域，指所要翻译成其他语言的原始文字。
蔼姓《百家姓》中无此姓蔼姓，一个中文姓氏。《中国姓氏大全》（陈明远汪宗虎著）《百家姓》《钦定古今图书集成/明伦汇编/氏族典（页面存档备份，存于互联网档案馆）》
罗马尼亚历罗马尼亚自1919年起启用公历。但传统的罗马尼亚历法也有自己的月份名称。在现代的罗马尼亚与摩尔多瓦，公历在大众生活中具有主导地位。尽管如此，传统月份名称仍然在某些情况下使用，如罗马尼亚正教会制作的教会日历上。1919年4月14日，罗马尼亚王国启用公历，当天是旧历法的4月1日。2019年，罗马尼亚国家银行为庆祝罗马尼亚采用公历一百周年，发行了10列伊银币纪念币。所有月份的传统名称都源自拉丁语，这表明它们的使用早于8世纪左右的斯拉夫接触。在前十一个月份中，有六个的名称来源于月份的特征，五个的名称源自现在在公历