CS4123 Theory of Computation. B-2002
Solutions Quiz 1 - November 7, 2002

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

Instructions


Problem I. Variants of Turing Machines (10 points)

A Left-Right-Stay Turing machine is similar to an ordinary Turing machine except that its head can move Left (L), Right (R), or Stay put (S). In other words, its transition function is defined as:
delta : Q x Gamma -> Q x Gamma x {L,R,S},
where S means that the head does not move.
Prove that this variant of Turing machines is equivalent to the ordinary Turing machines. That is, prove the following two facts.
  1. (3 points) Given any ordinary Turing machine M, one can construct a Left-Right-Stay Turing machine that simulates M.
    Let's construct a Left-Right-Stay Turing machine T that simulates M.
    Note that since M uses only capabilities of ordinary TMs and
    Left-Right-Stay machines have those plus more capabilities, then
    we can construct T equal to M.
    
    

    Clearly T is a Left-Right-Stay TM that simulates M.

  2. (7 points) Given any Left-Right-Stay Turing machine T, one can construct an ordinary Turing machine that simulates T.
    
    Let's construct an ordinary Turing machine M that simulates T. 
    Assume that the state-diagram of T =  is given. 
    Let's construct the state-diagram of M = .
    
    
    1. QM = QT union QS (I'll explain what QS is below)

    2. SigmaM = SigmaT

    3. GammaM = GammaT

    4. deltaM = QM x GammaM -> QM x GammaM x {L,R} We need to translate any transition (qi,a)->(qj,b,L/R/S) in deltaT into a valid transition in deltaM, where qi and qj are arbitrary states in QT and a and b are arbitrary symbols in GammaT. If the transition in deltaT is of the form (qi,a)->(qj,b,L/R), that is, it moves the head Left or Right, then we include exactly the same transition into deltaM. If the transition in deltaT is of the form (qi,a)->(qj,b,S), that is, it keeps the head still, then we include both of the following two transitions into deltaM:
      • (qi,a) -> (qij,b,R), and
      • (qij,x) -> (qj,x,L), for each character x in GammaT
      Here, qij is a new state that is included in QS (and hence in QM). Therefore, we get to keep the head still by moving it once to the right and immediately after once to the left. (Note that moving the head once to the left and immediately after once to the right doesn't work since the head wouldn't stay in the same position if the head is originally pointing to the "triangle" at the left-end (i.e. beginning) of the tape.)

Problem II. Decidable languages (10 points)

Let Sigma = {a,b,c}. Show that the following language over Sigma is decidable

L = { w in Sigma* | w contains the same number of occurrences of a's, b's, and c's}

by implementing a Turing machine that decides this language. Note that "bbacbcaac" and "" (the empty word) belong to L, but "babca" doesn't.

  1. (2 points) Briefly describe in words the behavior of your machine. State what symbols belong to Gamma (the tape alphabet).
    I'll describe several possible ways of solving this problem.
    I'll include below the state-diagram for jsut one of the alternative
    approaches, though.
    
    Approach 1:
    
    Gamma = Sigma union {triangle, blank, X}
    
    I'll use an ordinary TM to solve this problem. Initially the input word
    is written on the tape and the head is pointing to the first character.
    I'll move the head to the right looking for the first non-blank character.
    If blank is found, the word is accepted (the input word is the empty word).
    Otherwise, I mark the character I found (it can be an a, a b, or a c) with 
    an X. Then, continue moving to the right looking for a character different
    from the one I just marked. If I don't find it (i.e. I reach a blank at the 
    end of the input string), I reject. If I find it, I mark it with an X.
    Then, continue moving to the right looking for a character different
    from the two characters I just marked. If I don't find it (i.e. I reach a 
    blank at the end of the input string), I reject. If I find it, I mark it 
    with an X and rewind the tape. I repeat this process until either the
    process above rejects the input or all the characters on the tape have been 
    marked, in which case I accept the input.
    
    Approach 2:
    
    Gamma = Sigma union {triangle, blank, X}
    
    I'll use an ordinary TM to solve this problem. Initially the input word
    is written on the tape and the head is pointing to the first character.
    If the head is pointing to a blank, the word is accepted (the input word 
    is the empty word). Otherwise, I'll move the head to the right looking for 
    an a. If I don't find it (i.e. I reach a blank at the end of the input 
    string), I reject. If I find it, I mark it with an X.
    I rewind the tape.
    Then, I move the head to the right looking for a b. If I don't find it 
    (i.e. I reach a blank at the end of the input string), I reject. If I find 
    it, I mark it with an X.
    I rewind the tape again.
    Then, I move the head to the right looking for a c. If I don't find it 
    (i.e. I reach a blank at the end of the input string), I reject. If I find 
    it, I mark it with an X.
    I rewind the tape again and repeat this process until either the
    process above rejects the input or all the characters on the tape have been 
    marked, in which case I accept the input.
    
    Approach 3:
    
    Gamma = Sigma union {triangle, blank}
    
    I'll use a 4-tape Turing machine. Initially the input word is written on 
    the 1st tape and the 1st head is pointing to the first character.
    If the head is pointing to a blank, the word is accepted (the input word 
    is the empty word). Otherwise, I'll start processing the input word as follows.
    If the 1st head is pointing to an a, then I write an a on the 2nd tape and move 
    the 1st and the 2nd heads to the right once (the other two heads stay put).
    If the 1st head is pointing to a b, then I write a b on the 3rd tape and move 
    the 1st and the 3rd heads to the right once (the other two heads stay put).
    If the 1st head is pointing to a c, then I write a c on the 4th tape and move 
    the 1st and the 4th heads to the right once (the other two heads stay put).
    I repeat this process until the 1st head reaches a blank (end of input).
    Then I start moving the 2nd, 3rd, and 4th heads simultaneously to the left.
    If they all hit the beginning of their respective tapes (triangles) at the
    same time, then I accept the word otherwise I reject it.
    
    See David Loose's solution below. He followed this approach.
    
  2. (8 points) Provide a state-diagram for your Turing machine. Remember to make all the transitions explicit in the diagram.

    The following is the state-diagram for Approach 1 above.


    Here is David's Loose's excellent solution. He followed Approach 3 described above.

    Solution by David Loose:

    1. (2 points) Briefly describe in words the behavior of your machine. State what symbols belong to Gamma (the tape alphabet).

      The Turing machine will have 4 tapes: 1 for input and one each for a's, b's and c's.  Each of these will be able to stay place.  For every a read from input on x will be placed on the a tape.  b's and c's will be marked on their respective tapes with a x as well.  At the end the tapes will read left.  If a left end marker is found before the others are done, the TM will reject.  Otherwise, it accepts.

       

    2. (8 points) Provide a state-diagram for your Turing machine. Remember to make all the transitions explicit in the diagram.

    Here is the state diagram: