PROBLEM SET 6, CSC 280, 2006 DUE BEFORE CLASS, WED. MAR. 8 The sixth problem set is as follows. All 7 problems will be marked out of the same total. Answers to any 6 questions make a complete answer paper. However, you can do all questions to earn bonus points. Note that whenever you are asked to design a TM, what is meant is a 1-tape deterministic TM, unless specified otherwise. Keep your eyes on the instructor's and the TAs' web site for any corrections or discussion. PROBLEM 1 ~~~~~~~~~ a. Prove that {| A is a DFA s.t. L(A) is infinite} is decidable, using a proof that is directly based on the state transition diagrams of DFAs (rather than on use of the emptiness decider for DFAs, as in Sipser's proof on p.185). b. Prove that SUB_dfa defined as {| A, B are DFAs s.t. L(A) is a subset of L(B)} is decidable. You can use theorems taken in class. Problem 2 ~~~~~~~~~ a. Show that #CFG[>n], defined as {| G is a CFG and ||L(G)|| > n}, is decidable for n = 0, 1, 2, ... b. Show that INT_cfg, defined as {| G, G' are CFGs & L(G), L(G') are not disjoint} is Turing-recognizable (recursively enumerable). Problem 3 ~~~~~~~~~ Prove that #CFG[| G is a CFG and ||L(G)|| < n}, is decidable for n = 1, 2, 3, ... (Hint: We can bound the derivation length for nonrecursive CNF grammars.) PROBLEM 4 ~~~~~~~~~ a. Construct a TM (as a state transition diagram, omitting transitions to dead-end states) for recognizing {w^n | n >= 1 and w is a string of form 21...1, i.e., one 2 followed by one or more 1's}. Keep it as simple as you can. b. Construct (as a state transition diagram) a NTM for recognizing {1^n | n is not an odd prime}, keeping the machine as simple as possible. Suggestions: Make use of the machine in (a), and also employ nondeterminism to try to achieve simplicity. (The instructor's solution is a 7-state machine using symbols 0,1,2,#, discounting dead-end states; perhaps you can find a simpler one.) PROBLEM 5 ~~~~~~~~~ A context-sensitive grammar is a quadruple G = (V, Sigma, R, S) where V, Sigma, and S are defined as for CFGs, but rules in R are of form x -> y, where x, y are strings that can use both variable and terminal symbols, except that the RHS y must be at least as long as the LHS x. If the start symbol S does not occur on the RHS of any rule, then a rule S -> e is permitted as well, where e is the empty string. Derivations start with S and are defined much as for CFGs, except that now a step of a derivation is of form vxw => vyw, where x -> y is a rule. Any derivable terminal string is considered to be in L(G). Design context-sensitive grammars for (a) {ww | w is in {0,1}*} and (b) {a^ib^ib^ic^i | i is an integer >= 0}. PROBLEM 6 ~~~~~~~~~ a. A universal TM is a TM which, given as input where M is a TM, accepts [rejects] the input if M accepts [rejects] w, and does not accept the input if M fails to terminate on w. (It also rejects inputs that are not of form .) In other words, it behaves for essentially as M would behave for w. Prove that if U is a universal TM, then {w | U halts on w} is undecidable. b. Prove that if M is a TM that recognizes an undecidable language, then {w | M halts on w} is undecidable. PROBLEM 7 ~~~~~~~~~ Prove that determining whether a TM eventually prints a 1, i.e., {| M is a TM which eventually prints a 1 given input w} is undecidable.