Automata

Jeffrey Ullman, Professor, Stanford University

This course covers finite automata, context-free grammars, Turing machines, undecidable problems, and intractable problems (NP-completeness).

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.

Syllabus

Week 1: Finite Automata
Week 2: Regular Expressions and Properties of Regular Languages
Week 3: Context-Free Grammars and Languages
Week 4: Properties of Context-Free Languages, plus introduction to Turing Machines
Week 5: Turing Machines and Undecidability
Week 6: Intractable Problems (NP-Completeness)

Recommended Background

You should have had a second course in Computer Science — one 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.

If you need to review or learn some of these topics, there is a free on-line textbook Foundations of Computer Science, written by Al Aho and me, available at http://i.stanford.edu/~ullman/focs.html. Recommended chapters include 2 (Recursion and Induction), 3 (Running Time of Programs), 5 (Trees), 6 (Lists), 7 (Sets), 9 (Graphs), and 12 (Propositional Logic). You will also find introductions to finite automata, regular expressions, and context-free grammars in Chapters 10 and 11. Reading Chapter 10 would be good preparation for the first week of the course.

The course includes two programming exercises for which a knowledge of Java or Python is required. However, these exercises are optional. You will receive automated feedback, but the results will not be recorded or used to grade the course. So if you are familiar with neither Java nor Python, you can still take the course without concern for prerequisites.

The course is built around the material in Automata Theory, Languages, and Computation 3rd edition (2007), by John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, Addison-Wesley. However, you do not have to buy a copy of this book. The course is self-contained, and all homeworks and exams are based solely on concepts taught in the video lectures.

Course Format

3-4 lecture videos each week.  Many of these videos are longer than the typical MOOC video, so feel free to pause them and view them in several sessions of your own choice.

There will be 1-2 problem sets each week, which together count for 50% of the marks.  You can repeat them until you get them all correct, and they are due two Mondays after release of the videos on which they are based.

There are also two optional programming challenges.

FAQ

• Will I get a statement of accomplishment after completing this class?

Yes. Participants who successfully complete the class will receive a statement of accomplishment signed by the instructor.

• What is the format of the class?

The class will consist of lecture videos, which are between 15 and 45 minutes in length. These contain integrated quiz questions. There will also be standalone homeworks that are not part of video lectures, optional programming assignments, and a (not optional) final exam.

• How much work will I be expected to do in this class?

You need to work about 5-10 hours per week to complete the course. About 2 hours of video segments each week, containing inline ungraded quiz questions. A weekly, graded multiple choice homework.

Dates:
• 12 September 2015, 6 weeks
• 1 September 2014, 6 weeks
• 4 November 2013, 6 weeks
• 23 April 2012, 6 weeks
Course properties:
• Free:
• Paid:
• Certificate:
• MOOC:
• Video:
• Audio:
• Email-course:
• Language: English

Reviews

No reviews yet. Want to be the first?

Register to leave a review

Included in selections:
Информатика и программирование
1 курс МИЭМ ВШЭ, 10 кредитов

More on this topic:
Introduction to the Theory of Computation
This course is an introduction to the theory of computation, teaching...
Automata, Computability, and Complexity
This course provides a challenging introduction to some of the central ideas...
Mathematics for Computer Science (Fall 2010)
This course covers elementary discrete mathematics for computer science and...
Great Ideas in Theoretical Computer Science
This course provides a challenging introduction to some of the central ideas...
Algebraic Combinatorics
This is an introductory course in algebraic combinatorics. No prior knowledge...
More from 'Computer Science':
Bias and Discrimination in AI
Discover how even computer algorithms may be biased and have a serious impact...
Deep Learning Essentials
Do you want to learn how machines can learn tasks we thought only human brains...
Machine Learning with Python: A Practical Introduction
Machine Learning can be an incredibly beneficial tool to uncover hidden insights...
Compilers
This self-paced course will discuss the major ideas used today in the implementation...
Automata Theory
This course covers the theory of automata and languages. We begin with a study...
More from 'Coursera':
First Year Teaching (Secondary Grades) - Success from the Start
Success with your students starts on Day 1. Learn from NTC's 25 years developing...
Understanding 9/11: Why Did al Qai’da Attack America?
This course will explore the forces that led to the 9/11 attacks and the policies...
Aboriginal Worldviews and Education
This course will explore indigenous ways of knowing and how this knowledge can...
Analytic Combinatorics
Analytic Combinatorics teaches a calculus that enables precise quantitative...
Accountable Talk®: Conversation that Works
Designed for teachers and learners in every setting - in school and out, in...