CISC 303 -- Spring 2013
Instructor: Vijay Shanker
Office: 442 Smith Hall
Office Hours: Tuesdays 1:30pm -- 2:30pm and Wednesdays --
1:30pm -- 2:30pm
TA: Christopher Angelo Sapello
Office: 103 Smith Hall
Office Hours: Mondays and Wednesdays 10:00am -- 11:00am
- Automata and Computability
Dexter C. Kozen. Springer, 1997.
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
- 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
- Turing Machines: Turing machines
and models of computation, universal machine, decidable and undecidable
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
will be accepted without prior
permission of the instructor.
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
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
- In case of questions regarding the grading of the homeworks, you should
contact the TA first. Then, if you still have questions, contact
instructor. For other questions, you may contact either the
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.
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
- 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.
MATH 210, CISC181 and CISC220 with
C- or better.