2301379 Theory of Computation

• 0-Introduction
• 1-Regular expressions
• 2-DFA
• 3-NFA
• 4/1-DFA-NFA-RegEx
• 4/2-DFA-NFA-RegEx-Example
• 5-RegLang-PumpingLemma
• 6-PDA-CFG
• 7-DTM
• 8-NTM
• 9/1-Accept-Halt-Empty
• 9/2-Reduction
• 10/1-Reduction (cont.)
• 10/2-Rice's Theorem

Regular expression, relgular language and finite automata

• Problems from ACM-ICPC
  • 2596 - Acceptable Strings
  • 6280 - Disjoint Regular Expressions

Syllabus

First semester, 2013