Spring 2001, CSE 428: Quiz 1.2 - 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 (circle only one answer please) 
       S ::= aSa | b
    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 non-empty strings on {a,b} of odd length
    4. The language of all the strings containing one b and an arbitrary number of a's
    5. The language of all the strings of the form   aba, aabaa, aaabaaa,   etc.

  2. [Points 1] A grammar is ambiguous if (circle 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. The grammar is ambiguous
    2. "^" is right associative
    3. "-" has precedence over "^"

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

    1. 0 ^ 0
    2. 21

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