形式语言与自动机理论试题

1、形式语言与自动机理论试题 一、按要求完成下列填空 1. 给出集合,和集合,0,00的幂集 （2x4） (1) , (2) ,0,00,0,00,0,00,0,00 2. 设=0,1,请给出上的下列语言的文法 （2x5） (1)所有包含子串01011的串 SX01011Y X|0X|1X Y|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A|A|A” A 0|01|01A A” 1|10|10A” 3. 构造识别下列语言的DFA 2x6 (1) x|x?0，1+且x以0开头以1结尾 （设置陷阱状态，当第一个字符为1时，进入陷阱状态） (2) x|x?0，1+且x的第十个字符为

2、1 （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态） 二、判断（正确的写T，错误的写F） 5x2 1.设R1和R2是集合a,b,c,d,e上的二元关系，则 ( T ) 任取(x.,y),其中x,y?a,b,c,d,e，使得(x,y)?(R1?R2)R3。 ?z(x,z)?R1?R2?(z,y)?R3) z?a,b,c,d,e ?z(x,z)?R1?(x,z)?R2?(z,y)?R3) ?z(x,z)?R1?(z,y)?R3)?z(x,z)?R2?(z,y)?R3) ?(x,y)?R1R3?(x,y)?R2R3 ?(x,y)?R1R3?R2R3 (R?R)R?RR?RR123132

3、3 2 ( T ) 2.对于任一非空集合A，? 3.文法G：A|AS a|b|c|d|e|f|g 是RG ( F ) 4.3型语言2型语言1型语言0型语言 ( T ) A? 5.s（rs+s）*r=rr*s（rr*s）* ( F ) 不成立，假设r,s分别是表示语言R，S的正则表达式，例如当R=0，S=1, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ? L(rr*s(rr*s)*) 所以s(rs+s)*r? rr*s(rr*s)*,结论不成立 三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推

4、导（12分）。 S?aBC|aSBC aB?ab bBbb CBBC bCbc cCcc 推导一： S=>aSBC =>aaSBCBC =>aaaBCBCBC =>aaabCBCBC =>aaabBCCBC =>aaabbCCBC =>aaabbCBCC ? =>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccC =>aaabbbccc 推导二： S=>aSBC =>aaSBCBC =>aaaBCBCBC =>aaaBBCCBC =>aaaBBCBCC

5、=>aaabBCBCC =>aaabbCBCC =>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccC =>aaabbbccc 四、判断语言0n1n0n|n>=1是否为RL，如果是，请构造出它的有穷描述(FA,RG或者RL）；如果不是，请证明你的结论（12分） 解：设L=0n1n0n|n>=1。假设L是RL，则它满足泵引理。不妨设N是泵引理所指的仅依赖于 L的正整数，取Z=010 显然，ZL 。 按照泵引理所述，必存在u，v，w。由于|uv|<=N,并且|v|>=1，所以v只可能是由0组成

6、的非空串。不妨设v=0，k>=1 此时有u=0 uvw=0iNNNkN?k?j ，w=010 从而有jNNN?k?j(0k)i0j1N0N 当i=2时，有uv2w=0N?k1N0N 又因为k>=1, N?kN所以 N+k>N 这就是说010N不属于L， 这与泵引理矛盾。所以，L不是RL。 五、构造等价于下图所示DFA的正则表达式。(12分) 0 ?+(1+00)(1+00*1)0)*00*) 3 去掉q3： 去掉q1： 3Y Y Y 去掉q2： 去掉q0： Y 01+(1+00)(1+00*1)0)*(1+00*1)1) (01+(1+00)(1+00*1)0)*(1+00*

7、1)1)* (?+(1+00)(1+00*1)0)*00*) Y 六、设M=（q0,q1,q2，0,1，0,1，B，q0,B,2）,其中的定义如下： （0，0）=（q0，0，R） （q0，1）=（q1，1，R） （q1，0）=（q1，0，R） （1，B）=（q2，B，R） 请根据此定义，给出M处理字符串00001000,10000的过程中ID的变化。（10分） 解：处理输入串00001000的过程中经历的ID变化序列如下： qqqq 000001000 0q 00001000 000010q 100 00q 0001000 0000100q 10 000q 001000 00001000q 1

