上下文无关语言

定义：上下文无关文法G是一个四元组$(V, \Sigma, R, S)$，其中

• V是一个字母表，
• $\Sigma$是终结符集合，它是V的子集，($V-\Sigma$的成员叫做非终结符)
• R是规则集合，它是$(V-\Sigma)\times V^*$的有穷子集，
• $S\in V-\Sigma$是起始符。

G生成的语言$L(G)$为$\lbrace \omega\in\Sigma^*:S\omega \rbrace$

语法分析树：

D先于D':

最左推导：

最右推导：

定理：设G=(V, ∑, R, S)是一个上下文无关文法，A∈V-∑及ω∈∑^*，则下述命题是等价的：

1. A=>ω

2. 有一棵根为A、结果为ω的语法分析树

3. 有最左推导
4. 有最右推导

歧义性：

下推自动机：

定理：下推自动机接受的语言正好是上下文无关语言。

引理：每一个上下文无关语言都被一台下推自动机接受。

引理：如果一个语言被一台下推自动机接受，则它是上下文无关语言。

定理：上下文无关语言在并、连接和Kleene星号下是封闭的。

定理：一个上下文无关语言与一个正则语言的交是一个上下文无关语言。

泵定理：

定理：上下文无关语言在交和补下不是封闭的。

定理：（1）有多项式算法，任给一个上下文无关文法，构造一台等价的下推自动机。 （2）有多项式算法，任给一台下推自动机，构造一个等价的上下文无关文法。 （3）有多项式算法，任给一台上下文无关文法G和一个字符串x，判断是否x∈L(G)。

确定型上下文无关语言：

定理：确定型上下文无关语言类在补运算下是封闭的。

死结束：

推论：确定型上下文无关语言类是上下文无关语言类的真子集。（就下推自动机而言，非确定性比确定性更有力。）