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