课程名称︰计算理论 Theory of Computing
课程性质︰选修
课程教师︰颜嗣钧
开课学院：电资学院
开课系所︰电机所
考试日期（年月日）︰2017/11/07
考试时限（分钟）：170
试题 :
Theory of Computation
Fall 2017, Midterm Exam. (Nov. 7, 2017)
1. (20 pts) Let Σ = {0, 1}, answer the following questions (True or False)
and prove your answer:
(a) the set of nonpalindromes (i.e., Σ* - {w | w = w^R, w ∈ Σ*})
is nonregular;
(b) the set of odd-length strings with middle symbol 0 is regular;
(c) the set of strings that contain a substring of the form 'wuw' where
u ∈ Σ*, w ∈ Σ^+ is nonregular;
(d) the set of strings with the property that in every prefix, the number
of 0s and the number of 1s differ by at most 2 is regular;
(e) if L is nonregular and both of L' and L∩L' are regular, then L∪L'
is nonregular.
2. (16 pts) Let A = {xx | x ∈{a, b}*}, and h: {a, b}* → {a, b}* be a
homomorphism with h(a) = h(b) = a.
(a) What is h(A)?
(b) What is h^(-1)(A)?
(c) What is h^(-1)(h(A))?
(d) What is h(h^(-1)(A))?
3. ( 9 pts) Given Σ = {a, b}, we define Two(x) to be an operation doubling
each symbol in x ∈ Σ*. For instance, Two(abab) = aabbaabb, Two(aab) =
aaaabb.
(a) Define Two(x) recursively.
(b) Given a language L, define Two(L) = {x | Two(x), x ∈ L}. Prove that
if L is regular, so is Two(L).
4. ( 5 pts) Consider the following operations:
prefix(L) = {u | uv ∈ L, ∃v ∈ Σ*};
suffix(L) = {v | uv ∈ L, ∃u ∈ Σ*};
reverse(L)= {x | x^R ∈ L}.
Use the closure of regular languages under the reverse and prefix
operations to prove that suffix(L) is regular whenever L is regular.
5. ( 5 pts) Use the Myhill-Nerode theorem to show that for any positive
integer m, no DFA with less than m states recognizes
A_m = {1^k | m divides k} (⊆{1}*).
6. (10 pts) Let L be an infinite regular language. Prove that L can be
partitioned into two disjoint infinite regular languages, i.e.,
L = L_1∪L_2, L_1∩L_2 = Φ, and L_1, L_2 are infinite regular languages.
(Hint: Use the pumping lemma.)
7. (10 pts) Consider the following grammar G, where S, A are nonterminals,
and a, b are terminals:
S → aSA | ε ; A → bA | ε
Answer the following questions:
(a) Is L(G) regular? Why?
(b) Is G ambiguous? Explain your answer.
8. (10 pts) True or False? Score = max{0, Right - ½ Wrong}. No explanations
are needed.
Here are four regular expressions over the alphabet {a, b}:
E_1 = (ab+a*b*b*)*
E_2 = ((ab)*(a*b*b*)*)*
E_3 = (a+b)*
E_4 = a(a+b)*
(1) L(E_2) = L(E_3)
(2) L(E_3) = L(E_4)
(3) L(E_1) = L(E_4)
(4) The minimal DFA for L(E_1) has five states.
(5) The minimal DFA for L(E_4) has two states.
9. (10 pts) Use the pumping lemma to prove that the following language is
not regular:
L = {0^m 1^n | m ≦ 2n + 5, m,n ∈ Ν}.
10.( 5 pts) We say that a DFA M for a language A is minimal if there does
not exist another DFA M' for A such that M' has strictly fewer states
than M. Suppose that M = (Q, Σ, δ, q_0, F) is a minimal DFA for A.
Using M, we construct a DFA M_bar for the complement A_bar as
M_bar = (Q, Σ, δ, q_0, Q-F).
Is M_bar is a minimal DFA for A_bar? Why?