Podstawowe definicje słów i języków nad alfabetem, pojęcie wyrażenia regularnego, deterministyczny automat skończony, niedeterministyczny automat skończony, automat skończony z przejściami pustymi, twierdzenie Kleeniego, zamkniętość zbiorów regularnych na operacje standardowe, lemat o pompowaniu dla zbiorów regularnych, przykłady języków nieregularnych, algorytmy decyzyjne dla zbiorów regularnych, ilorazy i minimalizacja automatu skończonego, wprowadzenie do gramatyk bezkontekstowych, drzewa wywodu, wieloznaczność, upraszczanie gramatyk, postacie normalne gramatyk bezkontekstowych, lemat o pompowaniu dla języków bezkontekstowych, języki regularne a gramatyki regularne, przykłady języków niebezkontekstowych, definicja automatu ze stosem, automat ze stosem a gramatyki bezkontekstowe, zamkniętość języków bezkontekstowych na niektóre operacje, algorytmy decyzyjne dla języków bezkontekstowych, automat liniowo ograniczony, gramatyki kontekstowe i monotoniczne, równoważność definicji języka kontekstowego, podstawowe własności języków kontekstowych, algorytmy decyzyjne dla języków kontekstowych, istnienie języków niekontekstowych, gramatyki nieograniczone, maszyna Turinga, równoważne modele maszyny, obliczalność, problemy nierozstrzygalne, dowodzenie nierozstrzygalności, twierdzenie Rice'a, funkcje obliczalne, hierarchia Chomsky'ego języków i automatów, relacje pomiędzy klasami języków.