CS4123 Theory of Computation. B-2002
Exam 1 - November 15, 2002

Prof. Carolina Ruiz.
Department of Computer Science.
Worcester Polytechnic Institute.

NAME: Carolina Ruiz and Adam Elliot

Instructions


Problem I. Decidable and Semi-decidable Languages (Score: _______ out of 20 points)

Let Sigma be an alphabet.
  1. (20 points) Show that the set of decidable languages is closed under intersection. That is, show that if L1 and L2 are decidable languages, then L1 intersection L2 is a decidable language.
    Remember that L1 intersection L2 = { w in Sigma* | w belongs to L1 AND w belongs to L2}.
    Let M1 be a TM that decides L1 and
    let M2 be a TM that decides L2.
    
    The following TM M decides L = L1 intersection L2:
    
    Let M = "on input string w:
    
    1. Run M1 and M2 in parallel (or one after the other).
    2. If both M1 and M2 accept w, then accept w.
    3. If either one rejects w, then reject w.
    Let's prove that the Turing machine M above decides the language L1 intersection L2. M accepts w iff both M1 and M2 accept w iff w belongs to L1 AND w belongs to L2 iff w belongs to L1 intersection L2. M rejects w iff either M1 or M2 or both reject w iff w doesn't belong to L1 and/or w doesn't belong to L2 iff w doesn't belong to L1 intersection L2. Note that the machine M is guaranteed to halt, since M1 and M2 are deciders and so guaranteed to halt on all inputs.
  2. (OPTIONAL 10 points) Show that the set of semi-decidable languages is closed under intersection. That is, show that if L1 and L2 are semi-decidable languages, then L1 intersection L2 is a semi-decidable language.
    Let S1 be a TM that semi-decides L1 and
    let S2 be a TM that semi-decides L2.
    
    The following TM S semi-decides L = L1 intersection L2:
    
    Let S = "on input string w:
    
    1. Run S1 and S2 in parallel.
    2. If both S1 and S2 accept w, then accept w.
    3. If either one rejects w, then reject w.
    4. (Note that if both S1 and S2 "loop" on input w, then S will have to loop with them.)
    Let's show that S semi-decides L = L1 intersection L2: S accepts w iff both S1 and S2 accept w iff w belongs to L1 AND w belongs to L2 iff w belongs to L1 intersection L2. Note that the machine S may loop on input w if both S1 and S2 loop on w (tough we could have chosen to let S loop if one of these machines loops on w and the other one rejects w and still S would be semi-decider for L). However, if w belongs to L1 intersection L2, then both S1 and S2 halt and accept w and so S is guaranteed to halt accepting input w.

Problem II. Primitive Recursive Functions (Score: _______ out of 30 points)

  1. (10 points) Let pw2(n) denote "2n", that is "2 to the nth power". For instance, pw2(0)=1 and pw2(5)= 32. Show that the pw2 function is primitive recursive.
    Here are two possible solutions to this problem:
    
    Solution 1:
    Define pw2 by inductive definition as follows:
    
     pw2(0) = 1
     pw2(succ(n)) = mult(succ(succ(0)),pw2(n))
    
    Since mult and succ are primitive recursive as proven in class (and
    handout), and inductive definition preserves the property of being
    primitive recursive, pw2 is primitive recursive. 
    
    Solution 2:
    Define pw2 by inductive definition as follows:
    
     pw2(n) = exp(succ(succ(0)),n)
    
    where exp(x,y) is the exponentiation function xy 
    proven to be primitive recursive in class (and handout).
    Since pw2 is defined as the composition of succ and exp
    then pw2 is primitive recursive.
    
  2. (10 points) Let log2(n) denote "the integer part of the base2 logarithm of n". In other words, log2(n) is the maximum value for which 2log2(n) is less than or equal to n. For instance, log2(32) = 5, and log2(11) = 3. By convention, let's assume that log2(0) = 0. Show that the log2 function is primitive recursive.

    (Hint: If you wish, you can use the fact that bounded minimization preserves the property of being primitive recursive. If you wish, you can disregard this hint.)

    Here are two possible solutions to this problem:
    
    Solution 1:
    Define log2 using bounded minimization as follows:
    
      log2(n) = mun z [ greater_than(pw2(succ(z)), n) ]
    
      where:
    
      "mun z" means "the least number z less than or equal to n"
    
      greater_than(x,y) = mult(geq(x,y), not(equal(x,y)))
    
    Since succ, mult, not, equal were shown to be primitive recursive in
    class and/or handout and/or hw1, pw2 was shown to be prim. rec. above
    and bounded minimization preserves the property of being primitive 
    recursive, then log2 is primitive recursive.
    
    
    Solution 1:
    Define log2 using a helper function helper_log2:
    
      log2(n) = helper_log2(n,n)
    
    The helper function is defined using inductive definition as follows:
    
      helper_log2(n,0) = 0
                                /
                               | k,                 if greater_than(pw2(succ(k)),n)=1
      helper_log2(n,succ(k)) = | 
                               | helper_log2(n,k),  if greater_than(pw2(succ(k)),n)=0
                                \
    
    Since pw2 and greater_than were shown to be prim. rec. above and definition by 
    cases (see proof below) and inductive definition preserve the property of being 
    primitive recursive, then helper_log2 is primitive recursive and so is log2.
    
  3. (10 points) Show that definition by cases preserves the property of being primitive recursive. More precisely, consider the function f: NxNxN -> N defined by cases as follows:
                   /
                   | g(k,m,n),        if p(k,m,n)=1
       f(k,m,n) := |
                   | h(k,m,n),        if p(k,m,n)=0
                   \
    
    where g and h are functions from NxNxN -> N, and p is a function from NxNxN -> {0,1}. Prove that if g, h, and p are all primitive recursive functions, then f as defined above is also primitive recursive.
    
    Solution: 
     
      f(k,m,n) = plus(mult(g(k,m,n),p(k,m,n)), mult(h(k,m,n),not(p(k,m,n))))
    
    The explanation below is adapted from John Shutt's solutions to HW2, D term 2002.
    
      f is constructed by composition from previously shown primitive recursive 
      functions mult, plus, and not (from handout and class and hw2), and 
      functions g, h, and p that are primitive recursive by supposition.  So 
      f is primitive recursive.
    
      If p(k,m,n)=0, then f(k,m,n) = 0*g(k,m,n) + 1*h(k,m,n) = h(k,m,n).
      If p(k,m,n)=1, then f(k,m,n) = 1*g(k,m,n) + 0*h(k,m,n) = g(k,m,n).
      So f is the intended function.
    

