CS340A - Theory Of Computation

Scope and motivation for theory of computation; informal introduction to computability and complexity; set membership problem as idealization of computing problems; alphabets, strings, languages, automata; deterministic finite automata; non determinism; equivalence of DFAs and NFAs; regular expressions and their equivalence with finite automata; pumping lemma; some applications of FAs (e.g., text pattern matching); decision properties of regular languages; Myhill Nerode theorem; minimization of DFAs, Grammars as generative devices; context free grammars, derivation, and parse trees; pushdown automata; equivalence with CFGs; normal forms of CFGs, pumping lemma for context free languages; decision and closure properties; some applications (e.g., YACC, markup languages, XML and document type definition, etc.), Why consider Turing machines?; basic TM model and its extensions; NDTMs, TM configurations; robustness of TM as a computing model; universal TM, Recursive and r.e. languages; notion of un decidability; un decidability of halting problem; reducibility; other un decidable problems; Rice’s theorem; separation of r.e. and recursive languages; existence of non r.e. languages; self reference, recursion theorem; decidability of logical theories; implication to automated theorem proving, Motivation for examining feasibility/infeasibility distinction; definition of time and space complexity classes; P and NP, and their importance; polynomial time reducibility; definition of NP completeness, and NP hardness; Cook Levin theorem; some other NP complete problems, Brief review of the notion of randomized algorithms; probabilistic TMs; classes RP, BPP, and ZPP; relationships to P and NP; proof of inclusion of BPP in P/poly.