Mixing
上下文无关语言
上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。
目录
1 例子
2 闭包性质
2.1 在交集下不闭包
3 可判定性性质
4 上下文无关语言的性质
5 引用
例子
一个原型上下文无关语言是 L={anbn:n≥1}{displaystyle L={a^{n}b^{n}:ngeq 1}}
δ(q0,a,z)=(q0,a){displaystyle delta (q_{0},a,z)=(q_{0},a)}
δ(q0,a,a)=(q0,a){displaystyle delta (q_{0},a,a)=(q_{0},a)}
δ(q0,b,a)=(q1,x){displaystyle delta (q_{0},b,a)=(q_{1},x)}
δ(q1,b,a)=(q1,x){displaystyle delta (q_{1},b,a)=(q_{1},x)}
δ(q1,b,z)=(qf,z){displaystyle delta (q_{1},b,z)=(q_{f},z)}
- 这里的 z 是初始栈符号而 x 意味着弹出动作。
上下文无关语言在编程语言中有很多应用。大多数算术表达式可用上下文无关文法生成。
闭包性质
上下文无关语言闭合于下列运算下。就是说，如果 L 和 P 是上下文无关语言而 D 是正则语言，下列语言也是上下文无关语言：
L 的 Kleene星号 L∗{displaystyle L^{*}}
L 在字符串同态 φ 下的像 φ(L)
L 和 P 的串接 L∘P{displaystyle Lcirc P}
L 和 P 的并集 L∪P{displaystyle Lcup P}
L 和（正则语言）D 的交集 L∩D{displaystyle Lcap D}
上下文无关语言不闭合于补集，交集或差集下。
在交集下不闭包
上下文无关语言不闭合于交集下。其证明在 Sipser 97 中被作为习题给出。选用语言 A={ambncn∣m,n≥0}{displaystyle A={a^{m}b^{n}c^{n}mid m,ngeq 0}}
可判定性性质
上下文无关语言的下列问题是不可判定的：
- 等价：给定两个上下文无关文法 A 和 B，L(A)=L(B){displaystyle L(A)=L(B)}
吗？
L(A)∩L(B)=∅{displaystyle L(A)cap L(B)=emptyset }吗？
L(A)=Σ∗{displaystyle L(A)=Sigma ^{*}}吗？
L(A)⊆L(B){displaystyle L(A)subseteq L(B)}吗？
上下文无关语言的下列问题是可判定的：
L(A)=∅{displaystyle L(A)=emptyset }吗？
- L(A) 是有限的吗？
- 成员关系：给定任何字 w，w∈L(A){displaystyle win L(A)}
吗？（成员关系问题甚至是多项式可判定的 - 参见CYK算法）
上下文无关语言的性质
- 上下文无关语言的反转（reverse）也是上下文无关的，但是补（complement）不必须是。
- 所有正则语言都是上下文无关的，因为它们可以用正则文法描述。
- 存在不是上下文无关的上下文有关语言。
- 要证明给定语言不是上下无关的，可以采用上下文无关语言的泵引理。
引用
Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X. Chapter 2: Context-Free Languages, pp.91–122.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Comments
Post a Comment