※ [本文轉錄自 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