To support our site, Class Central may be compensated by some course providers.

Automata Theory

Stanford University via Stanford OpenEdx

students interested
  • Provider Stanford OpenEdx
  • $ Cost Free Online Course
  • Session Self Paced
  • Language English
  • Certificate Certificate Available
  • Effort 8-10 hours a week
  • Start Date
  • Duration 6 weeks long

Taken this course? Share your experience with other students. Write review

I am pleased to be able to offer free over the Internet a course on Automata Theory, based on the material I have taught periodically at Stanford in the course CS154. Participants have access to screencast lecture videos, are given quiz questions, assignments and exams, receive regular feedback on progress, and can participate in a discussion forum. Those who successfully complete the course will receive a statement of accomplishment. You will need a decent Internet connection for accessing course materials, but should be able to watch the videos on your smartphone.

The course covers four broad areas: (1) Finite automata and regular expressions, (2) Context-free grammars, (3) Turing machines and decidability, and (4) the theory of intractability, or NP-complete problems.

Why Study Automata Theory?


This subject is not just for those planning to enter the field of complexity theory, although it is a good place to start if that is your goal. Rather, the course will emphasize those aspects of the theory that people really use in practice. Finite automata, regular expressions, and context-free grammars are ideas that have stood the test of time. They are essential tools for compilers. But more importantly, they are used in many systems that require input that is less general than a full programming language yet more complex than "push this button."

The concepts of undecidable problems and intractable problems serve a different purpose. Undecidable problems are those for which no computer solution can ever exist, while intractable problems are those for which there is strong evidence that, although they can be solved by a computer, they cannot be solved sufficiently fast that the solution is truly useful in practice. Understanding this theory, and in particular being able to prove that a problem you are facing belongs to one of these classes, allows you to justify taking another approach — simplifying the problem or writing code to approximate the solution, for example.

During the course, I'm going to prove a number of things. The purpose of these proofs is not to torture you or confuse you. Neither are the proofs there because I doubt you would believe me were I merely to state some well-known fact. Rather, understanding how these proofs, especially inductive proofs, work, lets you think more clearly about your own work. I do not advocate proofs that programs are correct, but whenever you attempt something a bit complex, it is good to have in mind the inductive proofs that would be needed to guarantee that what you are doing really works in all cases.

Taught by

Jeffrey Ullman

Related Courses

Reviews for Stanford OpenEdx's Automata Theory
4.0 Based on 18 reviews

  • 5 stars 33%
  • 4 stars 44%
  • 3 stars 17%
  • 2 star 0%
  • 1 star 6%

Did you take this course? Share your experience with other students.

Write a review
  • 1
Anonymous
4.0 5 years ago
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.
3 people found
this review helpful
Was this review helpful to you? Yes
Mark W
5.0 4 years ago
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.
5 people found
this review helpful
Was this review helpful to you? Yes
Anonymous
4.0 2 years ago
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!

1 person found
this review helpful
Was this review helpful to you? Yes
Anonymous
3.0 4 years ago
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
2 people found
this review helpful
Was this review helpful to you? Yes
Anonymous
4.0 2 years ago
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!

Was this review helpful to you? Yes
Marat M
4.0 3 years ago
by Marat partially completed this course, spending 10 hours a week on it and found the course difficulty to be hard.
0 person found
this review helpful
Was this review helpful to you? Yes
Ashlynn P
5.0 a year ago
by Ashlynn completed this course.
Was this review helpful to you? Yes
Monica G
5.0 2 years ago
Monica completed this course.
Was this review helpful to you? Yes
Rey C
4.0 3 years ago
by Rey completed this course.
Was this review helpful to you? Yes
Mohammed E
3.0 a year ago
by Mohammed completed this course.
Was this review helpful to you? Yes
Bruno L
5.0 2 years ago
by Bruno completed this course.
Was this review helpful to you? Yes
Félix P
5.0 3 years ago
by Félix completed this course.
Was this review helpful to you? Yes
Marian M
3.0 2 years ago
by Marian partially completed this course.
Was this review helpful to you? Yes
Colin K
4.0 2 years ago
by Colin completed this course.
Was this review helpful to you? Yes
Maresu R
4.0 3 years ago
Maresu completed this course.
Was this review helpful to you? Yes
Christopher P
5.0 2 years ago
by Christopher completed this course.
Was this review helpful to you? Yes
Rafael P
1.0 3 years ago
Rafael dropped this course.
0 person found
this review helpful
Was this review helpful to you? Yes
Ilya R
4.0 3 years ago
by Ilya completed this course.
0 person found
this review helpful
Was this review helpful to you? Yes
  • 1

Class Central

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