课程名称︰自动机与形式语言 课程性质︰必修 课程教师︰林智仁 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2010.12.7 考试时限（分钟）：120 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : #Please give details of your calculation. A direct answer without explanation is not counted. #Your answers must be in English. #Please carefully read problem statements. #During the exam you are not allowed to borrow others' notes. #Try to work on easier questions first. #Please draw all the diagrams clearly. Prlblem 1 (20pts) Consider the following two-tape TM: U→R U→L 0→R U→R U→R U→L U→R U→R start → q0 → q1 → q2 → q4 → qa ↓↑ 0→R U→L ↓↑ 0→R 0→L↓↑0→L U→0,R U→0,R 0→R q3 Assume the initial configuration is U000000 in the 1st tape and UU... in the 2nd tape. Run the TM and give the sequence of configurations. Problem 2(40 pts) Construct a standard TM to recognize the following language: {0^n#1^n#0^n | n >= 0}, where Σ = {0,1}. The # states <= 9 (including q[accept] and q[reject]). You need to show the formal definition of the TM, but you can draw a state diagram instead of giving a formal definition of the transition function δ. You also need to explain the meaning of each edge. Problem 3(40 pts) Consider the following deginition of nondeterministic TM: NTM = (Q,Σ,ζ,δ,q1,qa,qr), where qa != qr and δ:Q X ζ^k → P(Q X ζ^k X {L,R,S}^k). Give a two-tape NTM to recognize the following language: {a^ib^ic^i | i,j,k >= 0 and i = j or i = k}. The # of state <= 8 (including q[accept] and q[reject]). You do not have to give a formal definition.(A diagram is enough.) You also need to explain the meaning of each edge. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.96