Spring 2001, CSE 428: Quiz 1.1 - 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 ::= aSb | ab
    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 even length
    4. The language containing only the string ab
    5. The language of all the strings of the form   ab, abab, ababab,   etc.

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

    1. The grammar generates two different strings
    2. There are two different derivations for the same string
    3. There are two different derivation trees for the same string
    4. There are two strings with the same derivation tree
    5. There are two different syntactic categories generating 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 left associative
    2. "^" has precedence over "-"
    3. The grammar is unambiguous

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

    1. 10
    2. 1 - 2

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