Models of Computation lecture notes (Strings, Regular Languages, Automata, NFAs, Context-Free Languages)
by Jeff Erickson · University of Illinois Urbana-Champaign
Free lecture notes from the University of Illinois, about 95 pages across five PDFs. They cover strings and induction, regular expressions, DFAs, NFAs and their equivalence, and context-free grammars. This is the strongest free written text for the formal-languages part of the topic. It is unusually careful with induction on strings, which is where self-learners usually get stuck, and it has plenty of exercises.
More resources on Formal Languages
Brilliant.org - Theory of Computation
Interactive problems on formal languages
Theory of Computation
Learn computability theory with Kamala Krithivasan's Theory of Computation course. Explore fundamental concepts and problem-solving!
Parsing Techniques: A Practical Guide (2nd Edition)
Comprehensive reference on how grammars are turned into parsers. Covers general CF parsing (CYK, Earley, GLR), deterministic top-down LL and bottom-up LR methods, regular-grammar parsing, error recovery, and non-Chomsky grammar formalisms. Requires no advanced mathematics.
brilliant.org
Brilliant.org is an online, interactive learning platform offering problem-based courses in math and computer science, including topics in automata theory, computation, and discrete mathematics, with guided lessons and practice problems.
Formal Languages and Their Relation to Automata
The 1969 monograph that organized formal language theory around the Chomsky hierarchy, pairing regular, context-free, context-sensitive and recursively enumerable languages with finite automata, pushdown automata, linear bounded automata and Turing machines. Proof-based; readers learn the classical closure and decidability results.