Theory of Computation

Catalog description

Deterministic and nondeterministic finite state automata; regular grammars and regular expressions; equivalence of regular expressions and finite automata; pumping lemma for regular languages; context free grammars; languages generated by context free grammars; parse trees and ambiguity; Chomsky normal form; pushdown automata; equivalence of context free grammars and pushdown automata; pumping lemma for context free languages; Turing machines; Universal Turing machine; Halting problem; solvable and unsolvable problems about automata and languages; introduction to complexity theory; NP-complete problems.