Kapitlena hänvisar till boken "Formella språk, automater och beräkningar" (andra upplagan).
1. Introduktion. Strängar, program, uppräknelighet, funktioner som ej kan beräknas med program. Språk. Kapitel 1.1 - 1.3.
2-3. Operationer på strängar och språk. Reguljära språk och uttryck. Deterministiska och icke-deterministiska ändliga automater. Delmängdskonstruktionen; för varje NFA så finns en DFA som accepterar samma språk. Ett språk är reguljärt om och endast om det är ett språk som accepteras av någon ändlig automat. Slutenhetsegenskaper för reguljära språk. Reduktion av antalet tillstånd hos en DFA. Kapitel 1.4, 2.1 - 2.7.
4. De reguljära språkens gränser; särskiljandesatsen, pumpsatsen. Kapitel 2.8.
5. Strängproduktion med grammatiska regler; sammanhangsfria grammatiker och språk; produktionsträd. Kapitel 3.1 - 3.2.
6-7. Pushdown automater; top-down och bottom-up parser. Ett språk är sammanhangsfritt om och endast om det är ett språk som accepteras av någon pushdown automat. De sammanhangsfria språkens gränser; pumpsatsen för sammanhangsfria språk. Chomskys språkhierarki. Kapitel 3.3 - 3.6.
8-9. Restriktionsfria grammatiker. Turingmaskiner. Ett språk är restriktionsfritt om och endast om det är Turing-accepterbart. Universella Turing maskiner. Primitivt rekursiva och rekursiva funktioner. Kapitel 4.1 - 4.6, 5.1 - 5.3.
10. Turings tes och Church tes. En funktion är rekursiv om och endast om den kan beräknas av en Turingmaskin. Oavgörbarhet; stop-problemet, Rices sats. Kapitel 5.4 - 5.6.
11. Repetition.