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

Solution

  1. The right answer is 2: The language of all non-empty strings on {a,b} with the same number of a's and b's and where all the a's come before all the b's

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

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

    1. 10: not derivable
    2. 1 - 2: derivable 

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