This course covers finite automata, context-free grammars, Turing machines, undecidable problems, and intractable problems (NP-completeness).
Stanford University and coursera offers this online course.
About the course:
They pleased to be able to offer free over the Internet a course on Automata Theory, based on the material they 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:
- Finite automata and regular expressions
- Context-free grammars
- Turing machines and decidability
- The theory of intractability, or NP-complete problems.
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)
- Duration: 6 weeks of study
- Timings: 8 to 10 hours of work / week.
To apply, click here.