8、 0000q 010000 00001000Bq2 00001q 10000 处理输入串10000的过程中经历的ID变化序列如下： q 010000 1q 100000 10q 1000 100q 100 1000q 10 10000q 1 10000Bq2 七、根据给定的NFA，构造与之等价的DFA。（14分） NFA M的状态转移函数如下表 解答： 参 考 题 目 1、设?a,b,c,，构造下列语言的文法。 (1) L1?anbn|n?0。 解答：G1?(S,a,b,S?aSb|?,S)。 (2) L2?anbm|n,m?1。 解答：G2?(S,A,B,a,b,S?A|B,A?aA|a,B

9、?bB|b,S)。 (3) L3?anbnan|n?1。 解答：G3?(S,A,B,a,b,P3,S) P3: S aAB|aSAB BAAB aBab bBbb bAba aAaa (4) L4?aba|n,m,k?1。 nmk 解答：G4?(S,A,a,b,S?ABA,A?aA|a,B?bB|b,S)。 (5) L5?awa|a?,w?。 解答：G5?(S,W,a,b,c,S?aWa,W?aW|bW|cW|a|b|c,S)。 (6) L6?xwxT|x,w?。 解答：G6?(S,W,a,b,c,P6,S) P6:S?aWa|bWb|cWc W?aW|bW|cW|a|b|c。 (7) L7?

10、w|w?w,w?。 T? 解答：G7?S,W,a,b,c,S?aWa|bWb|cWc|a|b|c,S。 (8) L8?xxTw|x,w?。 解答：G8?(S,W,X,a,b,c,P8,S) P8:S?XW X?aXa|bXb|cXc|a|b|c W?aW|bW|cW|a|b|c。 2、给定RG：G1?(V1,T1,P1,S1)，G2?(V2,T2,P2,S2)，试分别构造满足下列要求的RG G，并证明你的结论。 (1)L(G)?L(G1)L(G2) 解： 不妨假设V1V2?，并且S?V1V2，令G?S?V1V2，T1T2，P1其中， P3?S?S2?T1?且S1?证明： （1）设x?L?G?，

11、则S?*x 若x?，因为?L?G1?，?L?G2?，所以?L?G1?L?G2? 成立若x?，由产生式S?S2，不妨设x?x1x2，其中x1?T1?，x1?L?G1? 则S2?*x2，因为G的产生式包括P2，所以x2?L?G2?，可知x?x1x2?L?G1?L?G2?所以 L?G?L?G1?L?G2? （1）设x?L?G1?L?G2?，不妨设x?x1x2，其中x1?T1*，S1?*x1，x2?T2*，S2?*x2x1?时，由P3中S?S2?T1?且S1?，则S?x1S2?x1x2所以 x1x2?L?G?，L?G1?L?G2?L?G?x1?时，由P3中?S?S1? S?*x2x2?时，由S?，得S

12、?*x2 所以x2?L?G?L?G1?L?G2?L?G?综上，L?G?L?G1?L?G2? P2 P3，S? ? ?S?S 1 ?S? ? (2)L(G)?L(G1)L(G2) 解： 不妨假设V1V2?，并且S?V1V2，令 G?S?V1V2，T1T2，P1 其中， P3?S?S1?或S2? 证明： （1）设x?L?G1?L?G2? 不妨设x?L?G1? 那么可知S1?x*P2P3，S? 由G构造方法可知，S?*x 且x?L?G? 即L?G1?L?G2?L?G? （2）设x?L?G? 则S?*x，由P3知，S1?*x或S2?*x不妨设S1?*x 则 x?L?G1? ， L?G1?L?G? 同理

13、 L?G2?L?G? 则 L?G1?L?G2?L?G?所以 L?G?L?G1?L?G2? (3)L(G)?L(G1)?a,b?L(G2),其中a，b是两个不同的终极符号 解： 不妨假设V1V2?，并且S?V1V2，令 G?S?V1V2，T1T2，P1 其中， P3?S?aS2?bS2其中?T1*且S1?*? 证明： （1）设x?L?G? 则S?*x 由产生式S?aS2，不妨设x?1a?2 则?1?T1*，S2?*?2 则?1?L?G1?，?2?L?G2?所以x?1a?2?L(G1)?a,b?L(G2) 同理?1b?2?L(G1)?a,b?L(G2)可得L(G)?L(G1)?a,b?L(G2)

14、（2）设x?L(G1)?a,b?L(G2) 不妨设x?1a?2 其中?1?L(G1)，?2?L(G2) 即S1?*?1，S2?*?2 由P3中产生式 S?*?1aS2?1a?2 所以L(G1)?a,b?L(G2) ?L?G? 综上可得，L(G)?L(G1)?a,b?L(G2) P2P3，S?S?S1? (4)L(G)?L(G1)* 解： P=S|S1P1SSS|S1P1 证明略。 (5)L(G)?L(G1)? 解： P=S|S1P1SS|S1P1 证明略。 3、设文法G有如下产生式： SaBbA AaaSbAA BbbSaBB 证明L(G)中含有相同个数的a和b，且非空。 证：观察发现A的产生

