Automata Theory | Department of Mathematics

Automata Theory

Credits: 4 (3 lectures and 1 tutorial weekly)



Detailed Syllabus:

  1. Formal Logic: Statements and notation, Connectives, Normal Forms, Predicate Logic and Inference Theory, Propositional Logic, Proof in Propositional Logic
  2. Syntax of First-Order Logic: First-Order Languages, Formulas of a Language, First-Order Theories
  3. Semantics of First-Order Languages: Structures of First-Order Languages, Truth in a Structure, Model of a Theory, Embeddings and Isomorphisms
  4. Regular Languages and Regular Grammars: Regular Expressions, Regular Languages, Properties of Regular Languages, Regular Grammars
  5. Finite Automata: Finite State machines, Finite Automata, Deterministic Finite Automata, Nondeterministic Finite Automata
  6. Context-Free Grammars and Languages: Context-Free Grammars, Parsing, Ambiguity in Grammars and Languages, Pushdown Automata, Chomsky Normal Forms
  7. Computability: Turing Machines, Decidable Languages, the Halting Problem, Undecidability, Reducibility
  8. Time Complexity: Measuring Complexity, the Complexity Class P, the Complexity Class NP, NP-Completeness


  • S.M. Srivastava A Course on Mathematical Logic, Springer.
  • J. E. Hopcroft, R. Motwani, J. D. Ullman Introduction to Automata Theory, Languages and Computations, Pearson.
  • J. P. Tremblay, R. Manohar Discrete Mathematical Structures with Applications to Computer Science, Tata McGraw-Hill.
Course Code: 
Course Credits: 
Course Level: