Automata Theory

Credits: 4 (3 lectures and 1 tutorial weekly)

Prerequisites:

Overview:

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

References:

• 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.