CS 411 - Computability and Formal Languages

Description: 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.

Prerequisites: CS 310
Credit Hours: 3

Class Hrs./Week:
3

Lab Hrs./Week:
0

Hardware: None

Software: None
To Top of Page