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.

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)

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.

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.

**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

Included in selections:

Информатика и программирование

1 курс МИЭМ ВШЭ, 10 кредитов

1 курс МИЭМ ВШЭ, 10 кредитов

More on this topic:

Introduction to the Theory of Computation

This course is an introduction to the theory of computation, teaching...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

This course will explore indigenous ways of knowing and how this knowledge can...

Analytic Combinatorics

Analytic Combinatorics teaches a calculus that enables precise quantitative...

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...

Designed for teachers and learners in every setting - in school and out, in...

© 2013-2019