※ [本文轉錄自 NTU-Exam 看板 #1GlUsQUs ]
作者: rod24574575 (天然呆) 看板: NTU-Exam
標題: [試題] 101上 林智仁 自動機與形式語言 期中考2
時間: Tue Dec 4 20:33:27 2012
課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰林智仁
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2012.12.4
考試時限（分鐘）：135分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題：
˙ Please give details of your answer. 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' class notes.
˙ Try to work on easier questions first.
Problem 1 (20pt)
Consider the following NFA.
┌─┐ 1 ┌─┐0,1,ε┌─┐0,1,ε╔═╗
start ─→│q1│──→│q2│──→│q3│──→║q4║
└─┘ └─┘ └─┘ ╚═╝
↑│
└┘0,1
1. Find a CFG with no more than 7 rules for this language.
2. Find a PDA with no more than 4 states for this language. Give the formal
definition and the state diagram.
Problem 2 (25pt)
Consider the following language
n n
{0 1 │n≧0}.
1. What is the PDA with the smallest number of states such that it has a
single accept state?
2. Use the method taught in the class to simulate the input string 000111
by drawing a tree.
3. Modify the PDA in 1 to satisfy all conditions needed in lemma 2.27 and
produce CFG rules.
Problem 3 (5pt)
Let Σ = {0, 1}. Give a PDA with the smallest number of states such that it
may accept strings when the stack is not empty.
Problem 4 (10pt)
Please design an one tape Turing machine with no more than 5 states (including
q_a and q_r) that shifts the input to the right for one position. For example,
0101 becomes ∪0101. Let Σ = {1, 0}. You need only draw the state diagram.
Links to q_r are not needed.
Problem 5 (40pt)
Consider the following language
n 2n
{0 #0 │n≧0}.
1. (5%) Give a CFG with no more than 2 rules for this language.
2. (5%) Construct a PDA with no more than 5 states for this language.
3. (15%) Construct a Turing machine with no more than 9 states (including
q_a and q_r) for this language. Links to q_r are not needed.
4. (15%) Construct a 2-tape Turing machine with no more than 5 states
(including q_a and q_r) for this language, and simulate the string
00#000. Links to q_r are not needed. Note that the transition
function δ of multitape Turing machine is
k k
Ｑ × Γ → Ｑ × Γ × {Ｌ,Ｒ,Ｓ} ,
where k is the number of tapes.