Theory of Computation / Automata

Finite State Models, Regular expressions/Regular languages, Finite automata (FAs), Transition graphs (TGs), NFAs, Kleene’s theorem, Transducers, Pumping lemma, CFGs, Pushdown Automata (PDA), Turing Machines Theory, Decidability, and the Chomsky Hierarchy.

Instructor: Mr. Musawar Ali

Term: Spring (2 Semesters)

Location: CS Department, National University of Computer & Emerging Sciences, Karachi

Course Overview

This course delivers a comprehensive breakdown of theoretical computer science architectures, focusing on formal languages, automata models, and the boundaries of computation. Students will analyze, design, and differentiate mathematical models of computation from finite state machines to universal computing devices.

Students will:

  • Explain and manipulate the different concepts in automata theory and formal languages such as formal proofs, automata, regular expressions, and Turing machines.
  • Prove properties of languages, grammars, and automata with rigorously formal mathematical methods.
  • Design automata, Regular Expressions (RE), and Context-Free Grammars (CFG).
  • Transform between equivalent NFAs, DFAs, and REs.
  • Define Turing machines and PDA machines performing simple tasks.
  • Differentiate and manipulate formal descriptions of languages, automata, and grammars with a focus on regular and context-free languages.

Prerequisites

  • Discrete Structures

Textbooks

  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation.
  • P. Linz, Introduction to Formal Languages and Automata, 6th edition, 2017 (or 5th/4th edition), Jones and Bartlett.
  • Daniel I. A. Cohen, Introduction to Computer Theory.

Reference Material

  • John Martin, Introduction to Languages and the Theory of Computation, Third Edition.
  • Michael Sipser, Introduction to the Theory of Computation.

Grading

  • Semester Work (at least 5 assignments): 20%
  • Midterm Examination 1 (Week 6): 15%
  • Midterm Examination 2 (Week 12): 15%
  • Final Examination (Comprehensive): 50%

Academic Integrity & Policies

  • Plagiarism: Zero tolerance policy. Minimum grade penalty of 100% (course failure) for plagiarism.
  • Late Submissions: Allowed until the solution is discussed in class, subject to a maximum grade penalty of 50% for the assignment.
  • Quizzes: Held at the start of class. There will be NO compensation for missed quizzes.
  • Communication: Students must send a same-day email reminder to the instructor for any verbal comments or agreements made during class (e.g., class participation bonus, late submission allowance, or leaves).

Schedule

Week Date Topic Materials
1-5 Finite State Models & Regular Languages

Discussion on Course Outline, Introduction to Finite Automata, Languages, Alphabets, Strings, Kleene Star Closure, Regular Expressions (RE), Equivalent RE, Finite Automaton (FAs), Equivalent FAs, FA corresponding to finite languages, Transition Graphs (TGs), and Generalized Transition Graphs.
6-10 Advanced Automata, Properties of RLs & Context-Free Grammars

Language accepted by NFA, Recursive definition of NFA, Basis Clause and Inductive Clause of NFA, Language and Complement of DFA, Intersection of Regular Languages, Properties of RLs, Pumping Lemma, Minimization of DFA, Mealy & Moore Machines, Conversion between Mealy & Moore Machines, and Regular/Linear Grammars.
11-15 PDAs, Turing Machines & Decidability

Parse Trees, Derivations, Ambiguity, Chomsky Normal Form (CNF), Null Production, Trees, Polish Notations, Total Language Tree, Pushdown Automata (PDA), Deterministic PDA, NPDA and CFG Equivalence, Turing Machines (TM) Introduction, Designing TM as Acceptors/Transducers, Turing’s Thesis, TM Variations, Universal Turing Machine, Decidability, Recursive vs. Recursively Enumerable, Decidable/Undecidable Problems, and the Chomsky Hierarchy.