This page provides WWW access to various documents concerning
CSC448S/2405S.
Some of these documents are electronic versions of handouts
given to
the class.
Some announcements will also be made on this page.
Please send any comments or questions to the
instructor:
- Charles Rackoff (rackoff
at cs
dot toronto dot edu)
Last updated: April 23, 2012
Announcements
Marks have been posted below.
AIDS allowed on Final Exam: One 8.5 by 11 inch paper,
hand-written on both sides.
Remaining office hours, SF2301C: Thursday April 12, 3-5.
Assignments can be picked up
then, or
from room SF2301D.
Solutions to Assignment 4 have
been
posted below.
Assignment 4 is now complete.
Here is Section 8.6 of the previous
version
of our text, that uses an approach to
proving undecidability results about context-free grammars that
is
similar to what
I did in class.
We will now cover some material about Type 0 and
Context-Sensitive
grammars.
Some of this can be found in an even older version of the text
available on the internet
if you access it from a university machine:
http://portal.acm.org/citation.cfm?id=1096945&coll=GUIDE&dl=ACM&CFID=19913549&CFTOKEN=26910601
We will cover some material from chapters 2,7,8.
(Part of) Assignment 4, and solutions to Assignment 3, have been
posted
below.
Assignment 3 has been posted below.
Solutions to Assignment 2 have been posted below.
Assignment 2 has been posted below.
Solutions to Assignment 1 have been posted below.
A
paper showing
an
exonential blowup may be necessary when going from a DFA to a
regular
expression.
Notes about 2-way DFAs
here.
Assignment 1 has been posted below.
Assignments
and other handouts
Course information sheet
Assignment 1
Assignment 2
Assignment 3
Assignment 4
Grades