CSE 2103 Theory of Computation (Session 2018-19)
Undergraduate course, Noakhali Science and Technology University, Institute of Information Technology, 2019
This was full pledged class after COVID-19 crisis.
Time
From Dec 2018 to May 2019
Course Contents
Brief Review of mathematical background: Binary relations, digraph, string,languages, proofs, inductive definitions; Finite automata and regular expressions: Deterministic and non-deterministic finite automata, regular expressions and regular sets, Kleene’s Theorem; Properties of regular sets: pumping lemma, closure properties, decision algorithms; Context Free grammar and languages: Context-free grammars, regular grammars; Simplified forms and normal forms: useful symbols, productions, unit productions, chomsky normal form; Pushdown automata: pushdown automaton, equivalence between pushdown automata and context-free languages; Turing machine: introduction to Turing machines.
Reference Book:
- Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Third Edition, Pearson Education.
- Sipser, Michael. “Introduction to the Theory of Computation.” ACM Sigact News 27.1 (1996): 27-29.