Theory of Computation

UNIT 1: Foundations of Formal Languages & Finite Automata (15 Hrs)

• Mathematical Preliminaries
  • Alphabets
  • Strings
  • Languages
• Operations on Languages
  • Union
  • Concatenation
  • Kleene Star
  • Complement
  • Intersection
• Regular Languages
  • Regular Expressions and Their Equivalence to Finite Automata
  • Deterministic Finite Automata (DFA)
  • Non-deterministic Finite Automata (NFA)
  • NFA to DFA Conversion
• Properties of Regular Languages
  • Closure Properties
  • Pumping Lemma for Regular Languages
  • Limitations of Regular Languages

UNIT 2: Context-Free Languages & Pushdown Automata (15 Hrs)

• Context-Free Grammars (CFGs)
  • Derivations, Parse Trees, Ambiguity in Grammars
  • Simplification of CFGs
  • Normal Forms: Chomsky Normal Form (CNF)
  • Normal Forms: Greibach Normal Form (GNF)
• Pushdown Automata (PDA)
  • Definition and Examples
  • Acceptance by Final State and Empty Stack
  • Equivalence of PDA and CFG
• Properties of CFLs
  • Closure Properties of CFLs
  • Pumping Lemma for CFLs

UNIT 3: Turing Machines, Computability & Complexity (15 Hrs)

• Turing Machines (TMs)
  • Definition and Examples
  • Variants of TMs (Multi-tape, Non-deterministic)
  • Universal Turing Machine
• Computability Theory
  • Decidability and the Halting Problem
  • Recursive and Recursively Enumerable Languages
  • Examples of Unsolvable Problems
• Introduction to Complexity Theory
  • Basic Time and Space Complexity
  • Classes P and NP, NP-completeness

Tutorials Course (1 Credit, 15 Hours)

1. Write a regular expression for even number of a’s
2. To accept strings ending with ‘a’
3. To accept strings with exactly two consecutive ‘b’s
4. Convert a given NFA into DFA
5. Use Pumping Lemma to show a language is not regular
6. Write a CFG for balanced parentheses
7. Draw a parse tree for a given grammar
8. Design a PDA for strings of equal number of a’s and b’s
9. Design a simple Turing Machine to recognize 0^n1^n
10. Explain the Halting Problem with an example
11. Identify if a problem belongs to P or NP

SUGGESTED READING

1. Introduction to the Theory of Computation, Third Edition Michael Sipser, Cengage Learning, ISBN-13: 978-1-133-18779-0
2. Cohen, D. I. A. (2003). Introduction to computer theory (2nd ed., ISBN: 8126513349). New Delhi, India: McGraw-Hill Education.
3. Formal Languages and Automata Theory by Peter Linz (3rd edition, 2011)
4. Hoperoft, Aho, Ullman Introduction to Automata Theory, Language & Computation.