※ [本文转录自 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.