Description
We begin with a study of finite automata and the languages they can define (the socalled "regular languages." Topics include deterministic and nondeterministic automata, regular expressions, and the equivalence of these languagedefining mechanisms. We also look at closure properties of the regular languages, e.g., the fact that the union of two regular languages is also a regular language. We consider decision properties of regular languages, e.g., the fact that there is an algorithm to tell whether or not the language defined by two finite automata are the same language. Finally, we see the pumping lemma for regular languages  a way of proving that certain languages are not regular languages.
Our second topic is contextfree grammars and their languages. We learn about parse trees and follow a pattern similar to that for finite automata: closure properties, decision properties, and a pumping lemma for contextfree languages. We also introduce the pushdown automaton, whose nondeterministic version is equivalent in languagedefining power to contextfree grammars.
Next, we introduce the Turing machine, a kind of automaton that can define all the languages that can reasonably be said to be definable by any sort of computing device (the socalled "recursively enumerable languages"). We shall learn how "problems" (mathematical questions) can be expressed as languages. That lets us define problems to be "decidable" if their language can be defined by a Turing machine and "undecidable" if not. We shall see some basic undecidable problems, for example, it is undecidable whether the intersection of two contextfree languages is empty.
Last, we look at the theory of intractable problems. These are problems that, while they are decidable, have almost certainly no algorithm that runs in time less than some exponential function of the size of their input. We meet the NPcomplete problems, a large class of intractable problems. This class includes many of the hard combinatorial problems that have been assumed for decades or even centuries to require exponential time, and we learn that either none or all of these problems have polynomialtime algorithms. A common example of an NPcomplete problem is SAT, the question of whether a Boolean expression has a truthassignment to its variables that makes the expression itself true.
Requirements
The primary prerequisite for this course is reasonable "mathematical sophistication." That is, you should feel comfortable with mathematics and proofs. Specific topics that are useful include a knowledge of graphs, trees, and logic, as well as basic data structures and algorithms. If you do not meet the prerequisites, there is a free textbook, Foundations of Computer Science.
Instructor
Jeff Ullman is a retired professor of Computer Science at Stanford.
Delivery Option: 
Online


Online Course  Free 

Statement of accomplishment
You get a signed SoA from the instructor if you get 50% of the marks (roughly half for homework, half for the final). An SoA with Distinction requires 85% of the marks.
Textbook Requirements
The class is selfcontained, and you are not expected to purchase or steal a textbook. However, should you wish to do so, the textbook that matches the course most closely is Automata Theory, Languages, and Computation by Hopcroft, Motwani, and Ullman, AddisonWesley, 2007.
Expected Level of Effort
The amount of work will vary, depending on your background and the ease with which you follow mathematical ideas. However, 10 hours per week is a good guess.
This course may not currently be available to learners in some states and territories.
Delivery Option: 
Online


Online Course  Free 

Statement of accomplishment
You get a signed SoA from the instructor if you get 50% of the marks (roughly half for homework, half for the final). An SoA with Distinction requires 85% of the marks.
Textbook Requirements
The class is selfcontained, and you are not expected to purchase or steal a textbook. However, should you wish to do so, the textbook that matches the course most closely is Automata Theory, Languages, and Computation by Hopcroft, Motwani, and Ullman, AddisonWesley, 2007.
Expected Level of Effort
The amount of work will vary, depending on your background and the ease with which you follow mathematical ideas. However, 10 hours per week is a good guess.
This course may not currently be available to learners in some states and territories.