※ [本文转录自 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