Introduction to formal language theory. Topics include finite state languages, context-free languages, the relationship between language classes and formal machine models, the Turing Machine model of computation, theories of computability, resource-bounded models, and NP-completeness. It is recommended that students have a 'B-' or better in CMPSCI 311 in order to attempt CMPSCI 501.