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

CSC 456/656 Assignment 4

Due date: Thursday, February 19, 2015, 4:00 PM.

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.

  1. Recall the language L (we'll call it "Algebra I") given in exercise 2.1 of your textbook.
    1. Give the state diagram of a PDA which accepts L. Your PDA must be "bottom-up."
    2. Give the state diagram of a different PDA which accepts L. This PDA must be "top-down."
  2. Let L be the language of all non-empty palindromes over the alphabet {a,b}.
    1. Give a Chomsky Normal Form grammar for L.
    2. Give the state diagram of a PDA which accepts L.
    3. Give an informal reason for believing that there is no deterministic PDA which accepts L.
  3. Let G be the following context-free grammar, with terminal alphabet {a,e,i,w} and start symbol S.

    1. S → a
    2. S → wS
    3. S → iS
    4. S → iSeS

    1. Show that G is ambiguous. This is the dangling else problem.
    2. Give an unambiguous grammar equivalent to G. Possible hints.

Back to Course Page