Spring 2001, CSE 428: Quiz 1.2 - 18 Jan 2001

Solution

  1. The right answer is 5: the language of all the strings of the form   b, aba, aabaa, aaabaaa,   etc.

  2. The right answer is 4: A grammar is ambiguous if there are two different derivation trees for the same string

    1. The grammar is ambiguous: false
    2. "^" is right associative true
    3. "-" has precedence over "^" false

    1. 0 ^ 0 derivable
    2. 21 not derivable 

  5.           A
         /|\
        / | \
       A  -  B
       |     |
       B     C
      /|\    |
     / | \   |
    C  ^  B  1
    |     | 
    2     C
          |
          1