Automata

Product type

Automata

Coursera (CC)
Logo Coursera (CC)
Provider rating: starstarstarstar_halfstar_border 7.2 Coursera (CC) has an average rating of 7.2 (out of 6 reviews)

Need more information? Get more details on the site of the provider.

Description

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

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

About the Course

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. Students 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 th…

Read the complete description

Frequently asked questions

There are no frequently asked questions yet. If you have any more questions or need help, contact our customer service.

Didn't find what you were looking for? See also: .

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

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

About the Course

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

About the Instructor(s)

Jeff Ullman is the S. W. Ascherman Prof. of Engineering (emeritus) at Stanford University, where he taught in the Computer Science Dept. from 1979-2002. He worked at Bell Laboratories from 1966-1969, and taught at Princeton Univ. (from which he also received his PhD in 1966) between 1969 and 1979. He first taught Automata Theory in 1967 at Columbia University (from which he received his BS Degree in 1963), and has been teaching it periodically, ever since. He is the author or coauthor of widely read textbooks in Compilers, Databases, Algorithms, and Data Mining, as well as the book in Automata on which this course is based. He is a member of the National Academy of Engineering, winner of the ACM Karl V. Karlstrom Education award, the IEEE Von Neumann Medal, and the Knuth Prize.

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 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 not familiar with Java, you can still take the course without concern for prerequisites.

Suggested Readings

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.

FAQ

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

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

Provided by:

University: Stanford University

Instructor(s): Jeffrey Ullman, Professor

There are no reviews yet.

    Share your review

    Do you have experience with this course? Submit your review and help other people make the right choice. As a thank you for your effort we will donate $1.- to Stichting Edukans.

    There are no frequently asked questions yet. If you have any more questions or need help, contact our customer service.