CIS 5513. Automata and Formal Languages

Section 001. Fall 2017



Dr. Pei Wang
OFFICE: Room 347, Science Education and Research Center (SERC)
ADDRESS: CIS Department, Temple University, Philadelphia, PA 19122
PHONE: (215)204-9255 (available only during office hours)
EMAIL: (preferred way of communication)
Office Hours in Fall 2017: Monday/Friday 2-3pm, Monday 10-11am, and by appointment


Class: Monday 5:30 - 8:00 PM, Tuttleman Learning Center 401A


CIS 2166 and CIS 3242 (discrete mathematics: set theory, mathematical logic, graph theory, etc.)

Course Description

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 Objective


Introduction to Automata Theory, Languages, and Computation, Third Edition, John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Prentice Hall 2006, ISBN: 978-0321455369


See course website at


Policies and Rules