CISC 303 -- Spring 2013
TR 11:00-12:15pm
Instructor: Vijay Shanker
Office: 442 Smith Hall
Office Hours: Tuesdays 1:30pm -- 2:30pm and Wednesdays --
1:30pm -- 2:30pm
Phone: 831-1952
Email: vijay@cis.udel.edu
TA: Christopher Angelo Sapello
Office: 103 Smith Hall
Office Hours: Mondays and Wednesdays 10:00am -- 11:00am
Email: sapello@cis.udel.edu
Textbook
- Automata and Computability
by
Dexter C. Kozen. Springer, 1997.
Goals
This course introduces automata and formal
language theory. It is a study of the power and the limitations of
different classes of computational systems. Although the material is
theoretical (there will be no programming), much of the material
covered in the course has a
direct impact on the development of algorithms and models in compilers,
networks, natural language systems, as well as other areas in computer
science.
Syllabus
- Finite State Machines:
Deterministic and non-deterministic finite state automata, closure
properties, regular expressions, pumping lemma, Myhill-Nerode Theorem
and state minimization .
- Pushdown Machines: Deterministic
and non-deterministic pushdown automata, context-free grammars, pumping
lemma.
- Turing Machines: Turing machines
and models of computation, universal machine, decidable and undecidable
problems.
Grading
Homeworks:
There will be about 6-7 written homeworks.
They will have to be
turned in at the beginning of the class on the due date. No late
submission
will be accepted without prior
permission of the instructor.
Exams:
There will be three exams, one of which will
be held in the finals week.
Overall Course Grade:
60% for the three exams
40% for homework
General Items
-
Retain copies of your class notes,
handouts, homeworks, and
solutions (when provided). Exam questions
will generally be similar to homework problems or results presented in
class.
- In case of questions regarding the grading of the homeworks, you should
contact the TA first. Then, if you still have questions, contact
the
instructor. For other questions, you may contact either the
instructor or
the TA first.
- While students are encouraged to discuss the course material among themselves, all
written work you
turn in must be entirely your own.
Submitting
work that is not your
own is considered cheating, as per Departmental and University policy.
No discussion or joint effort in answering the homework questions is
acceptable.
- Please turn off you cell phone, pagers etc.
and refrain from using laptops during class.
- I will try to respond to emails from within
24 hours during the
week days. I may not be able to respond to emails over the weekends.
Prerequisite
MATH 210, CISC181 and CISC220 with
grades of
C- or better.
Homeworks
Homework Solutions
Handouts