CSE 2103 Theory of Computation (Session 2019-20)
Undergraduate course, Noakhali Science and Technology University, Institute of Information Technology, 2020
Description here
Time
From Dec Jan 2020 to Aug 2021
Course Outline
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 Books:
- 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.