CS25C14 Theory of Computation – Semester IV – CSE – R-2025

Subject Code & Name: CS25C14 – Theory of Computation

Regulation: R-2025

Semester: IV (Fourth Semester)

Branch: B.E. Computer Science and Engineering (CSE)

Credits / L-T-P: 4 Credits | L-T-P: 3-1-0

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.

Full Unit-wise Syllabus

Unit I – 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.

Unit II – 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.

Unit III – 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: Design simple TMs for unary increment, unary decrement; Design TM for binary addition, binary subtraction.

Unit IV – 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.

Course Outcomes (COs)

• CO1: Describe the fundamental concepts in the context of theoretical computer science.
• CO2: Analyze different computational models Turing machines to understand their capabilities and limitations.
• CO3: Evaluate formal languages, grammars, and decidability problems to assess computational complexity and solvability.
• CO4: Design computational models and formal language using appropriate automata and grammar techniques.
• CO5: Develop the ability to apply emerging topics in computational theory through continuous self-learning.

Assessment Pattern (Quick Note)

• Weightage: Continuous Assessment 40% | End Semester Theory Examination 60%
• Internal methodology: Activities 10% (Assignments 30, Quiz 10, Project based learning 25, Flipped Classroom 10, Review of GATE questions 25), Internal Examinations 30% (TWO tests)

Source: Official Anna University – B.E. Computer Science and Engineering R-2025 Syllabus
Last Updated: October 2026