15、式AbAA中的bA可以用S来代替，同样B的产生式BaBB中的 aB也可以用S代替。这样原来的文法可以化为如下的形式： SaBbA AaaSSA BbbSSB 进一步地，可以把产生式AaS中的S代换，把文法化为如下的形式： SaBbA AaaaBabASA BbbaBbbASB 7设DFA M=(Q,?,?,q0,F)，证明：对于?x,y?*,q?Q,?(q,xy)?(?(q,x),y) 注：采用归纳证明的思路 证明： (周期律 02282067) 首先对y归纳，对任意x来说，|y| = 0时，即y=? 根据DFA定义?(q,?)?q,?(q,xy)?(q,x)?(?(q,x),?)?(?(q,

16、x),y),故原式成立。 当|y| = n时，假设原式成立，故当|y|= n+1时， 不妨设y = wa, |w| = n, |a| = 1 根据DFA定义?(q,xa)?(?(q,x),a),a?，故 ?(q,xy)?(q,xwa)?(?(q,xw),a)?(?(?(q,x),w),a)?(?(q,x),wa)?(?(q,x),y)原式成立， 同理可证，对任意的y来说，结论也是成立的。 综上所述，原式得证 * 8证明:对于任意的DFA M1=(Q,q0,F1) 存在DFA M2=(Q,q0,F2), 使得L(M2)=*L（M1）。 证明：（1）构造M2。 设DFA M1=(Q,q0,F1)

17、取DFA M2=(Q,q0,QF1) （2）证明L(M2)=*L（M1） 对任意x?* x? L(M2)=*L（M1）?(q,x)?QF1?（q,x）?Q并且（q,x）?F1?x?*并且x?L(M1)?x?*L（M1） 10、构造识别下列语言的NFA (1)xx?0,1?且x中不含形如00的子串 (2)xx?0,1?且x中含形如10110的子串 (3)xx?0,1?且x中不含形如10110的子串 (4)xx?0,1?和x的倒数第10个字符是1，且以01结尾 1 (5)xx?0,1?且x以0开头以1结尾 (6)xx?0,1?且x中至少含有两个1 0，10，1 (7)xx? 0,1*且如果x以1结

18、尾，则它的长度为偶数； 如果以0结尾，则它的长度为奇数 (8)xx?0,1?且x的首字符和尾字符相等 (9)x?xTx,? 0,1? 11.根据给定的NFA，构造与之等价的DFA. （1） NFA M 的状态转移函数如表3-9 13试给出一个构造方法，对于任意的NFA M1?(Q1,?,?1,q0,F1)，构造NFA M2?(Q2,?,?2,q0,F2)，使得L(M2)?*?L(M1) 注：转化成相应的DFA进行处理，然后可参考第8题的思路 证明： 首先构造一个与NFA M1等价的DFA ，M3根据定理3.1（P106），L(M3)?L(M1) 构造M3?(Q3,?,?3,q0,F3),其中

19、Q3?2Q1,F3?p1,p2.pm|p1,p2.pm?Q,p1,p2.pm?F1?,p1,p2.pm?Q,a? ?3(q1.qn,a)?p1.pm?1(q1.qn,a)?p1.pm 在此基础上M2，Q2?Q3,?2?3,F2?p1.pm|p1.pm?F3? 即取所有M1确定化后不是终结状态的状态为M2的终结状态。 为了证明L(M2)? ? * ?L(M3)，我们在M3的基础上M4?(Q4,?,?4,q0,F4)，其 中Q4?Q3,?4?3,F4?Q4，即所有M1确定化后的状态都为终结状态。显然 L(M4)?*, ?x?L(M2),则?(q0,x)?F2?(q0,x)?F3?x?L(M3),又

20、因为 ?(q0,x)?Q3?(q0,x)?F4?(q0,x)?L(M4)?*,故x?*?L(M3)， 故L(M2)? ? * ?L(M3) 同理容易证明L(M2)?故L(M2)? ? * ?L(M3) ? * ?L(M3)，又因为L(M3)?L(M1)，故L(M2)?*?L(M1) 可知，构造的M2是符合要求的。 15P129 15.(1)、（2） （1）根据NFAM3的状态转移函数，起始状态q0的?闭包为 ?-CLOSURE（q0）= q0, q2。由此对以后每输入一个字符后得到的新状态再做?闭包，得到下表： （陶文婧 02282085） 0=0,21=0,1，22=0,1，2，332=0,

