[SOLVED] algorithm CS 341: Foundations of Computer Science II Prof. Marvin Nakayama

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 Kleenes 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
ACFG = {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 doesnt include the rule S . For example,ifGhasrulesSXY,XaY|,andY baX|,thenthederivation SXY Y =showsthatL(G),eventhoughGdoesntinclude the rule S . So its 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 onlywaywecanhaveL(G)isifG includestheruleS inR. Hence,if
1

G does not include the rule S , then L(G). Thus, a Turing machine that decides ACFG 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 Kleenes 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, CL(R) has some DFA DCL(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 DCL(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 Kleenes Theorem.
2. Construct a DFA DCL(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