乔姆斯基范式

✍ dations ◷ 2025-07-17 10:20:32 #乔姆斯基范式

在计算机科学中,一个形式文法是 Chomsky 范式的,当且仅当所有产生规则都有如下形式:

这里的 , 和 是非终结符,α 是终结符(表示常量值的符号), 是开始符号,而 ε 是空串。还有, 和 都不可以是开始符号。

所有的 Chomsky 范式的文法都是上下文无关,反过来,所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。

除了(在文法可能生成空串的时候包括的)可选规则 → ε 是例外,Chomsky 范式的文法的所有规则都是扩张的,就是说在字符串的整个导出过程中,每个终结符和非终结符的字符串比起前面导出的字符串要么同样长度要么多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。

Chomsky 范式得名于诺姆·乔姆斯基,他是发明乔姆斯基层级的美国语言学家。

进一步的,因为导出非终结符的所有规则都把一个非终结符变换成两个非终结符,基于 Chomsky 范式的文法上的一个分析树是二叉树,而这个树的高度被限制于最高为这个字符串的长度。

由于这些性质,在语言和可计算性领域中很多证明采用了 Chomsky 范式。这些性质还产生了基于 Chomsky 范式的文法的各种有效算法;例如,判定给定字符串是否可以被使用 Chomsky 范式的给定文法生成的 CYK算法。

某些来源以稍微不同的方式来定义 Chomsky 范式:

一个形式文法是 Chomsky 范式的,当且仅当所有产生规则都有如下形式:

这里的 , 和 是非终结符,而 α 是终结符。当使用这个定义的时候, 和 不能是开始符号。

这个定义不同于前面定义的是它排除了文法生成空串 ε 的可能性。接受一个语言 的任何上下文无关文法都可以有效的变换成接受 的 Chomsky 范式的文法。后者定义的首要好处是证明通常更简单,由于在导出过程中每个步骤都永不减少结果字符串的长度。当然它的缺点是在最初文法生成 ε 就需要特殊考虑。

相关

  • 裕陵清裕陵(满语:ᡨᠣᠮᠣᡥᠣᠩᡤᠣᠮᡠᠩᡤᠠᠨ,穆麟德:tomohonggo munggan)是清朝入关后第四位皇帝清高宗弘历(乾隆帝)与孝贤纯皇后、孝仪纯皇后、慧贤皇贵妃、哲悯皇贵妃、淑嘉皇贵
  • 卢斯阿莱尔塞斯国家公园坐标:42°48′27″S 71°53′56″W / 42.80750°S 71.89889°W / -42.80750; -71.89889卢斯阿莱尔塞斯国家公园是阿根廷的国家公园,位于该国中部,由丘布特省负责管辖,面积2,630
  • 克喇末-克勒尼希关系克喇末-克勒尼希关系式(英语:Kramers–Kronig relations)是数学上连系复面上半可析函数实数部和虚数部的公式。此关系式常用于物理系统的线性反应函数。物理上因果关系(系统反应
  • 阿波罗-联盟测试计划阿波罗-联盟测试计划(英语:Apollo-Soyuz Test Project (ASTP);俄语:Экспериментальный полёт «Союз-Аполлон» (ЭПСА))是历史上第一次由
  • 伊朗选举伊朗政府与政治 系列条目伊朗选举在中央上包括国家元首和政府首脑(即总统),立法机构(即议会)和“专家会议”(由专家会议选出最高领袖)。同时,全国的城乡议会每四年选举一次。总统每
  • 帕莱拉帕莱拉(Palera),是印度中央邦Tikamgarh县的一个城镇。总人口14646(2001年)。该地2001年总人口14646人,其中男性7760人,女性6886人;0—6岁人口2724人,其中男1432人,女1292人;识字率51.88
  • 马杜普尔马杜普尔(Madhupur),是印度贾坎德邦Deoghar县的一个城镇。总人口47349(2001年)。该地2001年总人口47349人,其中男性25235人,女性22114人;0—6岁人口7507人,其中男3901人,女3606人;识字
  • 打雪仗打雪仗是少年在雪中或雪后的一种娱乐方式。打雪仗所需的场地是一片有足够积雪的区域。打雪仗的过程中,参与者将雪制成雪球,抛向对方,也有将用手捧起一把雪近距离攻击。打雪仗的
  • 不可触碰 (1993年电视剧)《不可触碰》(英语:),又译《铁面无私》,是一部美国犯罪电视剧,播放日期是1993年1月至1994年5月,共有2季。本剧描述禁酒时期芝加哥的真实联邦调查小组“铁面无私(英语:Untouchables (l
  • 黎明监狱两逃犯越狱事件黎明监狱两逃犯越狱事件是2010年发生在哈尔滨市的一场越狱事件。越狱者为陈聪聪和孙星辰。这起事件自2010年2月23日算起,至3月8日陈聪聪被抓获为止,共计13天。首先,陈聪聪与孙星辰在2月23日越狱后,先后经过电碳路和信义村,之后孙陈二人在2月23日至25日间在科大小区租住,并在2月25日于大发市场逃亡;其时,两人多次在哈西服装城购物;随后二人分手。其中,孙星辰准备逃往双城,但在2月26日于金星收费站被抓获。而陈聪聪则从2月26日到3月4日一直藏身白家堡;之后他3月4、5日晚藏身欧亚之窗,5、6日则在龙