句子终极符号行，它不含语法变量
句型符号行，它可能含有语法变量
G=(V，T，P，S)，对于α∈(V∪T)*，如果S→* α，则称α是G产生的一个句型。
文法G=(V，T，P，S)。任意A∈V表示集合L(A)={w | w∈T*且A →* w}。 推导与归约。文法中的推导是根据文法的产生式进行的。如果α→β∈P，γ，δ∈(V∪T)*，则称γαδ在G中直接推导出γβδ：γαδG γβδ；也称γβδ在文法G中直接归约成γαδ。
对任意的x，y∈∑+，我们要使语法范畴D代表的集合为{xnyn|n≥1}，可用产生式组{D→xy|xDy}来实现。
设有两个文法G1和G2，如果L(G1)= L(G2)，则称G1与G2等价。
例文法G：S→abc | aSbc产生的语言为：{an(bc)n | n≥1}
线性文法(liner grammar)
设G=(V，T，P，S)，如果对于α→β∈P，αβ均具有如下形式：
A→w A→wBx
其中A，B∈V，w，x∈T*，则称G为线性文法。
G14：S→aBC | aSBC，
CB→BC
aB→ab
bB→bb
bC→bc
cC→cc
如果对于α→β∈P，均有|β|≥|α|成立，则称G为1型文法或上下文有关文法CSG)。
如果对于α→β∈P，均有|β|≥|α|，并且α∈V成立，则称G为2型文法，或上下文无关文法CFG)。
如果对于α→β∈P，αβ均具有形式A→w ,A→wB,其中A，B∈V，w∈T+。RG)
FA) M=(Q，∑，δ，q0，F)L(M)={x| x∈∑*且δ(q，w)∈F}
NFAL(M)={x| x∈∑*且δ(q0，w) ∩ F≠Φ}，
设DFA M=(Q，∑，δ，q0，F)
例 5-3 证明{0n1m2n+m|m，n≥1}不是 RL。
证明：假设L={0n1m2n+m|m，n≥1} 是 RL。
取z=0N1N22N
设 v=0k k≥1
从而有，
uviw=0N-k-j(0k)i0j1N22N
=0N+(i-1)k1N22N
uv0w=0N+(0-1)k1N22N
= 0N-k1N22N
注意到k≥1，
N-k+N=2N-k<2N
0N-k1N22N L
这个结论与泵引理矛盾。所以，L不是 RL。
设R是∑*上的等价关系，对于x，y∈∑*，如果x RL y，则必有xz RL yz对于z∈∑*成立，则称R是右不变的等价关系。
对于任意X∈V∪T，如果X是有用的，它必须同时满足如下两个条件：
① 存在w∈T*，使得X→*w；
② α，β∈(V∪T)*，使得S→*αXβ。
CNF乔姆斯基范式文法:CFG G=(V，T，P，S)中的产生式形式：A→BC，A→a,其中，A、B、C∈V，a∈T。不允许有ε-产生式、单一产生式。
对于任意CFG G，ε→L(G)，存在等价的 CNF→G2
格雷巴赫范式文法GNF:A→aα ,其中，A∈V，a∈T，α∈V* 。在GNF中，有如下两种形式的产生式A→a;
A→aA1A2…Am (m≥1)
推自动机PDA);M= (Q，∑，Γ，δ，q0，Z0，F) ID) (q，w，γ)∈(Q，∑*，Γ*)称为M的一个即时描述。
如果(p，γ)∈δ(q，a，Z)，a∈∑，则(q，aw，Zβ)├M(p，w，γβ)表示M做一次非空移动，从ID(q，aw，Zβ)变成ID(p，w，γβ)。
L(M)={w | (q0，w，Z0)├*(p，ε，β)且 p∈F}
M用空栈接受的语言
N(M) ={w | (q0，w，Z0)├*(p，ε，ε)}
对于任意CFL L，存在PDA M，使得N(M)=L。
能引导FA从开始状态到达q的字符串的集合为：set(q)={x | x∈∑*，δ(q0，x)=q}
定理5-1 (鼻渊散Myhill-Nerode定理)如下三个命题等价：
⑴ L∑*是 RL ；
⑵ L是∑*上的某一个具有有穷指数的右不变等价关系R的某些等价类的并；
⑶ RL具有有穷指数。
对于任意的 RL L，如果DFA M=(Q，∑，δ，q0，F)满足L(M)=L，则|∑*/RL|≤|Q|。
表明，对于任意DFA M=(Q，∑，δ，q0，F)，|Q|≥|∑*/RL(M)|。
二义性CFG G=(V，T，P，S)，如果存在w∈L(G)，w至少有两棵不同的派生树，则称G是二义性的。
如果语言L不存在非二义性文法，则称L是固有二义性的，又称L是先天二义性的。文法可以是二义性的。语言可以是固有二义性的。
递归如果G中存在形如AnαAβ的派生，则称该派生是关于变量A递归的，简称为递归派生。
当α=ε时，称相应的(直接/间接)递归为(直接/间接)左递归
PDA描述CFL，所以它应该与CFG等价。
PDA应该包含FA的各个元素，或者包含那些可以取代FA的各个元素的功能的元素。
PDA按照最左派生的派生顺序，处理处于当前句型最左边的变量，因此，需要采用栈作为其存储机构。
按照FA的“习惯”，PDA用终态接受语言。
模拟GNF的派生PDA用空栈接受语言。
对于任意PDA M1，存在PDA M2，使得L(M2)=N(M1)；
对于任意PDA M1，存在PDA M2，使得N (M2)= L (M1)。
CFL可以用空栈接受语言的PDA接受。
油气弹簧
PDA接受语言可以用CFG描述。
分支点(branch point)：该结点有两个儿子，并且它的这两个儿子均有特异点后代。
（CFL的泵引理）对于任意的CFL L，存在仅仅依赖于L的正整数N，对于任意的z∈L，当|z|≥N时，存在u，v，w，x，y，使得z=uvwxy，同时满足：
(1) |vwx|≤N；
(2) |vx|≥1；
(3) 对于任意的非负整数i ，uviwxiy∈L。
证明L={anbncn|n≥1}不是CFL。
证明：
取z=aNbNcN∈L
⑴ v=ah，x=bf，h+f≥1。
uviwxiy=aN+(i-1)hbN+(i-1)fcN，
当i≠1时，N+(i-1)h≠N和N+(i-1)f≠N中至少有一个成立。
环境法学论文uviwxiy=aN+(i-1)hbN+(i-1)fcNL。
⑵ v=bh，x=cf，h+f≥1。
uviwxiy=aNbN+(i-1)h cN+(i-1)f
当i≠1时，N+(i-1)h≠N和N+(i-1)f≠N中至少有一个成立。
uviwxiy=aNhbN+(i-1)cN+(i-1)f L。
这些都与泵引理矛盾，所以，L不是CFL。
Ogden引理） 对于任意的CFL L，存在仅仅依赖于L的正整数N，对于任意的z∈L，当z中至少含有N个特异点时，存在u，v，w，x，y，使得z=uvwxy，同时满足:
(1) |vwx|中特异点的个数≤N；
(2) |vx|中特异点的个数≥1；
(3) 对于任意的非负整数i ，uviwxiy∈L。
例8-3 证明L={anbmchdj|n=0或者m=h=j}不是CFL。
取z=abNcNdN
⑴ v=a，x=bk，k≠0
此时uv2wx2y=aabN+kcNdNL；
⑵ v=bk，x=cg，k≠0，g≠0
此时uv2wx2y=abN+kcN+gdNL；
⑶ v=bk，x=dg，k≠0，g≠0
此时uv2wx2y=aabN+kcNdN+gL；
反课纲运动与Ogden引理矛盾，所以，L不是CFL。
CFL与RL的交是CFL。
证明：
（1）构造
设PDA M1=(Q1，∑，Γ，δ1，q01，Z0，F1) L1=L(M1)
DFA M2=(Q2，∑，δ2，q02，F2) L2=L(M2)
取PDA M=(Q1×Q2，∑，Γ，δ，[q01，q02]，Z0，F1×F2)生物圈二号
对([q，p]，a，Z)∈ (Q1×Q2)×(∑∪{ε})×Γ
δ([q，p]，a，Z)={([q′，p′]，γ) | (q′, γ)∈δ1(q，a，Z) 且 p′=δ(p，a)}
结论
⑴ x的任意前缀y有惟一的一个后缀z与之对应，使得x=yz；反之亦然。
⑵ x的任意真前缀y有惟一的一个真后缀z与之对应，使得x=yz；反之亦然。
⑶ |{w|w是x的后缀}|=|{w|w是x的前缀}|。
⑷ |{w|w是x的真后缀}|=|{w|w是x的真前缀}|。
⑸ {w|w是x的前缀}={w|w是x的真前缀}∪{x}，
|{w|w是x的前缀}|=|{w|w是x的真前缀}|+1。
⑹ {w|w是x的后缀}={w|w是x的真后缀}∪{x}，
|{w|w是x的后缀}|=|{w|w是x的真后缀}|+1。
⑺ 对于任意字符串w，w是自身的前缀，但不是自身的真前缀；w是自身的后缀，但不是自身的真后缀。
⑻ 对于任意字符串w，ε是w的前缀，且是w的真前缀；ε是w的后缀，且是w的真后缀
关于CFG和PDA主要有如下结论：
(1) 对于任意PDA M1，存在PDA M2，使得N (M2)= L (M1);
(2) 对于任意PDA M1，存在PDA M2，使得L (M2)= N (M1);
(3) 对于任意CFL L，存在PDA M，使得N(M)=L;
(4) 对于任意的PDA M，存在CFG G使得L(G)=N(M)。
设∑={0,1},请给出∑上的下列语言的文法
(3)所有以11开头以11结尾的串
S→11A|11
A→11|0A|1A
(6)所有长度为偶数的串
S→01|10|00|11|01S|10S|00S|11S北京智障大学
设，构造下列语言的文法。
(6) 。
解答：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议