形式语言总结

语言L(G)={w|w∈T*且S→*w}句子终极符号行，它不含语法变量w∈L(G)，w称为G产生的一个句子。句型符号行，它可能含有语法变量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中直接归约成γαδ。对任意的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}G14：S→aBC|aSBC，CB→BCaB→abbB→bbbC→bccC→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≠Φ}，设DFAM=(Q，∑，δ，q0，F)例5-3证明{0n1m2n+m|m，n≥1}不是RL。证明：假设L={0n1m2n+m|m，n≥1}是RL。取z=0N1N22N设v=0kk≥1从而有，uviw=0N-k-j(0k)i0j1N22N=0N+(i-1)k1N22Nuv0w=0N+(0-1)k1N22N=0N-k1N22N注意到k≥1，N-k+N=2N-k2N0N-这个结论与泵引理矛盾。所以，L不是RL。设R是∑*上的等价关系，对于，y∈∑*，如果xRLy，则必有xzRLyz对于∈∑*成立，则称R是右不变的等价关系。对于任意X∈V∪T，如果X是有用的，它必须同时满足如下两个条件：①存在w∈T*，使得X→*w；②α，β∈(V∪T)*，使得S→*αXβ。CNF乔姆斯基范式文法:CFGG=(V，T，P，S)中的产生式形式：A→BC，A→a,其中，A、B、C∈V，a∈T。不允许有ε-产生式、单一产生式。对于任意CFGG，ε→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，γβ)。M用终态接受的语言L(M)={w|(q0，w，Z0)├*(p，ε，β)且p∈F}M用空栈接受的语言N(M)={w|(q0，w，Z0)├*(p，ε，ε)}对于任意CFLL，存在PDAM，使得N(M)=L。能引导FA从开始状态到达q的字符串的集合为：set(q)={x|x∈∑*，δ(q0，x)=q}定理5-1(Myhill-Nerode定理)如下三个命题等价：⑴L*是RL；⑵L是∑*上的某一个具有有穷指数的右不变等价关系R的某些等价类的并；⑶RL具有有穷指数。对于任意的RLL，如果DFAM=(Q，∑，δ，q0，F)满足L(M)=L，则|∑*/RL|≤|Q|。表明，对于任意DFAM=(Q，∑，δ，q0，F)，|Q|≥|∑*/RL(M)|。二义性CFGG=(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用空栈接受语言。对于任意PDAM1，存在PDAM2，使得L(M2)=N(M1)；对于任意PDAM1，存在PDAM2，使得N(M2)=L(M1)。CFL可以用空栈接受语言的PDA接受。PDA接受语言可以用CFG描述。分支点(branchpoint)：该结点有两个儿子，并且它的这两个儿子均有特异点后代。线性文法(linergrammar)设G=(V，T，P，S)，如果对于∈P，均具有如下形式：A→wA→wBx其中A，B∈V，w，x∈T*，则称G为线性文法。最左派生α的派生过程中，每一步都是对当前句型的最左变量进行替换。规范派生最右派生。规范句型规范派生产生的句型。规范归约最左归约。（CFL的泵引理）对于任意的CFLL，存在仅仅依赖于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)hcN+(i-1)f当i≠1时，N+(i-1)h≠N和N+(i-1)f≠N中至少有一个成立。uviwxiy=aNhbN+(i-1)cN+(i-1)fL。这些都与泵引理矛盾，所以，L不是CFL。Ogden引理）对于任意的CFLL，存在仅仅依赖于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）构造设PDAM1=(Q1，∑，Γ，δ1，q01，Z0，F1)L1=L(M1)DFAM2=(Q2，∑，δ2，q02，F2)L2=L(M2)取PDAM=(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)对于任意PDAM1，存在PDAM2，使得N(M2)=L(M1);(2)对于任意PDAM1，存在PDAM2，使得L(M2)=N(M1);(3)对于任意CFLL，存在PDAM，使得N(M)=L;(4)对于任意的PDAM，存在CFGG使得L(G)=N(M)。设∑={0,1},请给出∑上的下列语言的文法(3)所有以11开头以11结尾的串S→11A|11A→11|0A|1A(6)所有长度为偶数的串S→01|10|00|11|01S|10S|00S|11S设},,,{cba，构造下列语言的文法。(6)},|{6wxxwxLT。解答：),},,,{},,({66SPcbaWSG:6PcWcbWbaWaS||cbacWbWaWW|||||。(7)},|{7。解答：}},|||||{},,,{},,{{7ScbacWcbWbaWaScbaWSG(8)},|{8wxwxxLT。解答：),},,,{},,,({88SPcbaXWSGXWSP:8cbacXcbXbaXaX|||||cbacWbWaWW|||||。构造满足下列要求的RGG，并证明你的结论。12(1)()()()LGLGLG1212121212332111*12122121111*2222VVSVVGSVVTTPPPSPSSTSSSSxLGSxxLGLGLGLGxSSxxxxTxLGSxGPxL解：不妨假设，并且，令，，，其中，且证明：（1）设，则若，因为，，所以成立若，由产生式，不妨设，其中，则，因为的产生式包括，所以2121212****1212111122221321112121212*1312*2221GxxxLGLGLGLGLGxLGLGxxxxTSxxTSxxPSSTSSxSxxxxLGLGLGLGxPSSSxxSSxxLGLGLG，可知所以（1）设，不妨设，其中，，，时，由中且，则所以，时，由中时，由，得所以212LGLGLGLG综上，3101001000έέέέέέ011000έέέέ000έέέ构造下列语言的DFA（5）{x|x{0，1}+且x中含形如10110的子串}1S00100,11010111）{x|x{0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}可将{0，1}+的字符串分为4个等价类。q0：[]的等价类，对应的状态为终止状态q1:x的长度为奇且以0结尾的等价类q2：x的长度为奇且以1结尾的等价类q3:x的长度为偶且以0结尾的等价类q4:x的长度为偶且以1结尾的等价类11S0q1q2q0q40q310011S10，10(1)求正则方法G,使L(G)=L(M)q0→3q0|1q1q1→0q2|1q3q2→0|0q2q3→1|1q331q0q1q2q301011q0,3031,30,1,3*(7){{0,1}}xxx且如果以1结尾，则它的长度为偶数；如果以0结尾，则它的长度为奇数(1)给出你所画出的DFA的每个状态q的set(q):set(q)={x|xΣ*且δ(q0,x)=q}set(q0)={3*}set(q1)={3*1}set(q2)={3*100*}set(q3)={3*111*}set(q)={(3*0|3*13|3*100*(1|3)|3*111*(0|3))0*1*3*}例7