COM S 331: Theory of Computing, Summer 2021
Homework Assignment 7
Due at 11:59PM, Wednesday, June 30, on Gradescope.
You can use high-level descriptions for describing Turing machines.
Problem 25 (25 points). Let L = {〈D〉 | D is a DFA that accepts wR whenever it accepts w }.
Prove L is Turing-decidable.
(Hint: if 〈D〉 ∈ L, then w ∈ L(D) ⇐⇒ wR ∈ L(D). Based on this, if 〈D〉 ∈ L, what is the
relationship between L(D) and L(D)R?)
Solution If 〈D〉 ∈ L, that means ∀x ∈ L(D) ⇔ xR ∈ L(D) ⇔ x ∈ L(D)R, thus L(D) = L(D)R.
We know EQDFA = {〈A,B〉 | A and B are DFAs and L(A) = L(B)} is decidable (theorem 4.5 in
textbook), then we can build a TM M for L with the TM for EQDFA, MEQ as subroutine.
M = “on input 〈D〉:
(i) Build the reverse DFA of D, DR
(ii) Simulate MEQ with 〈D,DR〉 as input
(iii) M accepts 〈D〉 if MEQ accepts 〈D,DR〉, else reject.”
From exam1 question2, we know that if a language is regular then we can build a DFA that rec-
ognize its reverse, hence step (i). Since EQDFA is a decidable language, MEQ will always accept
〈D,DR〉 if L(D) = L(DR), reject otherwise. Thus M will accept 〈D〉 if D accepts wR whenever it
accepts w, reject otherwise. L(M) = L, L is decidable.
Problem 26 (25 points). Prove the language L = {〈R,S〉 | R and S are regular expressions and
L(R) ⊆ L(S)} is Turing-decidable.
(Hint: check Theorem 4.5 in the textbook)
Solution If L(R) ⊆ L(S), then L(S) ∩ L(R) = ∅. We know EDFA = {〈A〉 | A is a DFA and
L(A) = ∅} is decidable (theorem 4.4 in textbook), then we can build a TM M for L with the TM
for EDFA, ME as subroutine.
M = “on input 〈R,S〉,
(i) Build the DFA M ′ for L(S) ∩ L(R)
(ii) Simulate ME with 〈M ′〉 as input
1
(iii) M accepts 〈R,S〉 if ME accepts 〈M ′〉, else reject.”
We know regular languages are closed under complement and intersection, hence step (i) is viable.
Since EDFA is a decidable language, ME will always accept 〈M ′〉 if L(S) ∩ L(R) = ∅, reject other-
wise. Thus M will accept 〈R,S〉 if L(R) is a subset or equal to L(S), reject otherwise. L(M) = L,
L is decidable.
Problem 27 (25 points). Prove that the set of Turing-decidable languages are closed under in-
tersection, i.e., if both L1 and L2 are Turing-decidable, then L1 ∩ L2 is Turing-decidable.
Solution If L1 and L2 are decidable languages, then there must be total (always halt, i.e. accepts
all strings that belong to the language and reject otherwise) TMs such that L(M1) = L1 and
L(M2) = L2. Then we can build a TM M for L1 ∩ L2 with M1 and M2 as subroutine.
M = “on input x,
(i) Simulate M1 with x as input
(ii) If M1 rejects, M rejects x
(iii) If M1 accepts, simulate M2 with x as input
(iv) M accepts x if M2 accepts x, else reject.”
M will accept x if x is accepted by both M1 and M2, reject otherwise. L(M) = L1∩L2 and L1∩L2
is decidable, decidable languages are closed under intersection.
Problem 28 (25 points). Prove the language L = {〈M〉 |M is a Turing machine and |L(M)| ≥ 5}
is Turing-recognizable.
Solution We know Σ∗ is regular, thus Turing-recognizable and has an enumerator that enumerates
it. Let Σ∗ = {s0, s1, s2, …}
M ′ = “on input 〈M〉:
(i) Repeat for i = 0, 1, 2, …
Let j = 0
Enumerate strings s0, s1, …si
Simulate M for i steps on each string s0, s1, …si
If any computation accepts, j++, M ′ accepts 〈M〉 and halt whenever j = 5.”
M ′ will accept 〈M〉 if M accepts 5 or more strings. Thus L(M ′) = L and L is Turing-recognizable.
2