課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰林智仁
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2011.10.18
考試時限（分鐘）：
試題 :
˙ Please give details of your calculation. 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 (15 pts)
1. Consider the following language
n
A = { 0 1 │ n ≧ 0 }
Give a DFA state diagram for this language (no more than 3 states).
Give the formal definition of your DFA.
2. Consider the following language
n
B = { (10) │ n ≧ 0 }
Give a DFA state diagram for this language (no more than 3 states).
No need to give the formal definition of your DFA.
3. Construct the state diagram of A∪B using the method used in Theorem 1.25
(i.e., the method before we introduced NFA). Please remove unnecessary
states in final answer.
No need to give the formal definition of your DFA.
Problem 2 (15 pts)
1. For any regular language A, consider the following way to generate
language A*.
1. Find a DFA M (Figure 1a) which recognizes language A.
2. Add an edge from each accepting state to the initial state with empty
character.
3. Since we need to accept empty string, the initial state should also be
an accepting state.
4. So we get a new NFA (Figure 1b).
╔═╗ ε ╔═╗
║ ║ ┌───────║ ║
╚═╝ ↓ ╚═╝
┌─┐ ╔═╗
start ─→│q1│ … other … start ─→║q1║ … other …
└─┘ states ╚═╝ states
╔═╗ ↑ ╔═╗
║ ║ └───────║ ║
╚═╝ ε ╚═╝
(a) original DFA M (b) new NFA
Figure 1: A NFA generated from DFA M by the procedure in Problem 2.
Give a DFA M with number of states = 2, such that the language generated by
the procedure above is not A*. You only need to give a state diagram, and
you can assume Σ = {0, 1}.
2. For a general DFA M = (Q_1, Σ, δ_1, q0, F_1), what is the formal
definition of the NFA in Figure 1?
Problem 3 (15 pts)
Consider following NFA:
1
╭╮
0, 1 │↓ 0, ε
┌─┐───→╔═╗───→┌─┐
start ─→│q1│ ║q2║ │q3│
└─┘←───╚═╝←───└─┘
0 1
Please convert this NFA to DFA and remove unnecessary state in final answer.
Problem 4 (20 pts)
Given DFA in Figure 1.14.
0
╭╮
│↓
┌─┐
│q1│
2, r ╱└─┘╲ 1
0, r ╱↗ ↖╲ 0
╱╲ ↙╱ 1 2 ╲↘ ╱╲
↘╔═╗ 2 ┌─┐↙
start ─→║q0║─────→│q2│
╚═╝←─────└─┘
1, r
Σ = {r, 0, 1, 2} and we treat r as a single symbol. Transform it to a GNFA
and then obtain a regular expression by sequentially removing state q2, q1,
and q0.
Problem 5 (15 pts)
Is the following language regular?
i j
L = { 0 1 │ gcd(i, j) = 1 },
where gcd(i, j) means the greatest common divider of i and j. Explain your
answer clearly.
Problem 6 (20 pts)
Is the following language regular?
R +
L = { uww v │ u, v, w ∈ {0, 1} , |u| ≧ |v| },
+
where {0, 1} means the set of strings which are composed of 0 and 1 (ε is
not included). And w^R means the reverse of the string w. Explain your answer
clearly.