Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Online Course

Automata Theory

Stanford University via edX

Overview

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.

Taught by

Jeffrey Ullman

Reviews

4.0 rating, based on 20 reviews

Start your review of Automata Theory

  • Bruno completed this course.

  • Anonymous

    Anonymous completed this course.

    This course covers following topics : finite automata (deterministic, non-deterministic), regular expressions, context-free grammars and languages, Turing machines, decidability, and P and NP problems. The course closely follows the book “Introduction to Automata Theory, Languages, and Computation” by John Hopcroft, Rajeev Motwani and Jeffrey Ullman. I found the book more interesting than video lectures that , in my opinion, were too long and sometimes boring. Last two weeks, again, in my opinion, were rushed and I didn't really understand P and NP problems. That said, I'm glad I took this course and satisfied my interest in regular languages and context-free grammars.
  • Mark W.

    Mark completed this course.

    Automata lead me to more revelations about the nature of computing than any other class I’ve taken, online or offline. It was fantastic. Discrete math is definitely a pre-requisite but the course info page provided a link to a free online book for students without the needed background!

    The only caveat about this class is that unlike a lot of MOOCs, just working at the keyboard doesn’t work so well. I strongly recommend breaking out a pencil and paper and working through all the problems in the videos and homework assignments.
  • Anonymous

    Anonymous completed this course.

    Automata is an interesting concept and I had no prior knowledge to this part of computer science. Course content is good but one needs to invest lot of effort to learn it. I used 2 books linz(1) and ullman(2) books for studying the subject. But still i need to study hard to learn the concepts properly. NP complete and context free grammars were the points where i became blank.

    But finally completed the course :D

    Cheers!

  • Anonymous

    Anonymous completed this course.

    As the other reviewer stated, the lectures are too long , and the concepts advanced is a very rapid fashion.

    However i would say , i don't have a computer science or maths background. It was useful for quality information on automata
  • Kristina completed this course and found the course difficulty to be hard.

    This is a great course covering automata and complexity theory, aimed at those who can follow university-level mathematics easily. So, if there's no prior background, this might not be the case for you, since it's more math-oriented rather than computer...
  • Anonymous

    Anonymous completed this course.

    Automata is an interesting concept and I had no prior knowledge to this part of computer science. Course content is good but one needs to invest lot of effort to learn it. I used 2 books linz(1) and ullman(2) books for studying the subject. But still i need to study hard to learn the concepts properly. NP complete and context free grammars were the points where i became blank.

    But finally completed the course :D

    Cheers!

  • Prashant is taking this course right now, spending 10 hours a week on it and found the course difficulty to be hard.

    This course could be made more interesting .Video lectures sometimes feel very dry .This course is foundation of computer science so this concepts should be explained using concrete example to enforce understanding .
  • Andrei .

    Andrei completed this course.

  • Marat M.

    Marat completed this course, spending 10 hours a week on it and found the course difficulty to be hard.

  • Rey completed this course.

  • Félix completed this course.

  • Profile image for Monica Guimaraes
    Monica G.

    Monica completed this course.

  • Colin completed this course.

  • Marian completed this course.

  • Christopher completed this course.

  • Mohammed completed this course.

  • Ashlynn completed this course.

  • Ilya completed this course.

  • Rafael P.

    Rafael is taking this course right now.

Related Courses

Class Central

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free

Never stop learning Never Stop Learning!

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free