📚 Course Overview

Theory of Computation is a fundamental course that explores the mathematical foundations of computer science. You'll learn about different computational models, their capabilities, and limitations.

📖
5
Units
❓
10
Questions
⏱️
60+
Topics

📑 Course Units

Click on any unit to explore topics in detail

UNIT I

Automata Theory

Learn about FSM, DFA, NDFA, Mealy & Moore machines, Regular expressions, and Pumping Lemma

FSM DFA/NDFA Regular Expressions
Explore Unit I →
UNIT II

Context-Free Grammars

Master CFG, derivation trees, ambiguity, normal forms (CNF & GNF), and grammar simplification

CFG Chomsky NF Greibach NF
Explore Unit II →
UNIT III

Pushdown Automata

Study PDA, DPDA, CFG-PDA conversion, Pumping Lemma for CFLs, and closure properties

PDA DPDA CFL Properties
Explore Unit III →
UNIT IV

Turing Machines

Understand Turing Machine model, Church's hypothesis, recursive languages, and Universal TM

TM Model Church's Thesis UTM
Explore Unit IV →
UNIT V

P, NP & Related Problems

Explore complexity classes, NP-Complete problems, Hamiltonian Path, and Traveling Salesman Problem

P vs NP NP-Complete TSP
Explore Unit V →
⭐ IMPORTANT

Exam Questions

10 important questions with detailed answers covering all units for exam preparation

10 Questions Detailed Answers
View Questions →

🎯 Learning Outcomes

✅
CO1: Outline the concept of Finite Automata and Regular Expression
✅
CO2: Illustrate the design of Context Free Grammar for any language set
✅
CO3: Demonstrate the push down automaton model for the given language
✅
CO4: Make use of Turing machine concept to solve the simple problems
✅
CO5: Explain decidability or undecidability of various problems