Automata and Formal Languages

Course number: 
CIS 5513
Fall 2015
Name E-mail Office location
Pei Wang
Science Education and Research Center (SERC), Room 347
Introduction to Automata Theory, Languages, and Computation, Third Edition, John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Prentice Hall 2006, ISBN: 978-0321455369
Topics covered: 
Types of grammars. Finite automata and regular languages. Kleene's Theorem. Closure properties and decidable problems of regular languages. Derivation trees. Normal forms of context-free grammar. The self-embedding properties, closure properties and decidable problems of context-free languages. Methods of syntax analysis for context-free languages. Context-sensitive languages and linear bounded automata. Turing machines.
Course goals: 
  • To understand the basic concepts of automata, formal languages, and models of computation.
  • To be able to follow the common algorithms in the field to solve problems.
  • To be able to relate the materials covered in this course to the other topics in computer science.
Attendance policy: 
Attendance to all meetings of the class is mandatory
Accomodations for Students with Disabilities: 
Any student who has a need for accommodation based on the impact of a documented disability, including special accommodations for access to technology resources and electronic instructional materials required for the course, should contact me privately to discuss the specific situation by the end of the second week of classes or as soon as practical. If you have not done so already, please contact Disability Resources and Services (DRS) at 215-204-1280 in 100 Ritter Annex to learn more about the resources available to you. I will work with DRS to coordinate reasonable accommodations for all students with documented disabilities. (
Student and Faculty Academic Rights and Responsibilities: 
Freedom to teach and freedom to learn are inseparable facets of academic freedom. The University has a policy on Student and Faculty and Academic Rights and Responsibilities (Policy #03.70.02) which can be accessed through the following