Study of the relation of
languages (i.e. sets of strings) and machines for processing these languages,
with emphasis on classes of languages and corresponding classes of machines. Phrase structure languages and
grammar. Types of grammar and classes of languages.
Regular languages and finite state automata. Context-free languages and pushdown automata. Unrestricted languages and Turing Machines. Computability
models of Turing, Church, Markov, and McCarthy. Applications
to programming languages, compiler design, and program design and testing.
Updated: August 22, 2015