課程名稱︰自動機與形式語言 課程性質︰必修 課程教師︰林智仁 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰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