Solutions -- formal languages and theory of computation, part 2, CS 288,
May 3, 2006

    1. no such example is possible -- QBF is PS-complete
    2. no such example is possible
    3. Lu, the universal language, and Ld', the complement of the diagonal language, are two examples of RE languages that are not recursive. There are others.
    4. one such pair of languages is {0m1m2n | m,n > 0} and {0m1n2n | m,n > 0}. Their intersection is just {0m1m2m | m > 0}.

     

  2. One strategy is to show that the two languages are equal as sets. This would involve taking an arbitrary element 0(10)k of the first language, observing that this string equals (01)k0, and thus is a member of the second language. The reverse inclusion would be shown in a similar manner: an arbitrary element of the second language must have the form (01)k0, and thus equals 0(10)k, which is a member of the first language.

    An alternate approach would be to find DFAs accepting the two languages, and show that that the DFAs are isomorphic. Since there is only one minimal DFA (up to isomorphism) that accepts any given language, this is possible to do by converting each expression to an NFA, then to a DFA, and then (if necessary) minimizing.

     

    1. One strategy is to guess, for each node, whether it is in S. This takes O(n) time. Then one checks that |S|=k; this also can be done in time O(n). Note that we may now assume that k<n. Finally, one checks that all pairs of nodes in S are connected by an edge; this can be done in O(nk2) time even in an adjacency list representation. Since k<n, the overall time complexity is polynomial in n, and thus in the length of the instance.

    2. Let G be defined as in the hint. Let k be n-j, where n is as defined in part 1 and j is the integer component of the NODE COVER instance. Then if this instance has a solution T, let S = V - T. Note that since |T| > j, |S| >= k.

      Claim: |S| is a clique. In particular, if |S| > k, then any subset of S of size k is a clique.

      To prove the claim, let v and w be in S. Since neither v nor w is in T, it would violate the definition of a node cover for {v,w} to be an edge of G'. So by definition of G, {v,w} is an edge of G.