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

CSC 456/656 Assignment 4
Due date: Tuesday, September 23, 2008, 2:30 PM.
-
Work Exercise 2.11 on page 129 of your textbook.
Work the following problems, but do not hand them in.
-
Prove that there is no deterministic PDA that accepts the language of
all palindromes over {a,b}.
-
Is there a deterministic PDA that accepts the language given in
Exercise 2.6 on page 129?
-
-
Prove that the following grammar is ambiguous by giving two different
leftmost derivations of some string.
-
S -> a
-
S -> bLn
-
S -> wS
-
S -> iS
-
S -> iSeS
-
L -> SL
-
L -> (epsilon)
-
Find an unambiguous
context free grammar equivalent to that grammar.
-
Let L1 = {
an
bn
cn}.
Let L2 be the complement of L1, i.e., all strings
over {a,b,c} which are not in L1.
-
Prove that L2 is context free.
-
Prove that L1 is not context free.

Back to
Assignment Page
Back to
Course Page