课程名称︰自动机与形式语言
课程性质︰必修
课程教师︰林智仁
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰2018.10.22
考试时限（分钟）：10:26 ~ 13:06
试题 :
˙Please write your answers in English.
˙Please give detail of your answers. A direct answer without explanation
is not counted.
˙Read the problem statements carefully.
˙During the exam, you are not allowed to borrow other's notes.
˙The problems may not be ordered according to difficulty. Try to work on
the easier problems first.
Problem 1 (10pts)
Consider the following NFAs, where Σ_N = {a, b}, Σ_M = {b, c}.
N M
┌─┐ a ╔═╗ ┌─┐ b ╔═╗
start ─→│q0│──→║q2║ start ─→│q3│──→║q4║
└─┘ ╚═╝ └─┘<—— ╚═╝
↑│ ε,b b ↑│
｜｜ └┘b,c
Ｖ
╔═╗
║q1║
╚═╝
(a) (5 pts) Construct N・M using the procedure in Theorem 1.47 of the textbook.
(b) (5 pts) Give the formal definition of the resulting NFA.
Problem 2 (50 pts)
Assume Σ= {0, 1}. Consider the language
A = { w ∈Σ* | at least one of the last two characters of w is 1 }
(a) (5 pts) Find an NFA that recognizes A with the smallest number of states.
Give the formal definition and show the tree of running the input
string 110.
(b) (10 pts) Explain wht your solution in (a) has the smallest number of
states. You must clearly explain all details.
(c) (5 pts) Convery your NFA in (a) to a DFA by the procedure in Theorem 1.39
of the textbook.
(d) (10 pts) Simplify your DFA in (c) to have the smallest number of states.
Is there more than one DFA(s) that has the same smallest number of
states and recognizes A? If you think so, find out how many are there;
otherwise, prove that there can be only one DFA that recognizes A with
this number of states. You must clearly explain all details.
(e) (10 pts) Give a regular expression that describes A by applying the method
in Lemma 1.60 of the textbook to convert your DFA in (d) to a GNFA,
and then reducing it to a regular expression. Please remove the start
state of your DFA first.
(f) (10 pts) In the textbook, Lemma 1.60 shows how to convert a DFA to a GNFA.
How about converting a NFA to a GNFA? Try to convert your NFA (a) to a
GNFA, and then reduce it to a rgular expression by the same procedure.
Again, please remove the start state of your NFA first.
Problem 3 (15 pts)
Is the language regular or not?
B = { 1^n | n = 2^k, k ≧0 }
Either provide an NFA that recognizes B and explain why it does, or use
pumping lemma to prove it is not regular.
Problem 4 (25 pts)
Let Σ= {0, 1}. For any w = w_1w_2 ... w_n ∈Σ*, where w_i ∈Σ for 1 ≦i ≦n,
the substring of w are w_{i:j} = w_iw_{i+1} ... w_j, where i ≦j .
Note that we do not consider ε to be a substring here. In particular,
the prefixes of w are w_{1:j} = w_1w_2 ... w_j and the suffixes of w
are w_{i:n} = w_iw_{i+1} ... w_n, for 1 ≦i, j ≦n . Also define 0/1
difference of w to be
d(w) ≡| (number of 0's in w) - (number of 1's in w) |
For example if x = 100111, then d(x) = |2-4| = 2.
(a) (10 pts) Is the language regular or not?
C = { w ∈Σ* | d(w) ≦ 2 }
Either provide an NFA that recognizes B and explain why it does, or use
pumping lemma to prove it is not regular.
(b) (10 pts) Is the language regular or not?
D = { w ∈Σ^n | n ≧ 1 and d(w_{1:j}) ≦ 2 for 1 ≦j ≦n }
Either provide an NFA that recognizes D and explain why it does, or use
pumping lemma to prove it is not regular.
(c) (5 pts) Is the language regular or not?
D = { w ∈Σ^n | n ≧ 1 and d(w_{i:n}) ≦ 2 for 1 ≦i ≦n }
Either provide an NFA that recognizes E and explain why it does, or use
pumping lemma to prove it is not regular.
( Hint: Consider the relationship between D and E )