課程名稱︰ 自動機與形式語言
課程性質︰ 資工系必修
課程教師︰ 林智仁
開課學院： 電資學院
開課系所︰ 資工系
考試日期（年月日）︰ 2008.10.16
考試時限（分鐘）： 90分鐘
是否需發放獎勵金： 是
（如未明確表示，則不予發放）
試題 :
Please give details of your calculation. A direct answer withour explanation
is not counted. Your answers must be in English. Please carefully read problem
statements.
1.(20％)
(a) In proving that (√2) is an irrational number, we used the following
property:
2
(n) is even → n is even. (1)
Formally prove (1).
y
(b) Do two irrational numbers x, y exist such that x is a rational number?
Please prove your answer (yes or no).
(√2)
Hint: consider (√2) .
2.(25％)
Assume Σ={a,b}. Consider a regular language A with the following NFA diagram:
→
a↑↓
┌─┐
│q1│
└─┘↖
↗ ↘ ↖ b
a↗ ↘ ↖
↗ a↘ ↖
↗ ↘ ↖
╔═╗ a ┌─┐
→║q0║→→→→→→→→│q2│
╚═╝←←←←←←←←└─┘
ε
Give an NFA diagram which accepts the complement of A:
_
A = {w | w dose not belong to A}.
You don't need to give the formal five-tuple definition.
3.(15％)
Given a regular language A and assume it is represented by (Q1,Σ,δ1,q1,F1).
Let
+
A = {(W1)...(Wk) | k is grater or equal to 1, (Wi) belongs to A }
+ +
Is A regular? If it is, give the formal definition of A (i.e., show what the
+
five-tuple definition of A is).
4.(20％)
Transfer the DFA in Figure 1.14 of the textbook to a GNFA and then obtain a
regular expression. Please remove q1 first, q2 second, and then q0.
We give Figure 1.14 here ( Σ={0,1,2,r} ):
→
0↑↓
┌─┐
│q1│
↙└─┘↖
↙ ↗ ↘ ↖
2,r ↙ ↗ ↘ ↖2
↙ ↗1 1 ↘ ↖
↙ ↗ ↘ ↖
╔═╗ 2 ┌─┐
→║q0║→→→→→→→→→│q2│
╚═╝←←←←←←←←←└─┘
↓↑ 1,r ↓↑
→ →
0,r 0
5.(20％)
Assume Σ={0,1}. Consider the language ψ (empty set).
(a) Give a DFA to recognize the language ψ. Show the transition diagram and
the formal five-tuple definition. We require you to use the smallest
possible number of states. For example, if a 4-state DFA and a 3-state DFA
can both recognize this language, then you should not consider the
4-state one.
(b) Transfer your DFA to GNFA and then get a regular expression (of course
this regular expression should be ψ).
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.229.220.150
※ 編輯: pinkyenyen 來自: 61.229.231.102 (10/18 10:01)