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.

  1. Work Exercise 2.11 on page 129 of your textbook.
Work the following problems, but do not hand them in.
  1. Prove that there is no deterministic PDA that accepts the language of all palindromes over {a,b}.
  2. Is there a deterministic PDA that accepts the language given in Exercise 2.6 on page 129?
    1. Prove that the following grammar is ambiguous by giving two different leftmost derivations of some string.
      1. S -> a
      2. S -> bLn
      3. S -> wS
      4. S -> iS
      5. S -> iSeS
      6. L -> SL
      7. L -> (epsilon)
    2. Find an unambiguous context free grammar equivalent to that grammar.
  3. 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.
    1. Prove that L2 is context free.
    2. Prove that L1 is not context free.

Back to Assignment Page
Back to Course Page