《形式语言总结》由会员分享，可在线阅读，更多相关《形式语言总结（4页珍藏版）》请在金锄头文库上搜索。
1、aE语言 |L(G)=w 丨 wet*且 Sf* w 句子终极符号行，它不含语法变量 wEL(G), w称为G产生的一个句子。 句型符号行，它可能含有语法变量G=(V，T，P，S),对于 aW(VUT)*,如果 Sf* a, 则称a是G产生的一个句型。文法 |G=(V, T，P，S)。任意 AEV 表示集合 L(A)=w I wET* 且 A f* wo推导与归约。文法中的推导是根据文法的产生式进行的。 如果afEP，y，8E(VUT)*，则称ya在G中直接推导出 Y閃：YaS G y閃；也称Y閃在文法G中直接归约成yaN 对任意的x，yE +,我们要使语法范畴D代表的集合为 xnynlnl，
2、可用产生式组DfxylxDy来实现。设有两个文法G1和G2,如果L(G1)= L(G2),则称G1与G2 等价。例文法G： Sf abc I aSbc产生的语言为：an(bc)n丨n三1下两个条件： 存在wET*，使得Xf*w； a,卩E(VUT)*，使得 Sf*aXp。CNF|乔姆斯基范式文法:CFG G=(V, T, P, S)中的产生式形 式：AfBC, Afa，其中，A、B、CEV, aET。不允许有- 产生式、单一产生式。对于任意CFG| G, fL(G)，存在等价的CNFfG2 格雷巴赫范式文法GNF:Af a a，其中，AEV, aET,V*。在GNF中，有如下两种形式的产生式A
3、fa;AfaA1A2Am(m 三 1)推自动机*, r*)称为m的一个即时描述。如果(p，Y )E6 (q, a, Z), aE工，贝 J(q, aw, ZB)卜 M(p, w，yB )表示M做一次非空移动，从ID(q, aw, ZB )变成ID(p, w，yB )。M用终态接受的语言G14： SfaBC | aSBC,CBfBC aBf ab bBfbb bCfbc cCf cc线性文法(liner grammar)设G=(V, T, P, S)，如果对于 afEP, a卩均具有如下形 式：AfwAfwBx其中 A, BEV, w, xET*,则称L(M)=w l (q0, w, Z0)|-
4、*(p,&,B)且 pEFM用空栈接受的语言N(M) =w l (q0, w, Z0) |-*(p,&, ) 对于任意CFL L,存在PDA M,使得N(M)=Lo 能引导FA从开始状态到达q的字符串的集合为:set(q)=x l x EE*,6(q0, x)=q定理5-1 (Myhill-Nerode定理)|如下三个命题等价:L 工*是RL ；最左派生I a的派生过程中，每- 步都是对当前句型的最左变量 进行替换。规范派生最右派生。 规范句型规范派生产生的句型。规范归约最左归约。如果对于afEP,均有卩曰a成立，则称G为1型文法或 上下文有关文法IcsG)o如果对于afEP,均有|阻|a|，
5、并且aEV成立，则称G 为2型文法，或上下文无关文法CFG)。如果对于 afEP, a卩均具有形式Afw ,AfwB,其中 A, BEV, wET+o Rg|)FA) M=(Q, , S, qO, F)L(M)=xl xE*且 S(q, w)EFNFAL(M)=xl xEE*且5(q0, w) n FO,设 DFA M=(Q, , S, q0, F)例 5-3 证明0n1m2n+mlm, n1不是 RL。 证明：假设 L=0n1m2n+mlm, n1是 RL。 取 z=0N1N22N 设 v=0k k1从而有，uviw=0N-k-j(0k)i0j1N22N=0N+(i-1)k1N22N uv0
6、w=0N+(0-1)k1N22N=0N-k1N22N注意到k1,N-k+N=2N-k2N0N-k1N22N L这个结论与泵引理矛盾。所以，L不是RLo设R是Y*上的等价关系，对于x, yE*,如果x RL y, 则必有xz RL yz对于zE*成立，则称R是右不变的等价 关系。对于任意XEVUT，如果X是有用的，它必须同时满足如L是工*上的某一个具有有穷指数的右不变等价关系R的 某些等价类的并；RL具有有穷指数。对于任意的RL L,如果DFAM=(Q，E，8，q0，F)满足L(M)=L,则l*/RLlWlQl。表明，对于任意 DFA M=(Q,工，S,q0, F), IQllY */RL(M)
7、l。 二义性CFG G=(V, T, P, S),如果存在wEL(G), w至少 有两棵不同的派生树，则称G是二义性的。如果语言L不存在非二义性文法，则称L是固有二义性的, 又称L是先天二义性的。文法可以是二义性的。语言可以是 固有二义性的。递归如果G中存在形如A na AB的派生，则称该派生是 关于变量A递归的，简称为递归派生。当a= 时，称相应的(直接/间接)递归为(直接涧接)左递归 PDA描述CFL，所以它应该与CFG等价。PDA应该包含FA的各个元素，或者包含那些可以取代FA 的各个元素的功能的元素。PDA按照最左派生的派生顺序，处理处于当前句型最左边 的变量，因此，需要采用栈作为其存
8、储机构。按照FA的“习惯” PDA用终态接受语言。模拟GNF的派生PDA用空栈接受语言。对于任意PDA M1,存在PDA M2,使得L(M2)=N(M1)； 对于任意PDA M1,存在PDA M2,使得N (M2)= L (M1)。CFL可以用空栈接受语言的PDA接受。儿子均有特异点后代。(CFL的泵引理)对于任意的CFL L,存在仅仅依赖于L的 正整数N,对于任意的zWL，当Izl三N时，存在u, v, w, x, y,使得z=uvwxy，同时满足：(1) IvwxIWN；(2) Ivxll；(3) 对于任意的非负整数i , uviwxiyWL。证明 L=anbncnln三 1不是 CFL。
9、证明：取 z=aNbNcNGL v=ah, x=bf, h+f三 1。uviwxiy=aN+(i-1)hbN+(i-1)fcN,当iH1时，N+(i-1)hMN和N+(i-1)fMN中至少有一个成立。 uviwxiy=aN+(i-1)hbN+(i-1)fcNL。 v=bh, x=cf, h+f三 1。uviwxiy=aNbN+(i-1)h cN+(i-1)f当iH1时，N+(i-1)hMN和N+(i-1)fMN中至少有一个成立。 uviwxiy=aNhbN+(i-1)cN+(i-1)fL。这些都与泵引理矛盾，所以,L不是CFL。Ogden引理)对于任意的CFL L,存在仅仅依赖于L的正 整数N
10、,对于任意的zL,当z中至少含有N个特异点时, 存在u, v, w, x, y,使得z=uvwxy，同时满足：(1) |vwx|中特异点的个数WN；(2) |vx|中特异点的个数三1；(3) 对于任意的非负整数i , uviwxiyWL。例 8-3 证明 L=anbmchdj|n=O 或者 m=h=j不是 CFL。取 z=abNcNdN v=a, x=bk, kMO此时 uv2wx2y=aabN+kcNdNL； v=bk, x=cg, kM0, gM0此时 uv2wx2y=abN+kcN+gdN L； v=bk, x=dg, kM0, gM0此时 uv2wx2y=aabN+kcNdN+gL；与
11、Ogden引理矛盾，所以，L不是CFL。CFL与RL的交是CFL。证明：(1)构造设 PDA M1=(Q1,E,r,S 1, q01, Z0, F1)L1=L(M1)DFA M2=(Q2,E,6 2, q02, F2)L2=L(M2)取 PDA M=(Q1XQ2,E,r,S, q01, q02, Z0, F1XF2)对 (q, p, a, Z)G (Q1XQ2)X(EU e )Xr6 (q，p，a, Z)=(q，pz ，Y) | (q , Y)eS 1(q, a, Z)且 p = 6 (p, a)结论(1) x的任意前缀y有惟一的一个后缀z与之对应，使得x=yz； 反之亦然。x的任意真前缀y有
12、惟一的一个真后缀z与之对应，使得 x=yz ；反之亦然。|w|w是x的后缀|=|w|w是x的前缀|。|w|w是x的真后缀|=|w|w是x的真前缀|。w|w是x的前缀=w|w是x的真前缀 U x,|w|w是x的前缀|=|w|w是x的真前缀|+1。(6) w|w是x的后缀=w|w是x的真后缀 U x,|w|w是x的后缀|=|w|w是x的真后缀|+1。对于任意字符串w, w是自身的前缀，但不是自身的真 前缀；w是自身的后缀，但不是自身的真后缀。 对于任意字符串w, e是w的前缀，且是w的真前缀; e是w的后缀，且是w的真后缀 关于CFG和PDA主要有如下结论:(1) 对于任意 PDA M1,存在 P
13、DA 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,请给出送上的下列语言的文法所有以11开头以11结尾的串S11AI11A11I0AI1A (6)所有长度为偶数的串S01I10I00I11I01SI10SI00SI11S设工=a,b,c,，构造下列语言的文法。(6) L = xwxt I x, w e E+。6解答： G6 = (S,W,a,b,c, P6,S)P S
14、T aWa I bWb I cWc6:W T aW I bW I cW I a I b I c。(7) L7解答：=w I w = wt , w e E+ o解：不妨假设VV =0,并且S电vUv，令g = (sUVuV, tUt, pUP P, s)1212123其中，P =Sbe T+且S n+S Ta Is TaUs ts32111证明：(1)设x e L(G)，贝IJS n* x若x = s,因为s e L(G ), s e L(G )，所以s e L(G )L(G )成立1 2 1 2若x hs,由产生式S TbS，不妨设x = xx，其中x e T+, x e L(G )则S n* x，因为G的产生式包括P,所以x eL(G )，可知x = xx eL(G )L(G 所以 L(G)匸 L(G )L(G )2心12(1)设x e L (G )L (G )，不妨设x =x 北时，由户中5 tbS beT+且S n+b$,贝iS n+ xS n+1321112所以 xx e L(G), L(G )L(G)匸 L(G)x =时，由P 中Ta Is Ta S n* x1 312x =时，由$ TS,得S n* x 所以x eL(G)2 2 2L(G )L(G 尢 L(G)12综上, L(G)=L(G )L(G )12=xx，其中x eT*, S n* x, x eT*,
