565
备注:
|
1878
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 1: | 行号 1: |
上下文无关文法:上下文无关文法G是一个四元组(V, ∑, R, S),其中 V是一个字母表,∑是终结符集合,它是V的子集,R是规则集合,它是(V-∑)×V^*^的有穷子集, S∈V-∑是起始符。 |
定义:上下文无关文法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-∑及ω∈∑^*^,则下述命题是等价的: a. A=>ω a. 有一棵根为A、结果为ω的语法分析树 a. 有最左推导 a. 有最右推导 歧义性: |
行号 13: | 行号 33: |
定理:上下文无关语言在并、连接和Kleene星号下是封闭的。 定理:一个上下文无关语言与一个正则语言的交是一个上下文无关语言。 泵定理: 定理:上下文无关语言在交和补下不是封闭的。 定理:(1)有多项式算法,任给一个上下文无关文法,构造一台等价的下推自动机。 (2)有多项式算法,任给一台下推自动机,构造一个等价的上下文无关文法。 (3)有多项式算法,任给一台上下文无关文法G和一个字符串x,判断是否x∈L(G)。 |
|
行号 14: | 行号 46: |
定理:确定型上下文无关语言类在补运算下是封闭的。 死结束: 推论:确定型上下文无关语言类是上下文无关语言类的真子集。(就下推自动机而言,非确定性比确定性更有力。) |
定义:上下文无关文法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-∑及ω∈∑*,则下述命题是等价的:
A=>ω
有一棵根为A、结果为ω的语法分析树
- 有最左推导
- 有最右推导
歧义性:
下推自动机:
定理:下推自动机接受的语言正好是上下文无关语言。
引理:每一个上下文无关语言都被一台下推自动机接受。
引理:如果一个语言被一台下推自动机接受,则它是上下文无关语言。
定理:上下文无关语言在并、连接和Kleene星号下是封闭的。
定理:一个上下文无关语言与一个正则语言的交是一个上下文无关语言。
泵定理:
定理:上下文无关语言在交和补下不是封闭的。
定理:(1)有多项式算法,任给一个上下文无关文法,构造一台等价的下推自动机。 (2)有多项式算法,任给一台下推自动机,构造一个等价的上下文无关文法。 (3)有多项式算法,任给一台上下文无关文法G和一个字符串x,判断是否x∈L(G)。
确定型上下文无关语言:
定理:确定型上下文无关语言类在补运算下是封闭的。
死结束:
推论:确定型上下文无关语言类是上下文无关语言类的真子集。(就下推自动机而言,非确定性比确定性更有力。)