形式化3：NP问题的概念及上下文无关文法

文法"/>

形式化3：NP问题的概念及上下文无关文法

NP问题

指的是如果要求问题的解，时间复杂度至少为 O ( 2 n ) O(2^n) O(2n)，而验证解的时间复杂度仅为 O ( n k ) O(n^k) O(nk)这一类的问题。（求解难，验证易）

上下文无关文法

乔姆斯基文法体系

乔姆斯基起初为研究自然语言而构造了一系列数学工具，但其最终却广泛应用于计算机程序语言

[[[[正则表达式]上下文无关文法]上下文有关文法]任意文法]

从内向外文法的表达能力越来越强，其中正则表达式应用于词法，无关文法应用于程序语言的语法规则，有关文法和任意文法在计算机中未得到广泛应用。

定义

上下文无关文法G是一个四元组：

G = ( T , N , P , S ) G=(T,N,P,S) G=(T,N,P,S)

• T T T：终结符集合，本课中都用小写符号表示
• N N N：非终结符集合，本课中都用大写符号表示
• P P P：一组产生式规则，每条规则形式为： X → β 1 β 2 . . . β n , X ∈ N , β i ∈ ( T ⋃ N ) X \rightarrow \beta_1 \beta_2...\beta_n,\ X \in N,\ \beta_i \in (T \bigcup N) X→β1​β2​...βn​, X∈N, βi​∈(T⋃N)
• S S S：唯一的开始符号（非终结符），它总是产生式规则的第一个非终结符。 S ∈ N S \in N S∈N

例如一句话要求的结构为【主语，谓语，宾语】

G = (N, T, P, S)        // 非终结符，终结符，产生式规则，开始
N = (S, N, V)           // 开始, 名词, 动词
T = (s, t, g, w, e, d)  // sheep，tiger，grass，water，eat，drink
P = X -> N V N          // 名词 动词 名词产生式规则展开如下
S -> N V N
N -> s| t| g| w
V -> e| d

由于以上大小写字符的区分，和开始符号的位置规定，仅通过产生式规则我们就可以确定 N T P S N\ T\ P\ S N T P S四个集合

推导

给定文法G，从G的开始符号S开始，用产生式的右部替换左侧的非终结符，此过程不断重复，直到不出现非终结符为止。最终的串称为句子。

• 最左推导：每次总是选择最左侧的符号进行替换
• 最右推导：每次总是选择最右侧的符号进行替换