CPSC 289 Sec 502: Quiz 11
April 24, 2007

Printed Name:________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."


  1. (2 pts) What is the difference between an equivalence relation and a partial order?

  2. (1 pt) True or False: The partial order represented by the Hasse diagram below is a lattice.

  3. (2 pt) Consider the regular grammar G = (V,T,S,P), where
    V = {S,A,0,1}
    T = {0,1}
    P consists of the rules S -> 0S | 1A | 1 and A -> 1A | 1.
    Give a derivation for the string 011.