Computer Science 501 - Formal Language Theory

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.

Undergraduates must have completed CMPSCI 311 with a grade of 'C' or better. LECT 01 FOR UNDERGRADS; LECT 02 FOR GRADS. IT IS RECOMMENDED THAT UNDERGRADUATE STUDENTS HAVE A B- OR BETTER IN COMPSCI 311 IN ORDER TO ATTEMPT 501. CS MINORS, APPLICANTS-ON-CONTRACT, AND OTHERS NOT MEETING ELIGIBILITY, OR STUDENTS NEEDING SPECIAL PERMISSION MUST REQUEST OVERRIDES VIA THE ON-LINE FORM: https://www.cs.umass.edu/overrides.