上下文有关文法

✍ dations ◷ 2025-07-09 00:19:45 #上下文有关文法

上下文有关文法(CSG,英语:context-sensitive grammar)是一种形式文法,其中任何产生式规则的左手端和右手端都可以被终结符和非终结符构成的上下文所围绕。上下文有关文法比上下文无关文法更一般性,但仍足够有秩序得可以被线性有界自动机所解析。

上下文有关文法的概念是诺姆·乔姆斯基在1950年代介入的,被作为描述自然语言的语法的一种方式,在自然语言中一个单词是否可以出现在特定位置上,要依赖于上下文。可以被上下文有关文法描述的形式语言叫做上下文有关语言。

形式文法 = (, Σ, , ) 如果在 中所有的规则都有如下形式,则我们说它是上下文有关的

这里的 ∈ (就是 是单一非终结符),α,β ∈ ( U Σ)*(就是 α 和 β 是非终结符和终结符的字符串)而 γ ∈ ( U Σ)+(就是 γ 是非终结符和终结符的非空字符串)。

上下文有关文法的某些定义只要求,对于任何形如 u → v 的产生式规则,u 的长度应当小于或等于 v 的长度。这个看起来要弱些的要求,被断定为在实际上等价于上面的定义。

此外,还允许如下形式的规则

这里的 ε 表示空串,而 S 不出现在任何规则的右手端。增加空串允许声明:上下文有关语言是上下文无关语言的真超集,而不是作出弱一些的声明:没有 →ε产生式的所有上下文无关文法也是上下文有关文法。

上下文有关这个名称来源自 α 和 β 形成了 的上下文并且决定 是否可以被 γ 所替代。这不同于上下文无关文法,它不考虑非终结符的上下文。

如果把向语言增加空串的可能性增加到由不收缩文法所识别的那些字符串(永不包括空串的)中,则在这两种定义下的语言是相同的。

正规的非上下文无关语言 { a n b n c n : n 1 } {displaystyle {a^{n}b^{n}c^{n}:ngeq 1}} 拆分为 ();规则3到5允许随后将每个 对换位置为 (需要用3个规则,因为1个 → 规则,不能适合 αβ → αγβ 模式,即产生式左手端只有1个非终结符能被替换);规则6到9允许将在适当位置上的非终结符 或 分别替代为其对应的终结符 或 。

aaa bbb ccc 的产生链是:

{ a n b n c n d n : n 1 } {displaystyle {a^{n}b^{n}c^{n}d^{n}:ngeq 1}} 是否属于特定上下文有关文法 的语言的判定问题是 PSPACE-完全的。实际上,甚至有些上下文有关文法的固定文法识别问题也是 PSPACE-完全的。

上下文有关文法的空虚(emptiness)问题(给定上下文有关文法 G, L ( G ) = {displaystyle L(G)=emptyset } 吗?)是不可判定的。

已经证实几乎所有自然语言一般的都可以用上下文有关文法来刻画,但是整个 CSG 类好像比自然语言要大。更糟糕的是,因为上述 CSG 的判定问题是 PSPACE-完全的,这使得它们对于实际使用而言是完全不能运作的,因为一般算法将运行指数时间。关于计算语言学的当前进行中的研究关注于公式化是适度上下文有关语言的其他语言类,这种语言如树-邻接文法、组合范畴文法、连结上下文无关文法和线性上下文无关重写系统的判定问题是可行的。这些形式化所生成的语言适当的位于上下文无关和上下文有关语言之间。

相关

  • Hs5f14 6d6 7s2(预测)2, 8, 18, 32, 32, 14, 2(预测)第一:733.3(估值) kJ·mol−1 第二:1756.0(估值) kJ·mol−1 第三:2827.0(估值) kJ·mol−1 (主条目:
  • 1952年秋季朝鲜战争1952年秋季战役,中华人民共和国亦称“抗美援朝战争1952年秋季战术反击”或“抗美援朝战争1952年秋季反击作战”,是朝鲜战争中双方发生的战役。战役第一阶段为9月18日-1
  • 手越祐也手越祐也(1987年11月11日-),日本杰尼斯事务所旗下男子偶像组合NEWS及团体手越增田的成员。血型B型,身高168cm。 NEWS手越增田NEWS手越增田NEWSNEWS手越增田
  • 岱依族岱依族(越南语:người Tày/.mw-parser-output .han-nom{font-family:"Nom Na Tong","Han-Nom Gothic","Han-Nom Ming","HAN NOM A","HAN NOM B","Ming-Lt-HKSCS-UNI-H","Ming
  • 扎尔巴奇克火山托尔巴奇克火山是俄罗斯的火山,位于堪察加半岛,两个山峰海拔高度为3,682米和3,085米,山体由玄武岩组成,最近一次火山喷发在公元2012年11月底发生。
  • 地铁2033 (小说)《地铁2033》(俄语:Метро 2033)是由俄罗斯作家德米特里·格魯克夫斯基(Дми́трий Глухо́вский,Dmitry Glukhovsky)所著的一本科学幻想小说。小说讲述了在
  • 卓建荣卓建荣,中国男导演、制片人和编剧,同时也是厦门蓝火焰影视的董事长。他经营的厦门蓝火焰影视专门制作儿童动画作品;他曾在访谈时表示,现在的动画大多打打杀杀,这对儿童的影响不好
  • 克里门特·朱格拉克里门特·朱格拉(法语:Clément Juglar,又译克莱门·尤格拉,1819年10月15日-1905年2月28日)是一名法国医生和统计学家。朱格拉是最早提出商业周期经济学理论的人之一。他确定了以
  • 加悦悦和加盼盼加悦悦和加盼盼是2015年10月13日出生在多伦多动物园的双胞胎大猫熊,它们是首二只在加拿大出生的大猫熊。它们的母亲是二顺(英语:Er Shun),在2015年5月13日至14日期间,对它进行了两
  • 洪皓洪皓(1088年-1155年),字光弼,饶州鄱阳(今江西省鄱阳县古南乡)人,中国南宋著名的忠臣。宋哲宗元祐三年出生(1088年)。书无所不读,虽食不释卷,宋徽宗政和五年(1115年)进士,不久出任台州宁海县(今浙江省宁海)主簿,又升迁秀州(今浙江省嘉兴市)司录。建炎三年(1129年)知泗州(今江苏盱眙北)兼淮南、京东等路抚谕使,对付叛军李成。同年八月奉命赴金国至太原,滞留近一年,十二月被迁往云中(今山西省大同市)。绍兴元年(1131年),被金人流放到冷山(今黑龙江五常境内的大青顶子山),从云中至冷山走了六