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

Please write your Name, Student ID, and Section at the top of the page.
  1. [Points 2] What is the language generated by the following grammar (only one answer please) 
       S ::= bSb | a
    1. The language of all non-empty strings on {a,b} with the same number of a's and b's
    2. The language of all the non-empty strings with the same number of a's and b's and where all the a's come before all the b's
    3. The language of all the strings of the form   b, baba, bababa, babababa,   etc.
    4. The language of all the strings of the form   a, bab, bbabb, bbbabbb,   etc.
    5. The language of all the non-empty strings on {a,b} of odd length
    6. The language of all the strings containing one a and an arbitrary number of b's

  2. [Points 1] A grammar is ambiguous if (only one answer please)

    1. There are two different syntactic categories generating the same string
    2. The grammar generates two or more different strings
    3. There are two strings with the same derivation tree
    4. There are two different derivation trees for the same string
    5. There are two different derivations for the same string

  3. [Points 3] Consider the following grammar, where A is the start symbol: 
       A ::= A - B | B
   B ::= C ^ B | C
   C ::= 0 | 1 | 2
    For each of the following assertions, say whether it is true or false

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

  4. [Points 2] For each of the following strings, say whether it can be derived from the grammar in Question 3.

    1.       2 ^ 2 ^ 2
    2.       16

  5. [Points 2] Given the grammar in Question 3, draw the derivation tree for the string   1 ^ 2 ^ 0