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>| 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>| 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>| G is a CFG and ||L(G)|| > n},
     is decidable for n = 0, 1, 2, ...

  b. Show that INT_cfg, defined as {<G,G'>| G, G' are CFGs & L(G), L(G')
     are not disjoint} is Turing-recognizable (recursively enumerable).
  

Problem 3
~~~~~~~~~
  Prove that #CFG[<n], defined as {<G>| 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 <M,w> 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 <M,w>.) In other words, it behaves for
     <M,w> 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,w>| M is a TM which eventually prints a 1 given input w} is 
  undecidable.