• Length:
    7 Weeks
  • Effort:
    5–10 hours per week
  • Price:

    FREE
    Add a Verified Certificate for $129 USD

  • Institution
  • Subject:
  • Level:
    Advanced
  • Language:
    English
  • Video Transcript:
    English

Prerequisites

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.

It is intended for students who have had at least 2 years of Computer-Science courses, including discrete mathematics (graphs, trees, logic, proofs, etc.) and an introduction to data structures and algorithms.

About this course

Skip About this course

We begin with a study of finite automata and the languages they can define (the so-called "regular languages." Topics include deterministic and nondeterministic automata, regular expressions, and the equivalence of these language-defining 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 context-free 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 context-free languages. We also introduce the pushdown automaton, whose nondeterministic version is equivalent in language-defining power to context-free 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 so-called "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 context-free 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 NP-complete 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 polynomial-time algorithms. A common example of an NP-complete problem is SAT, the question of whether a Boolean expression has a truth-assignment to its variables that makes the expression itself true.

What you'll learn

Skip What you'll learn
  • Finite automata and regular expressions
  • Context-free grammars
  • Turing machines and decidability
  • The theory of intractability, or NP-complete problems

Meet your instructors

Jeffrey D. Ullman
Professor of Engineering, Emeritus
Stanford University

Pursue a Verified Certificate to highlight the knowledge and skills you gain
$129.00

View a PDF of a sample edX certificate
  • Official and Verified

    Receive an instructor-signed certificate with the institution's logo to verify your achievement and increase your job prospects

  • Easily Shareable

    Add the certificate to your CV or resume, or post it directly on LinkedIn

  • Proven Motivator

    Give yourself an additional incentive to complete the course

  • Support our Mission

    EdX, a non-profit, relies on verified certificates to help fund free education for everyone globally

Frequently asked questions

Do I need to buy a textbook?

The class is self-contained, 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, Addison-Wesley, 2007.

What should I do if I don't have the prerequisites?

For this purpose, there is a free textbook Foundations of Computer Science.

How much work is expected?

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.

Who can take this course?

Unfortunately, learners from one or more of the following countries or regions will not be able to register for this course: Iran, Cuba and the Crimea region of Ukraine. While edX has sought licenses from the U.S. Office of Foreign Assets Control (OFAC) to offer our courses to learners in these countries and regions, the licenses we have received are not broad enough to allow us to offer this course in all locations. EdX truly regrets that U.S. sanctions prevent us from offering all of our courses to everyone, no matter where they live.