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

CSC 456/656 Assignment 3
Due date: Tuesday, February 9, 2010, 2:30 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.
-
Design a PDA that accepts the language of all palindromes over
the alphabet {a,b}. Can you make sure this PDA
is deterministic?
-
Work Exercise 2.9 on page 129 of your textbook.
Exercise 2.9 on page 121 of the first edition.
-
Design an unambiguous context-free grammar for the language of all
algebraic expressions with the following rules.
-
The operations are addition, subtraction, multiplication, and negation, where
negation is unary. Addition uses the symbol
+,
Subtraction and negation both use the symbol
-,
and multiplication uses the symbol
*.
-
There are no constants. The variables are
x,
y,
and
z.
-
There are parentheses.
-
The parse tree of any expression is consistent with the usual
order of evaluation of operators.
For example, in the parse tree for the expression
x + y * z, there will be a subtree whose leaves are
y,
and
*,
and
z,
but there will be no subtree whose leaves are
x,
+, and
y.
-
Additional problems to be added by Thursday, February 4.

Back to
Course Page