Problem III. Decidable Languages (Score: ________ out of 25 points)

Let Sigma be an alphabet. Show that the language

SUBSETrex = {< R,S > | R and S are regular expressions and L(R) is a subset of L(S)}

is decidable.

Solution 1

Proof Idea:
The idea of the proof below is the following: L(R) is a subset of L(S)
iff L(R) intersected with the complement of L(S), L(S)C is the empty set. 
We'll use Theorem 4.4 (or its equivalent for regular expressions) to prove that 
the condition "L(R) intersection L(S)C =  empty set" is decidable.

Proof

The following Turing machine N decides the language SUBSETrex.

"On input string x,
  1. Check that x encodes a pair < R,S > where R and S are regular expressions
    If it does not, then reject x.
  2. Translate R into an equivalent DFA DR and S into an equivalent DFA DS using the procedure given in Theorem 1.28.
  3. Construct a DFA DSC that accepts the language L(DS)C.
  4. Construct a DFA D that is the intersection of DR with DSC. That is, L(D) = L(DR) intersection L(DSC).
  5. Now, run the Turing machine T from Theorem 4.4 (see p154) with input < D > to determine if L(D) is empty. If T accepts < D > (which means that L(D) is empty), then accept x. If T rejects < D > (which means that L(D) is NOT empty), then reject x."

Now we prove that the TM N decides the language SUBSETrex.

ALTERNATIVE SOLUTION 2: Beth's idea Use the fact that L(R) is a subset of L(S) iff L(R) union (LS) = L(S). Construct the union of L(R) and L(S) and use the Turing machine that decides EQDFA in Theorem 4.5 to decide whether or not L(R) union (LS) = L(S). Use these ideas in the construction of a TM that decides SUBSETrex, similarly to what was done in solution 1. ALTERNATIVE SOLUTION 3: Beth's idea Use the fact that L(R) is a subset of L(S) iff L(R) intersection (LS) = L(R). Construct the intersection of L(R) and L(S) and use the Turing machine that decides EQDFA in Theorem 4.5 to decide whether or not L(R) intersection (LS) = L(R). Use these ideas in the construction of a TM that decides SUBSETrex, similarly to what was done in solution 1.

Problem IV. Turing Machines (Score: ________ out of 25 points)

Let Sigma = {a,b}. Show that the set of words of odd length with one b in the middle position is a decidable language. That is, show that the following language over Sigma is decidable

L = { w in Sigma* | the length of w is odd and there is a b in the middle position of w}

by implementing a Turing machine that decides this language. As an illustration, note that "abaabbbab" and "b" belong to the language, but the following words do not: "aabbba", "abaaa", and "" (the empty word).

  1. (5 points) Briefly describe in words the behavior of your machine. State what symbols are in Gamma, the tape alphabet.
    
    Solution: By Adam Elliot.
    
      Gamma={a,b,X,_,triangle} (_ is blank, triangle is start-of-tape symbol, 
                                X is the marker)
    
       1. Make sure the input string is odd-length and contains only a and b:
    
          This approach uses a two-state procedure to search for the end of
          the word, oscillating between a reject and a "continue" state.
    
          So always moving right....
          A. Read an a, b, or blank. If blank, reject.
          B. Read an a, b, or blank. If blank, continue on to 2.
             Otherwise, go back to A.
    
       2. Now verify the middle character is a "b":
    
          Move the head back to the beginning.
          Move right until a non-marked character is found:
          If it's an "a":
            - Mark it with an X.
            - Scan right, until an X or blank is encountered, then move left.
            - If this is an X, then we didn't find a match, which means that
              "a" was the middle character. Reject.
            - Otherwise, mark with X, rewind, repeat.
          If it's a b:
            - Mark it with an X.
            - Scan right, until an X or blank is encountered, then move left.
            - If this is an X, then we just discovered the middle character
              is a b. Accept.
            - Otherwise, mark with X, rewind, repeat.
    
    
    
    Alternative Solution: 
    Construct a non-deterministic Turing machine that non-deterministically
    chooses a b in the input (if no b is found the machine rejects the input
    word) and then checks that the strings in both sides of that b are of
    equal length.
    
  2. (20 points) Provide a diagram of states and transitions for your machine. Remember to make all the transitions explicit in your diagram.
    See Adam's nice state diagram
    In that diagram "S" denotes the triangle at marks the Start of the tape.