作者pinkyenyen (彦彦)
看板NTU-Exam
标题[试题] 自动机与形式语言 期中考
时间Sat Oct 18 09:06:32 2008
课程名称︰ 自动机与形式语言
课程性质︰ 资工系必修
课程教师︰ 林智仁
开课学院： 电资学院
开课系所︰ 资工系
考试日期（年月日）︰ 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)