Introduction to Theory of Computing

This is a first course on the theory of computing. Fundamental Topics include finite automata, regular expressions and languages, context-­free grammars and languages, push-­down automata, pumping lemmas for regular languages and for context-­free grammars, the Chomsky hierarchy of language classes, Turing machines and computability, undecidability of the halting problem, reducibilities among decision problems and languages, time complexity, and NP-­completeness and tractability.

Prerequisites: 
http://bulletin.uga.edu/CoursesHome.aspx

Semester Offered: 
Fall
Spring
Level: 
Course Information File: