CPSC 340

This course examines regular expressions, deterministic and non-deterministic finite automata, pushdown automata, Chomsky and Greibach normal forms. Chomsky hierarchy, pumping lemmas, Turing machines, undecidability, computability, recursive function theory, computational complexity. NP-hard and NP-complete problems and context-free and other grammars. Section information text: This course examines regular expressions, deterministic and non-deterministic finite automata, context-free and other grammars, pushdown automata, Chomsky and Greibach normal forms. Chomsky hierarchy, pumping lemmas, Turing machines, undecidability, computability, recursive function theory, computational complexity, NP-hard and NP-complete problems.