AUCSC 315 / AUMAT 355 Assignment 6

DUE: Wednesday, 3 April 2013, 6:00 p.m.

  1. Working with a non-deterministic PDA.

    1. Problem 12, part (ii), chapter 14 (use the PDA given before problem 12).

    2. Problem 12, part (iv), chapter 14.

    3. Problem 13, chapter 14.

  2. This problem involves working with a language identical to PAREN on the midterm except that the letters a and b are used instead of left and right parentheses (so, if you want, you may use left and right parentheses in your answer for this problem). Note that the empty string, Λ, is included in the language considered in this problem.

    1. Problem 20, part (ii), chapter 14. Your PDA should be deterministic.

    2. Problem 20, part (iv), chapter 14.

  3. Problem 5, chapter 19. I suggest that your TM include a INSERT # command immediately after START (and, if you choose to do this, do NOT include the TM code for this command -- just write INSERT #). This will allow you to easily recognize when you have made one pass to the end of the input string and back (and will help avoid crashing off the left end of the tape).

  4. Problem 20, chapter 19. The easiest way to do this problem is to modify the PALINDROME-accepting TM given on page 442 (which, by the way, can be simplified a bit by combining its states 4 and 7, as we did when we discussed it in class).

  5. Problem 4, chapter 20. Modify the PM for EQUAL given on the same page (i.e. page 477 of Cohen), but be careful: this PM for EQUAL loops forever on some inputs [see problem 2, part (iii) on the same page], and your PM for UNEQUAL will do the same if you are not careful.

  6. Problem 7, part (ii) only, chapter 20. You may not use the READ BACK (i.e. read from the back end of the queue) subroutine for this problem, but you may use the SRC (Shift Right Cyclically) subroutine.

  7. Problem 14, chapter 21. Note that a 2PDA, unlike a PDA, must be deterministic.

Copyright © 2013 William W. Hackborn
Document last modified on