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

CSC 456/656 Assignment 5
Due date: Tuesday, October 8, 2013, 1: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.
-
Let Σ = {a,e,i,w} and let G be the context-free grammar whose
start symbol is S, and whose productions are as follows:
-
S → a
-
S → iS
-
S → iSeS
-
S → wS
Let L be the language generated by G.
-
Give a Chomsky normal form grammar equivalent to G.
-
Prove that the string "iwiaea" is in L using the CYK algorithm.
Turn in the worksheet, with all boxes appropriately filled in.
Worksheet in encapsulated postscript
Worksheet in portable document format
-
Fill in the Action and GoTo tables given as Figure 2 in the handout
given in class October 1.
handout in postscript
handout in portable document format

Back to
Course Page