|
大小: 337
备注:
|
大小: 1212
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 1: | 行号 1: |
| 上下文无关文法： | 上下文无关文法：上下文无关文法G是一个四元组(V, ∑, R, S)，其中 V是一个字母表，∑是终结符集合，它是V的子集，R是规则集合，它是(V-∑)×V^*^的有穷子集， S∈V-∑是起始符。V-∑的成员叫做非终结符。 语法分析树： D先于D': 最左推导： 最右推导： 定理：设G=(V, ∑, R, S)是一个上下文无关文法，A∈V-∑及ω∈∑^*^，则下述命题是等价的： a. A=>ω a. 有一棵根为A、结果为ω的语法分析树 a. 有最左推导 a. 有最右推导 歧义性： |
| 行号 11: | 行号 29: |
| 定理：上下文无关语言在并、连接和Kleene星号下是封闭的。 定理：一个上下文无关语言与一个正则语言的交是一个上下文无关语言。 泵定理： 定理：上下文无关语言在交和补下不是封闭的。 |
上下文无关文法：上下文无关文法G是一个四元组(V, ∑, R, S)，其中 V是一个字母表，∑是终结符集合，它是V的子集，R是规则集合，它是(V-∑)×V*的有穷子集， S∈V-∑是起始符。V-∑的成员叫做非终结符。
语法分析树：
D先于D':
最左推导：
最右推导：
定理：设G=(V, ∑, R, S)是一个上下文无关文法，A∈V-∑及ω∈∑*，则下述命题是等价的：
A=>ω
有一棵根为A、结果为ω的语法分析树
- 有最左推导
- 有最右推导
歧义性：
下推自动机：
定理：下推自动机接受的语言正好是上下文无关语言。
引理：每一个上下文无关语言都被一台下推自动机接受。
引理：如果一个语言被一台下推自动机接受，则它是上下文无关语言。
定理：上下文无关语言在并、连接和Kleene星号下是封闭的。
定理：一个上下文无关语言与一个正则语言的交是一个上下文无关语言。
泵定理：
定理：上下文无关语言在交和补下不是封闭的。
确定型上下文无关语言：