Automata Theory on Coursera
Written by Sue Gee   
Wednesday, 16 September 2015

Jeff Ullman's course on automata and language theory started on September 12th on the Cousera platform. It runs until October 23rd with a final exam at the beginning of November so there is still time to join.


Automata is based on Stanford University's course CS154. Over 6 weeks, with a workload of around 10 hours per week the course cover fours broad areas:

(1) Finite automata and regular expressions,

(2) Context-free grammars,

(3) Turing machines and decidability,

(4) Intractability and NP-completeness.

Each week there's about two hours of video to watch and one or two groups of homework questions.

If you are asking yourself, "why study automata and language theory" it is a question addressed in this trailer video in which Jell Ullman points out that finite automata, regular expressions and context-free grammars are concepts that have stood the test of time. As well as essential tools for compilers 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."

Evidence of the practical usefulness of studying these topics comes from a survey of Stanford graduates taken five years after they got their undergraduate degrees asking which of the courses they actually used in their jobs. Among Computer Science graduates CS154 placed second among elective courses, second only to databases.



This course is a re-run and a review on Class Central from a student who completed a previous presentation gives another good reason in a 5/5 star review: 

Automata lead me to more revelations about the nature of computing than any other class I’ve taken, online or offline.

The same student advised:

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.

Another reviewer who rated it 4/5 points out that the course follows the book “Introduction to Automata Theory, Languages, and Computation” by John Hopcroft, Rajeev Motwani and Jeffrey Ullman and commented:

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.

On Coursetalk a reviewer awarding 4.5 stars states:

If you don't have prior knowledge you will find very very hard to follow lectures.

The prerequistes for the course are a second-level course in Computer Science that covers basic data structures (e.g., lists, trees, hashing), and basic algorithms (e.g., tree traversals, recursive programming, big-oh running time). In addition, a course in discrete mathematics covering propositional logic, graphs, and inductive proofs is valuable background. Also there are optional programming exercises for which a knowledge of Java or Python is required. 



Keep Up To Date With Microsoft's .NET Live TV

Microsoft has a new portal for all its .NET and Visual Studio live streams. While the original Twitch and YouTube channels aren't going away, .NET Live TV provides easy access to what's currently on o [ ... ]

Haskell Foundation Launched

Launched at this week's Haskell eXchange online event, the newly formed Haskell Foundation has been established as a non-profit dedicated to broadening the adoption of the Haskell programming language [ ... ]

More News






or email your comment to:

Last Updated ( Thursday, 17 September 2015 )