Theory of Computation



Chapter 1: Introduction

Topics: (3 lectures)
  • Introduction to Theory of Computation
  • Finite State Machine –Prerequisites
  • Finite State Machine

Chapter 2: Finite Automata Without Output

Topics: (24 lectures)
  • Deterministic Finite Automata (DFA)
  • Regular Languages
  • Non-Deterministic Finite Automata (NFA)
  • Conversion of NFA to DFA
  • Minimization of DFA
  • Minimization of DFA using Myhill Nerode Theorem

Chapter 3: Finite Automata With Output

Topics: (14 lectures)
  • Introduction to Mealy Machine and Moore Machine
  • Construction of Mealy Machine
  • Construction of Moore Machine
  • Conversion of Moore Machine to Mealy Machine
  • Conversion of Mealy Machine to Moore Machine

Chapter 4: Epsilon NFA

Topics: (5 lectures)
  • Introduction to Epsilon NFA
  • Conversion of Epsilon NFA to NFA

Chapter 5: Regular Expressions

Topics: (20 lectures)
  • Introduction to Regular Expression
  • Identities of Regular Expressions
  • Arden’s Theorem and Examples using Identities
  • Conversion of Regular Expression to Finite Automata
  • Equivalence of two Finite Automata
  • Pumping Lemma for Regular Languages
  • Regular Grammar

Chapter 6: Context Free Language

Topics: (10 lectures)
  • Introduction to Context Free Language (CFL)
  • Derivation Tree
  • Ambiguous Grammar
  • Simplification/ Reduction of CFG
  • Chomsky Normal Form (CNF)
  • Conversion of CFG to CNF
  • Greibach Normal Form (GNF)
  • Conversion of CFG to GNF
  • Pumping Lemma for CFG

Chapter 7: Pushdown Automata

Topics:
  • Not Available

Chapter 8: Turing Machine

Topics:
  • Not Available

Chapter 9: Decidability

Topics:
  • Not Available