Semester 5Year 3 · OddCore Subject★★★★★ Hard
CS 503

Theory of Computation

Study of automata, formal languages, computability, and complexity theory.

4Units
26Topics
4Credits
60hLecture hrs
100Max marks
Your Progress
0 / 26 topics
0% complete
Overview
🎯
Why it matters
TOC answers 'What can computers compute?' and 'How fast?'. Understanding P vs NP, decidability, and automata is fundamental to computer science theory. Regex, compilers, parsers — all rooted here.
💼
Placement relevance
Less direct placement impact but CRITICAL for GATE CSE (12-15 marks). Core companies may test automata. Essential theoretical foundation for advanced CS.
🔗
Prerequisites for
Compiler Design · Formal Methods · Cryptography · Complexity Theory · Research in CS
📚
Recommended books
Introduction to the Theory of Computation by Michael Sipser · Introduction to Automata Theory by Hopcroft, Ullman · Theory of Computer Science by K.L.P. Mishra
Curriculum — 4 Units
U1
Unit 1 · 7 Topics · 0% complete
Finite Automata
⚡ Key Formulae
DFA:5-tuple: (Q, Σ, δ, q0, F)
NFA to DFA:Power set construction: 2^n states maximum
Pumping Lemma:For regular L, ∃p: if |w|≥p, then w=xyz where |xy|≤p, |y|>0, xy^iz∈L
DFA
NFA
NFA to DFA Conversion
Minimization of DFA
Regular Expressions
Regular Languages
Pumping Lemma for Regular
U2
Unit 2 · 7 Topics · 0% complete
Context-Free Grammars
⚡ Key Formulae
CFG:4-tuple: (V, T, P, S)
PDA:7-tuple: (Q, Σ, Γ, δ, q0, Z0, F)
CFG Basics
Derivations
Parse Trees
Ambiguity
Chomsky Normal Form
Pushdown Automata
Pumping Lemma for CFL
U3
Unit 3 · 6 Topics · 0% complete
Turing Machines
⚡ Key Formulae
TM:7-tuple: (Q, Σ, Γ, δ, q0, qaccept, qreject)
Decidable:TM halts on all inputs (accepts or rejects)
TM Definition
TM Variants
Church-Turing Thesis
Decidability
Halting Problem
Reducibility
U4
Unit 4 · 6 Topics · 0% complete
Complexity Theory
⚡ Key Formulae
P vs NP:P ⊆ NP; P = NP is unsolved
NP-Complete:In NP AND all NP problems reduce to it
P Class
NP Class
NP-Complete
NP-Hard
Cook's Theorem
Reductions
Previous Year Questions
Unit 12023 · End Semester10 marks
Design a DFA that accepts strings over {0,1} where number of 0s is divisible by 3. Convert it to regular expression.
Unit 32022 · End Semester8 marks
Prove that the Halting Problem is undecidable using reduction technique.
Exam Strategy
🎨
Draw state diagrams
DFA/NFA questions need clear state diagrams. Label states (q0, q1...), transitions (0,1), final states (double circle). Neat diagrams = better grades.
📝
Master conversions
NFA→DFA, RE→NFA, CFG→CNF — these conversions are 40% of exam. Practice step-by-step procedures. Show all intermediate steps.
🔍
Pumping Lemma proofs
Prove language is NOT regular/CFL using pumping lemma. Choose string carefully, show contradiction for all decompositions. Common exam question.
Related Subjects
Semester 5
Compiler Design
CS 502
Semester 3
Discrete Mathematics
MATH 201