Various representations for regular languages, context-free grammars, normal forms, simple parsing, pumping lemmas, Turing machines, the Church-Turing thesis, intractable problems, the P-NP question.
Prerequisites:
Quality:
Difficulty:
Remarks:
- Very logic based class
- Lots of proofs (especially in the beginning) of the class
- Some memorization needed to remember definitions of the finite automatas