※ [本文轉錄自 NTU-Exam 看板 #1KkrPdqp ]
作者: irritum (働いたら 負け) 看板: NTU-Exam
標題: [試題] 103上 林智仁 自動機與形式語言 第一次期中考
時間: Sun Jan 18 14:44:48 2015
課程名稱︰ 自動機與形式語言
課程性質︰ 必修
課程教師︰ 林智仁
開課學院： 電資學院
開課系所︰ 資訊工程
考試日期（年月日）︰ 2014/10/28
考試時限（分鐘）：
試題 :
‧Please give details of your calcultatoin. 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 other's class notes.
‧Try to work on easier question first.
Problem 1 (25%)
1. Consider the following language of having only one string:
{a}
Assume Σ = {a}, what is the DFA diagram with the samllest number of states
for this language ? Give the formal definition.
2. Prove why yours has "the smallest number of states" ?
3. Now consider two languages:
A = {a}, with Σ_A = {a},
B = {b}, with Σ_B = {b},
We would like to prove that
A∪B
is regular. Before introducing DFA, in our lecture (or in the textbook), we
construct a DFA with states like (q,r), where q is from that of the first
machine and r is from the other. However, in that construction, we assume
that A and B have the same Σ.
Please modify your DFA for A in 1., so that it handles the language :
{a}, with Σ = {a,b}
4. After 3., we can use a similar setting for {b}, with Σ = {a,b}. Then use
the procedure in our lecture to construct a DFA for A∪B.
5. Give a DFA with the smallest number of states for A∪B. Can you reduce the
DFA in 4. to your DFA here?
Problem 2 (15%)
Consider the following regular expression
(a∪b)*
Assume Σ = {a,b}
1. What is the DFA with the smallest number of states for this language ?
2. Starting with the following NFA.
┌─┐ a, b ╔═╗
start →│q1│───→║q2║
└─┘ ╚═╝
Use the procedure in the text book to prove that A* is regular to generate a
three-state NFA. Let's follow the textbook to have ε-links from the accept
states to the original start state. Give the formal definition of this
three-state NFA.
3. Convert the three-state NFA to an eight-state DFA by using the power set of
NFA's states as the new set of states. Can the eight-state DFA be simplified
to the DFA obtained in 1. ?
Problem 3 (20%)
Consider the following state diagram:
1
╔═╗←───╔═╗ 0 ╔═╗ 1 ┌─┐
start →║q1║ ║q2║───→║q3║───→│q4│
╚═╝───→╚═╝ ╚═╝ └─┘
↑│ 0 ↑│ ↑│
└┘ └┘ └┘
1 0 0,1
1. (5%) What is the language of this DFA ?
2. (8%) Modify this DFA to GNFA and find the regular expression of the
language. Please follow the order q1, q2, q3, q4 to remove states.
3. (7%) Can you see that the results in 2. correspond to the language described
in 1. ? Prove it !
Problem 4 (20%)
1. Assume L is regular. Is the following language regular ?
_ R
L = { w | w ∈ L of w ∈ L }
R
where w is the reverse of w. Please prove your answer.
2. Is the following language regular ?
n!
L = { a | n ≧ 0 }
Please prove your answer.
Problem 5 (20%)
In our proof of that
n n
A = { 0 1 | n ≧ 0 }
is not regular, we demonstrate that we can use only two of the three
consditions :
i
i. x y z ∈ A, ∀i
ii. |y| > 0
n^2
1. For proving that { 1 | n ≧ 0} is not regular, is it possible to use
also only the above two conditions?
2. Is it possible to prove that a language is not regular by using only
i
i. x y z ∈ A, ∀i
ii. |xy| ≦ p
or
i. |y| > 0
ii. |xy| ≦ p