Homework 1 [ ps | pdf | LaTeX source] out, due February 12 at 5PM.
To get started typing up your solutions, use this LaTeX shell for Homework 1. The LaTex shell requires the use
of 6045preamble.tex.
Homework solutions for this class MUST be typed.
We highly recommend that you use LaTeX.
Here is a useful document on how to use LaTeX.
One more useful LaTeX website is this one.
Homework 2 out ( [ ps | pdf | LaTeX source ]); will be due on Tue Feb 20. You might want to use the Xfig program to generate some of the figures (of the FAs etc.). Here is a comprehensive Xfig manual.
Reading: Computation histories (see page 176) and Sections 5.2
Handout 6 : A photocopy of Section 8.5 from "Introduction to Automata Theory, Languages and Computation" by Hopcroft, Motwani and Ullman will be distributed in the class. NOT AVAILABLE ON THE WEB.
Undecidability. Computation histories. Post Correspondence Problem.
Friday, May 25, 9:00am-12:00pm (Noon) at Walker. Be on time!
NOTE: MOST OF THE SOLUTIONS APPEARING ON THIS PAGE ARE BORROWED FROM SUSAN HOHENBERGER (2004) AND VINOD VAIKUNTANATHAN (2005).
Last modified: Monday, May 21st, 2007