48
备注:
|
602
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 1: | 行号 1: |
上下文无关文法: | 上下文无关文法:上下文无关文法G是一个四元组(V, ∑, R, S),其中 V是一个字母表,∑是终结符集合,它是V的子集,R是规则集合,它是(V-∑)×V^*^的有穷子集, S∈V-∑是起始符。V-∑的成员叫做非终结符。 |
行号 4: | 行号 6: |
定理:下推自动机接受的语言正好是上下文无关语言。 引理:每一个上下文无关语言都被一台下推自动机接受。 引理:如果一个语言被一台下推自动机接受,则它是上下文无关语言。 确定型上下文无关语言: |
上下文无关文法:上下文无关文法G是一个四元组(V, ∑, R, S),其中 V是一个字母表,∑是终结符集合,它是V的子集,R是规则集合,它是(V-∑)×V*的有穷子集, S∈V-∑是起始符。V-∑的成员叫做非终结符。
下推自动机:
定理:下推自动机接受的语言正好是上下文无关语言。
引理:每一个上下文无关语言都被一台下推自动机接受。
引理:如果一个语言被一台下推自动机接受,则它是上下文无关语言。
确定型上下文无关语言: