Automata Theory and Formal Languages
Second Semester (Spring)

Instructor
Ayaz
Teaching Assistant
Javad
Semester
Spring 2010
Class Time
Saturday   08:00 - 10:00    (Theoretical concepts)
Sunday  08:00 - 10:00*   (Tutoring and implementation issues)
Class Location
University of Tabriz, Department of Computer Science, Room A
Textbook
Introduction to Automata Theory, Languages, and Computation, 3rd Edition
Hopcroft, Motwani, and Ullman, Addison-Wesley, 2007.
Course Objectives
As a fundamental concept in Theoretical Computer Science, the aim of this course is,
  • To define mathematical models of computing devices, called abstract machines, namely Finite Automata, Pushdown Automata, and Turing Machines.
  • To study the capabilities of these abstract machines,
  • To develop theory and techniques for reasoning about computation... And thereby,
  • To achieve an understanding of the theoretical limits of computation.
Course Contents
Topics include:
  1. Introductory Notions of Grammars, Languages, and Abstract Machines
    1. Alphabets, Strings, Languages, Grammars, and their Classifications
    2. Abstract Machines and corresponding Languages
  2. Finite Automata and Regular Languages
    1. Finite Automata: Definitions and Examples
    2. Deterministic and Non-Deterministic Finite Automata
    3. Regular Languages and Regular Expressions
    4. Properties of Regular Languages
    5. Pumping Lemma for Regular Languages
  3. Pushdown Automata and Context-Free Languages
    1. Pushdown Automata: Definitions and Examples
    2. Context-Free Grammars
    3. Pars Trees and Ambiguity in Grammars
    4. Pushdown Automata and their equivalence to CFG's
    5. Pumping Lemma for Context-Free Languages
  4. Turing Machines
    1. Turing Machines: Definitions and Examples
    2. Halting and Acceptance Problems
    3. Turing Machines and Computers
Grading
Coursework, Course Policies, Evaluations and Grading...
Additional References and Resources
  • Languages and Machines, 3rd Edition,
    Thomas A. Sudkamp, Addison-Wesley, 2005.
  • Introduction to Languages and the Theory of Computation, 3rd Edition,
    John Martin, McGraw-Hill, 2003.
  • An introduction to Formal Languages and Automata, 3rd Edition,
    Peter Linz, Jones and Bartlett Publishers, 2001.
  • Our own e-book.
  • And, of course, various resources available on the net, including the publisher's resource site for the textbook.
Back to Homepage

Ayaz Isazadeh
March, 2010