CS 341: Foundations of Computer Science II Prof. Marvin Nakayama
Homework 8 Solutions
1. Consider the decision problem of testing whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
Answer: Define the language as
C = {⟨M,R⟩ | M is a DFA and R is a regular expression with L(M) = L(R)}.
Recall that the proof of Theorem 4.5 defines a Turing machine F that decides the language EQDFA = {⟨A,B⟩ | A and B are DFAs and L(A) = L(B)}. Then the following Turing machine T decides C:
T = “On input ⟨M, R⟩, where M is a DFA and R is a regular expression:
1. Convert R into a DFA DR using the algorithm in the
proof of Kleene’s Theorem.
2. Run TM decider F from Theorem 4.5 on input ⟨M,DR⟩.
3. If F accepts, accept. If F rejects, reject.”
2. Consider the decision problem of testing whether a CFG generates the empty string. Express this problem as a language and show that it is decidable.
Answer: The language of the decision problem is
AεCFG = {⟨G⟩ | G is a CFG that generates ε}.
If a CFG G = (V,Σ,R,S) includes the rule S → ε, then clearly G can generate ε. But G could still generate ε even if it doesn’t include the rule S → ε. For example,ifGhasrulesS→XY,X→aY|ε,andY →baX|ε,thenthederivation S⇒XY ⇒εY ⇒εε=εshowsthatε∈L(G),eventhoughGdoesn’tinclude the rule S → ε. So it’s not sufficient to simply check if G includes the rule S → ε to determine if ε ∈ L(G).
But if we have a CFG G′ = (V ′, Σ, R′, S′) that is in Chomsky normal form, then G′ generates ε if and only if S′ → ε is a rule in G′. Thus, we first convert the CFG G into an equivalent CFG G′ = (V ′, Σ, R′, S′) in Chomsky normal form. If S′ → ε is a rule in G′, then clearly G′ generates ε, so G also generates ε since L(G) = L(G′). Since G′ is in Chomsky normal form, the only possible ε-rule in G′ is S′ → ε, so the onlywaywecanhaveε∈L(G′)isifG′ includestheruleS′ →εinR. Hence,if
1
G′ does not include the rule S′ → ε, then ε ̸∈ L(G′). Thus, a Turing machine that decides AεCFG is as follows:
M = “On input ⟨G⟩, where G is a CFG:
1. Convert G into an equivalent CFG G′ = (V ′, Σ, R′, S′)
in Chomsky normal form.
2. If G′ includes the rule S′ → ε, accept. Otherwise, reject.”
3. Let Σ = {0,1}, and consider the decision problem of testing whether a regular expression with alphabet Σ generates at least one string w that has 111 as a substring. Express this problem as a language and show that it is decidable.
Answer: The language of the decision problem is
A = { ⟨R⟩ | R is a regular expression describing a language over Σ containing at least one string w that has 111 as a substring
(i.e., w = x111y for some x and y) }.
DefinethelanguageC={w∈Σ∗ |whas111asasubstring}. NotethatCisa regular language with regular expression (0 ∪ 1)∗111(0 ∪ 1)∗ and is recognized by the following DFA DC:
0
0,1
111
1234 0
0
Now consider any regular expression R with alphabet Σ. If L(R) ∩ C ̸= ∅, then R generates a string having 111 as a substring, so ⟨R⟩ ∈ A. Also, if L(R) ∩ C = ∅, then R does not generate any string having 111 as a substring, so ⟨R⟩ ̸∈ A. By Kleene’s Theorem, since L(R) is described by regular expression R, L(R) must be a regular language. Since C and L(R) are regular languages, C ∩ L(R) is regular since the class of regular languages is closed under intersection, as was shown in an earlier homework. Thus, C∩L(R) has some DFA DC∩L(R). Theorem 4.4 shows that EDFA = { ⟨B⟩ | B is a DFA with L(B) = ∅ } is decidable, so there is a Turing machine H that decides EDFA. We apply TM H to ⟨DC∩L(R)⟩ to determine if C ∩ L(R) = ∅. Putting this all together gives us the following Turing machine T to decide A:
T =
“On input ⟨R⟩, where R is a regular expression:
1. Convert R into a DFA DR using the algorithm in the
proof of Kleene’s Theorem.
2. Construct a DFA DC∩L(R) for language C ∩ L(R)
from the DFAs DC and DR.
3. Run TM H that decides EDFA on input ⟨DC ∩L(R) ⟩.
4. If H accepts, reject. If H rejects, accept.”
2
4. Consider the emptiness problem for Turing machines:
ETM = {⟨M⟩ | M is a Turing machine with L(M) = ∅}.
Show that ETM is co-Turing-recognizable. (A language L is co-Turing-recognizable if its complement L is Turing-recognizable.) Note that the complement of ETM is
ETM = {⟨M⟩ | M is a Turing machine with L(M) ̸= ∅}.
(Actually, ETM also contains all ⟨M⟩ such that ⟨M⟩ is not a valid Turing-machine
encoding, but we will ignore this technicality.)
Answer: We need to show there is a Turing machine that recognizes ETM, the com- plement of ETM. Let s1, s2, s3, . . . be a list of all strings in Σ∗. For a given Turing machine M, we want to determine if any of the strings s1, s2, s3, . . . is accepted by M. If M accepts at least one string si, then L(M) ̸= ∅, so ⟨M⟩ ∈ ETM; if M accepts none of the strings, then L(M) = ∅, so ⟨M⟩ ̸∈ ETM. However, we cannot just run M sequentially on the strings s1, s2, s3, . . .. For example, suppose M accepts s2 but loops on s1. Since M accepts s2, we have that ⟨M⟩ ∈ ETM. But if we run M sequentially on s1, s2, s3, . . ., we never get past the first string. The following Turing machine avoids this problem and recognizes ETM:
R = “On input ⟨M⟩, where M is a Turing machine:
1. 2. 3.
Repeat the following for i = 1,2,3,….
Run M for i steps on each input s1,s2,…,si. If any computation accepts, accept.
3