CSC 101
Intro to Languages and Theory

Computability refers to the study of the mathematical foundations of computation: what is an appropriate mathematical model of a computer, what types of computations are possible in the model, what types are not, the inherent complexity of certain computations and so forth. Perhaps surprisingly, many concepts from the theory of computation have become of fundamental importance in other areas of computer science, such as computational linguistics, compiler design, hardware design, object-oriented design, artificial intelligence, and even the syntax of the UNIX grep and awk commands.

In this course we will investigate the interaction between various models of computation. Along the way the intimate connection between computation and language recognition will be developed. We will study several classes of abstract machine including finite automata, push-down automata and Turing machines along with several classes of languages such as regular and context-free languages. In addition we will examine some of those problems, such as the Halting Problem, which are not amenable to computer solution.

To complement the study of theoretical aspects of modeling computer languages, we will also investigate and practice writing parsers and interpreters for simple programming languages. This hands-on experience will provide a firm grounding in both the run-time characteristics of programming languages and the formal specification of programming language semantics. The formal specification of different aspects of languages allows us to prove properties of the languages themselves, such as type safety, as well as reason properly about programs in the languages.

By the end of this course, you should be able to:

  1. Describe and use formal systems to model real phenomena.
  2. Recognize language classes (e.g., regular, cfl, decidable, r.e.), their gaps, and why each is important.
  3. Determine in which classes a language is contained (including via using pumping lemmas).
  4. Understand the equivalence of generators and recognizers of languages (e.g. regular expressions and finite automata, cfg’s and pda’s, r.e. languages and Turing machines).
  5. Understand the use of formal specifications (e.g., context-free grammars) to derive algorithms to parse, type-check, and/or interpret languages, and be able to implement some of these in a functional language.
  6. Understand the Church-Turing thesis and several models of universal computation.
  7. Understand and be able to show that a variety of interesting problems involving computation are undecidable using reduction to the halting problem and/or Rice's theorem.