CS 456/656 Assignment 5

Due date: December 1, 2005, 4: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.
  1. Design a Turing Machine that accepts the language of all palindromes over the binary alphabet.
  2. Design a general grammar that generates the language of all strings of length a power of 2 over the unary alphabet {1}.

Back to Course Page