Formal languages and theory of computation, part 2
CS 288
May 9, 2005

  1. Recall that a context-free grammar is in Chomsky Normal Form iff the right-hand side of each rule consists of a single terminal or two variables (that is, two nonterminals).

    a) Find a grammar in Chomsky Normal Form that generates that same language as the grammar with start symbol E and rules

    E → E+E | E*E | (E) | x | y

    b) How many nodes (including leaves) are there in a parse tree for a string of length n if the underlying grammar is in Chomsky Normal Form?

    c) What is the asymptotic nondeterministic time complexity, as a function of n, of parsing a string of length n for a grammar in Chomsky Normal Form? Justify your answer. Note that this problem is not a decision problem.

    d) What is the (deterministic) time complexity, as a function of n, for determining whether a given string of length n is generated by a given grammar in Chomsky Normal Form, using the CYK algorithm?

     

  2. Describe briefly a decision algorithm, if one exists, for determining whether
    a) L(G) is empty given a CFG G
    b) L(M) is empty given a DFA M
    c) L(M) is empty given a PDA M
    d) L(M) is empty given a TM M
    e) L(M) is infinite for a DFA M
    In cases where you say there is no such algorithm, give a brief justification of your answer. If your algorithm invokes another algorithm, you need only specify what this other algorithm does -- you needn't give details of how it works.

     

  3. An instance of the SUBSET-SUM problem is an integer J and a set S of n items, each with an integer weight. The question is whether there is a subset of S such that the sum of the weights of the items in the subset equals J.

    a) Give a brief argument to show that the SUBSET-SUM problem is in NP.

    Given an instance I of 3SAT, it is possible to define an instance T(I) of SUBSET-SUM. For example, suppose that I is the conjunction of C4, C3, C2, and C1 and 

     C4 = x1 ∨ x2' ∨ x3',         C3 = x1' ∨ x2' ∨ x3',         
 C2 = x1' ∨ x2' ∨ x3,         C1 = x1 ∨ x2 ∨ x3

    Then for each number in T(I) the leftmost three digits from left to right correspond to the variables x3, x2, x1, the next four correspond to the four clauses of I (in the order given above), and the last digit is always 0. The target value J is 11144440, and the elements of the set S and their (decimal) weights are 

      v1: 00110010
  v2: 01000010
  v3: 10000110
  w1: 00101100
  w2: 01011100
  w3: 10011000
  p1: 00000010
  p2: 00000100
  p3: 00001000
  p4: 00010000
  q1: 00000020
  q2: 00000200
  q3: 00002000
  q4: 00020000
    The idea of the construction is that a solution for T(I) would contain vi if xi is assigned value 1 in a corresponding satisfying assignment for I, and would contain wi otherwise. In general, S = V ∪ W ∪ P ∪ Q, where |V| = |W| = the number of variables in I, and |P| = |Q| = the number of clauses in I. And all digits of the weights of members of S are 0 except that 
    vi contains a 1 in the 10j position iff j<=|P| and xi appears in Cj, or j = |P| + i
wi contains a 1 in the 10j position iff j<=|P| and xi' appears in Cj, or j = |P| + i
pi contains a 1 in the 10i position 
qi contains a 2 in the 10i position
    Also, 
    J contains a 1 in the 10j position iff j>|P|
       and a 4 in the 10j position iff 0<j<=|P|
    b) For the SUBSET-SUM instance given above, find the solution corresponding to the satisfying assignment x1 = 1, x2 = 0, x3 = 0 for the given instance of 3SAT. You will get partial credit if you find a different solution.

    c) Find T(I) for the 3SAT instance where I is the conjunction of C3, C2, and C1 and 

     C3 = x1 ∨ x2 ∨ x3',    C2 = x1 ∨ x2' ∨ x3,       C1 = x1' ∨ x2 ∨ x3'

    d) With T defined as above, show that the answer to an instance I of 3SAT is "yes" if and only if the answer to the solution T(I) of SUBSET-SUM is "yes".

    e) What, if anything, besides (a) and (d) has to be shown to show that SUBSET-SUM is NP-complete, given that 3SAT is NP-complete?