MyPage is a personalized page based on your interests.The page is customized to help you to find content that matters you the most.

I'm not curious


Course Summary

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

  • +

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

  • +

    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.

  • +

    Suggested Reading

    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 Fee:

Course Type:


Course Status:



1 - 4 hours / week

Related Posts:

Attended this course?

Back to Top

Awards & Accolades for MyTechLogy
Winner of
Top 100 Asia
Finalist at SiTF Awards 2014 under the category Best Social & Community Product
Finalist at HR Vendor of the Year 2015 Awards under the category Best Learning Management System
Finalist at HR Vendor of the Year 2015 Awards under the category Best Talent Management Software
Hidden Image Url

Back to Top