Theory of Computation

CS25C14:

Theory of Computation

Course Objectives: To apply the foundational concepts of automata theory and formal languages to model computational problems and analyze the properties of languages and grammars.

Finite Automata: Deterministic Finite Automata (DFA), Nondeterministic Finite Automata (NFA), and Finite Automata with Epsilon Transitions (ε-NFA): Transition table, Transition function, Extended Transition Function, Equivalence of Deterministic and Nondeterministic Finite Automata–Eliminating ε Transitions -Testing equivalence and Minimization of DFA: Table filling algorithm.

Activities:

• Assignment: Construction of DFA for real-world patterns like valid binary strings, identifiers in programming languages and so on.

• Flipped Class Room: Practice of minimization and table-filling algorithm with multiple examples.

Regular Expressions and Languages: Operators and precedence, Building regular expressions - Converting DFAs to Regular Expressions Converting Regular Expressions to Automata – Applications, Regular Languages - Pumping Lemma - Closure properties.

Activities:

• Quiz: "Build the regex" for language patterns

• Assignment: RE ↔ FA with state elimination and construction

Turing Machines: Notation, Instantaneous descriptions, Transition diagram, Language of TM – Basics on Types of TMs - Design of simple TMs: Integer functions.

Activities:

• Project based experiential learning:

o Design simple TMs for unary increment, unary decrement.

o Design TM for binary addition, binary subtraction.

Computability: Recursive and Recursively Enumerable (RE) languages: Fundamentals – Decidability and Undecidability: Concepts and characteristics - Rice Theorem – Halting problem - Post’s Correspondence Problem (PCP) – Modified Post’s Correspondence Problem (MPCP).

Activities:

• Review of GATE Questions

• Quiz: NP, NP-Complete with examples like SAT, Hamiltonian path.

Assessment Weightage:

Weightage:Continuous Assessment: 40%

(i) . Activities: 10%

(ii) . Internal Examination: 30%

End Semester Theory Examination: 60%

Mandated Activities with marks: Assignments (30), Quiz (10), Project based learning (25), Flipped Classroom (10), Review of GATE questions (25).

Internal Examinations: TWO tests

References:

1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Pearson, 2018.

2. Michael Sipser, Introduction to the Theory of Computation, 3rd Edition, Cengage Learning, 2017.

3. Pallavi Vijay Chavan & Ashish Jadhav, Automata Theory and Formal Languages, 1st Edition, Academic Press (Elsevier), April 2023.