Computability and Formal Languages

3 credits

The notion of effective procedure and Turing machine. The universal Turing machine. Nondeterministic Turing machine. Recursive functions and other computable functions. The halting problem and unsolvability. Grammar and formal language. Finite automata and regular grammars. Context-free grammars and push-down automata. Post correspondence problem. The Chomsky hierarchy of languages and context-sensitive language. *** Prerequisite: CS 310 ***