21、1，2，3为终止状态 2 （2）用上述方法得 0=1,31=3，22=0,1，2，33=0,1，34=1，2，3终止状态，所以q0, q1，q2，q3,q4均为终止状态 注：本题没有必要按照NFA到DFA转化的方法来做，而且从?-NFA到NFA转化时状态没有必要改变，可以完全采用?-NFA中的状态 如（1） 16、证明对于?的FA M1=(Q1,1,1,q01,F1)，FA M1=(Q2,2,2,q02,F2)，存在FA M， 使得 L(M)= L(M1)L(M2) 证明：不妨设Q1 与Q2的交集为空 （1） 构造M=（Q1Q2 q0, q0,F）其中： 1）=12 F= F1F2 2) (q

22、0,)= q01 ,q02 对于? qQ1,a1(q, a)=1(q,a) 对于? qQ2,a2 ,(q, a)=2(q,a) (1) 证明： 1）首先证L(M1)L(M2)L(M) 设 x L(M1)L(M2)，从而有x L(M1)或者x L(M2)，当x L(M1)时 1(q01,x)F1 由M的定义可得： （q0,x）=（q0,x）=(q0,), x)=(q01 ,q02,x)=(q01 , x)(q02, x) =1(q01 , x) (q01 , x)F1(q01 , x) 即xL(M) 同理可证当x L(M2)时xL(M) 故L(M1)L(M2)L(M) 2) 再证明L(M)L(M

23、1)L(M2) 设xL(M) 则（q0,x）F 由M的定义： （q0,x）=（q0,x）=(q0,), x)=(q01 ,q02,x) =(q01 , x)(q02, x) 如果是(q01 , x) 因为Q1 与Q2的交集为空 而且（q0,x）F F= F1F2 则 (q01 , x)= 1(q01 , x)F1 因此xL(M1) 如果是(q02 , x) 因为Q1 与Q2的交集为空 而且（q0,x）F F= F1F2 则 (q02 , x)= 2(q02 , x)F1 因此xL(M2) 因此xL(M1)L(M2) L(M)L(M1)L(M2)得证 因此L(M)= L(M1)L(M2) 17

24、证明：对于任意的FAM1?(Q1,?1,?1,q01,F1),FAM2?(Q2,?2,?2,q02,F2), 存在FA M,使得L(M)?L(M1)L(M2). 证明：令 ? ( Q 1 Q 2 , ? , ? ,其中的定义为： M?,q01,f2) 1) 对?qQ1-f1，a (q，a)=1(q，a)； 2) 对?qQ2-f2，a (q，a)=2(q，a)； 3) (f1，)=q02 要证 L ( ) ? L ( M 1 ) L ( M 2 ) ， M 只需证明 L ( M 1 ) L ( M 2 ) ? L ( M ) ， ( M 1 ) L ( M 2 ) L ( M ) L? 1. 证

25、明 L (M 1)L(M2)?L(M) 设x?L(M1)L(M2),从而有x1?L(M1)并且x2?L(M2), x?x1x2 使得 M1在处理x1的过程中,经过的状态全部都是Q1中的状态,所以在定义 M时,对?q?Q1,a?,?(q,x)?1(q,a) 故?(q01,x1)?1(q01,x2)?f1 M2在处理x2的过程中,经过的状态全部都是Q2中的状态,所以在定义 M时,对?q?Q1,a?,?(q,x)?2(q,a) ?(q02,x)?2(q01,x)?f2 下面证明x?L(M) ?(q01,x)?(q01,x1x2)?(?(q01,x1),x2)?(?1(q01,x1),x2)?(f1,

26、x2)?(f1,?x2) 2) 再证明 ?(?(f1,?),x2)?(q02,x2)?2(q02,x2)?f2即得证x?L(M)L(M)?L(M1)L(M2)设x?L(M),即?(q01,x)?f2M是从q01启动的,由M的定义可知,M要达到状态f2,必须先到f1.由于除了对应状态转移函数式?(f1,?)?q02的移动外,不存在从f1出发的任何其他移动,而且该移动是f2的必经移动,所以,比存在x的前缀x1和后缀x2,使得x?x1x2,并且x1将M从状态q01引导到状态f1,x2将M从状态q02引导到状态f2.即?(q01,x)?(q01,x1x2)?(f1,x2)?(f1,?x2)?(q02,

27、x2)?f2其中,?(q01,x1)?f1,说明?1(q01,x1)?f1;?(q02,x2)?f2,说明?2(q02,x2)?f2 由于 这表明 x1?L(M1)x2?L(M2) 从而x?x1x2?L(M1)L(M2) 故 L(M)?L(M1)L(M2)L(M)?L(M1)L(M2 * （吴丹 02282090） 综上所述, 18.证明：对于任意的FA M1?Q1，?1，?1，q01，F1?，FA M2?Q2，?2，?2，q02，F2?存在FA M，使得L?M?L?M1?L?M2?。证明：不妨将这些FA看成DFA 取M?Q1?Q2，?1?2，?，?q01，q02?，F? 对于?a?1?2，?q,p?Q,?q,p?，a?1?q，a?，?2?p，a?. ?1?设：x?L?M?则?x?x1x2.xk其中xi?i?1,k?1?2使得?q,p?，xi?1?q，xi?,?2?p，xi?xi?L?M1?L?M2?x?L?M1?L?M2?从而可得L?M?L?M1?L?M2? ?2?