※ [本文转录自 NTU-Exam 看板 #1IPYRGmM ]
作者: ibetrayall () 看板: NTU-Exam
标题: [试题] 102上 林智仁 自动机与形式语言 期中考1
时间: Tue Oct 22 15:18:38 2013
课程名称︰自动机与形式语言
课程性质︰
课程教师︰林智仁
开课学院：电资学院
开课系所︰资讯系
考试日期（年月日）︰102/10/15
考试时限（分钟）：10:20 ~ 12:50
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
‧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 (30 pts)
Consider Σ = {a,b} and the following NFA.
start
│
↓
ε┌─→《q1》──┐ε
│ ↓
q3 ←───── q2
ε
↑ │ ↑ │
└─┘ └─┘
b a
1. Give the formal definition of this NFA. (5 pts)
2. Run the input string aabba. You need to show the full tree. (5 pts)
3. Use the procedure described in the textbook (or in the lecture) to
transform this NFA to an 8-state DFA. (5 pts)
4. What is the language of this NFA? (5 pts)
5. What is the simplest NFA for this language? We mean the NFA with the
smallest number of states and links. (5 pts)
6. What is the simplest DFA for this language? We mean the DFA with the
smallest number of states and links. (5 pts)
Problem 2 (10pts)
Convert the following DFA into GNFA and follow the procedure in Section 1.3
of the textbook to obtain the corresponding regular expression.
Please remove the nodes in the order of q1, q2 and q3.
a start b
┌┐ │ ┌┐
│↓ b ↓ b │↓
───→ ───→
《q2》 q1 q3
←─── ←───
a a
Problem 3 (20 pts)
Let Σ = {a,b} and A be a regular language.
1. Define
__
A* = {w | w /∈ A*}.
__
We try to use the following way to construct a machine recognizing A*. Let
M = (Q,Σ,δ,q0,F)
be a DFA recognizing A. Define
_
M = (Q,Σ,δ,q0,Q\F).
_ __
Does M recognize A*? If yes, give a short explaination. If not, give a
counterexample with the smallest number of states.
2. Define
_
A = {w | w /∈ A}.
_
We try to use the following way to construct a machine recognizing A. Let
M = (Q,Σ,δ,q0,F)
be a NFA recognizing A. Define
_
M = (Q,Σ,δ,q0,Q\F).
_ _
Does M recognize A? If yes, give a short explaination. If not, give a
counterexample with the smallest number of states.
Note that in 1. we consider DFA, while in 2. we consider NFA.
Problem 4 (20 pts)
Is the following language regular?
L = {a^(m)b^(nt) | gcd(m-n,t)=1 }, where m,n,t∈N, and m-n>1
Explain your answer clearly.
Problem 5 (20 pts)
Is the following language regular?
L = {a^(m)b^(n)c^(t) | m > n >= 0, t < (m+n)/(m-n) }
Explain your answer clearly.
附注：被《》括住的代表 accept state