University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page
Course Page

CSC 456/656 Assignment 3

Due date: Wednesday, February 20, 2018, 11:30 AM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.

Two of the most important classes of context-free grammars are the algebraic and the programming style grammars.
Exercise 2.27 gives a context-free grammar for a programming style language.
  1. Work Exercise 2.1 on page 154 of the third edition.
    Exercise 2.1 on page 128 of the second edition.
    Exercise 2.1 on page 119 of the first edition.
    This is an example of an algebraic language.
  2. Work Exercise 2.4 part (e) on page 155 of the third edition.
    Exercise 2.4 on page 128 of the second edition.
    Exercise 2.4 part (f) on page 120 of the first edition.
  3. Work Exercise 2.8 on page 129 of the second edition.
  4. The following context-free grammar, G, generates an algebraic language, where all variables are one letter, which is either x, y, or z. The start symbol of G is E.
    1. E ⟶ E + E
    2. E ⟶ E - E
    3. E ⟶ - E
    4. E ⟶ E * E
    5. E ⟶ (E)
    6. E ⟶ x
    7. E ⟶ y
    8. E ⟶ z
    Prove that G is ambiguous by writing two leftmost derivations for the string x + y + z. Which one of those would be considered "correct"?

Back to Course Page