课程名称︰自动机与形式语言
课程性质︰必修
课程教师︰林智仁
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰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.