Answers to Problem Set #5

CS 154
May 17, 2005

  1. The table is given at left below. The S entry in the top row means that the given string is generated by the grammar. This entry is licensed by the rule S -> AB and the values k = 2, 3, and 4, and also by the rule S -> BA and the value k=1. One parse tree corresponding to these cases isgiven at right below; other parse trees are possible. 
    A,B,S                               S                S              S           S
A,S   A,B,S                        / \              / \            / \         / \
A,S     A   A,B,S                 A   B            A   B          A   B       B   A
A,S     A     A   B,S            / \ / \          / \  /\        / \  |       |  / \
B,C    A,C   A,C  A,C  B,C       C A C  B        C  A  C B      C   A b       b A   S
                                 | | |  /\       | /\  | |      |  / \          |  / \
                                 b a a C  B      b C A a b      b  C  A         a A   S
                                       |  |        | |             | / \          |  / \
                                       a  b        a a             a C A          a A   B
                                                                     | |            |   |
                                                                     a a            a   b

  2. The construction of part (c) would give a CFG with the following rules: 
      E -> T | TX
  X -> +T | -T | +TX | -TX  
  T -> F | FY
  Y -> *F | *FY  
  F -> x | y | (E)
    A parse tree for x+(x*y)-y in this grammar is given below. 
              E
        /   \
       T     X
       |   / | \
       F  +  T  X
       |     |  | \
       x     F  -  T
            /|\   / \
           ( E ) -   T
             |       |
             T       y
            / \
           F   Y
           |  / \
           x *   F
                 |
                 y
    EXTRA CREDIT: For the CFG G, if the variables are ordered E, X, T, Y, F, then the construction given by the rest of the exercise is similar to the above, and gives the same result, except that the F rules (recalling that there are no longer any parentheses) are replaced by 
      F -> x | y | xZ | yZ
  Z -> *F | *FY | +T | -T | +TX | -TX | *FX | *FYX | *FZ | *FYZ | +TZ | -TZ | +TXZ | -TXZ | *FXZ | *FYXZ
    The leftmost derivation becomes 
      E => T => FY => xZY => x+TY  => x+FY => x+yY => x+y*F => x+y*z

  3. A table for one appropriate TM is given below. Here state q0 checks for the leading 1, state q1 looks for the right end of the string, state q2 performs the subtraction by changing 0's to 1's and moving left until it finds a 1 that it can change to 0 (note that if the TM reaches state q2 there will always be such a 1), state q3 looks for the left end of the input, and state qf is the accepting state.

    δ
    0
    1
    B
    q0   (q1, 1, R)  
    q1 (q1, 0, R) (q1, 1, R) (q2, B, L)
    q2 (q2, 1, L) (q3, 0, L)  
    q3 (q3, 0, L) (q3, 1, L) (qf, B, R)
    qf      

  4. Yes, it would accept (and halt). The pieces of the input string would be interpreted as follows:
      010100010100       the move (q3, 0, R) ε δ(q1, 0) 
  11                 separator between moves
  0001010010100      the move (q2, 0, R) ε δ(q3, 0) 
  11                 separator between moves
  0001001000100100   the move (q3, 1, R) ε δ(q3, 1) 
  111                separator between last move and input 
  0101               the input to the TM with moves given above
    So the universal TM would simulate the accepting computation 
      q10101 ⊢ 0q3101 ⊢ 01q301 ⊢ 010q21
    for the string 0101.

    5. GRADING SCALE: 35 A-, 30 B-, 25 C-, 20 D-