CORE

Theory of Computation

24CST601 · S6 · 4 credits

Official KTU 2024 syllabus subject — study with practice, PYQs and AI tools.

Syllabus

Loading syllabus…

⚡ DAY-BEFORE EXAM

Have an exam tomorrow?

Get a high-yield attack plan focused on maximum marks per minute. Zero fluff, strict PYQ priority, active recall, and trap avoidance.

1. How much time do you have remaining?

Strategy: High-yield concepts + PYQs + weak areas

2. Topic Prioritization (Highest Marks First)Tap a module to mark as weak

PRIORITY A

Module 1

Why:Foundation module

+ Mark Weak

PRIORITY A

Module 2

Why:High exam relevance

+ Mark Weak

PRIORITY B

Module 3

Why:Core module

+ Mark Weak

PRIORITY B

Module 4

Why:Applied concepts

+ Mark Weak

PRIORITY C

Module 5

Why:Standard exam coverage

+ Mark Weak

Modules

Module 01Regular languagesexpand

Introduction to Regular Languages, Finite state automata - Types (DFA, NFA, Epsilon- NFA), properties, Extended Transition functions. Designing DFA, NFA and Epsilon-NFA. Equivalence and conversions: DFA and NFA, NFA and Epsilon-NFA, Myhill-Nerode Theorem and applications, Minimization of DFA states.

Module 02Regular Expressionsexpand

Regular Languages- Closure Properties of Regular Languages, Necessary conditions for regular languages-Pumping Lemma, Homomorphism. Regular Grammar (RG), Regular Expressions (REs), Equivalence and conversions: REs and Epsilon-NFA. Context-Free Languages (CFL)-Closure Properties of CFL. Necessary conditions for Context Free Languages-Pumping Lemma

Module 03Context free languages Context-Free Grammar (CFG)expand

Derivation trees, Ambiguity, Normal forms for CFGs: Chomsky Normal Form and Greibach normal forms (Definitions only). Nondeterministic Pushdown Automata (PDA), Deterministic Pushdown Automata (DPDA), Designing NPDAs and DPDAs. Turing Machine (TM) – Basics and formal definition, TMs as language acceptors, Encoding of Turing Machine

Module 04Turing Machine and decidability Recursively Enumerable Languages (REL)expand

Recursive languages (RL), Properties of REL and RL. Church-Turing thesis, Notion of undecidable problems. Universal language and universal TM. Notion of reduction. Halting Problem and undecidable problems of TMs, Rice's theorem.

Module 05Complexity classes and related problemsexpand

Time and space measures of complexity, complexity classes P, NP, NP-complete problems. Cook-Levin theorem: NP-completeness of propositional satisfiability, other variants of satisfiability. NP-complete problems from graphs-vertex cover, Hamiltonian cycle Chomsky Hierarchy

Notes / Resources

Exam-focused notes are optional context — Continue Learning above works even without them.

Notes for this subject aren't written yet

Continue Learning above adapts to this subject anyway — it teaches from your active syllabus.