上下文无关文法的定义

Question

如题所述

Answer 1

上下文无关文法的定义具体如下：

一、简述

1、在计算机科学中，形式语言是：某个字母表上，一些有限长字串的集合，而形式文法是描述这个集合的一种方法。形式文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故。

2、形式文法描述形式语言的基本想法是，从一个特殊的初始符号出发，不断的应用一些产生式规则，从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。

3、最常见的文法的分类系统是诺姆·乔姆斯基于1956年发展的乔姆斯基谱系，这个分类谱系把所有的文法分成四种类型：无限制文法、上下文相关文法、上下文无关文法和正规文法。四类文法对应的语言类分别是递归可枚举语言、上下文相关语言、上下文无关语言和正规语言。

二、详细情况

1、上下文无关文法（英语：context-free grammar，缩写为CFG），在计算机科学中，若一个形式文法G=(N,Σ,P,S)的产生式规则都取如下的形式：V->w，则谓之。其中V∈N，w∈(N∪Σ)*。

2、上下文无关文法取名为“上下文无关”的原因就是因为字符V总可以被字串w自由替换，而无需考虑字符V出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的（条目上下文无关语言）。

3、上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串。