Pojęcia łańcucha pustego, przyrostka, przedrostka, alfabetu i języka.
Operacja konkatenacji
Definicja Automatu skończonego (AS)
Rozszerzenie funkcji przejścia AS
Akceptowanie łańcucha przez AS
Pojęcie języka regularnego
Automaty NAS
Rozszerzenie funkcji przejścia w NAS
Akceptowanie języka przez NAS
Konwersja NAS w DAS
Automat skończony z ε-ruchami
Pojęcie ε-domknięcia
Konwersja automaty NAS z ε-ruchami na NAS
Podnoszenie wyrazu do potęgi
Operacje na językach
Definicja rekurencyjna wyrażeń regularnych
Priorytety operatorów w wyrażeniach regularnych
Skróty notacyjne w wyrażeniach regularnych
Konwersja WR na automat NAS z ε-ruchami (konstrukcja Thompsona)
Zastosowanie Grep, Perl i Flex.
Minimalizacja AS -metoda Huffmana.
Minimalizacja AS - metoda tablicy implikantów
Lemat o pompowaniu (nieformalnie)
Definicja formalnej gramatyki
Alfabet całkowity gramatyki
Wyprowadzenie bezpośrednie wyrazu, wyprowadzenie wyrazu
Pojęcie pustego języka
Hierarchia Chomsky'ego
Rozpoznawanie gramatyki danego rodzaju wg hierarchii Chomsky'ego
Budowa AS z zadanej gramatyki oraz odczyt gramatyki z AS.
Drzewo składniowe
Ciąg numerów reguł gramatyki
Niejednoznaczność wyprowadzenia
Notacja BNF
Wykresy składniowe
Definicja automatu ze stosem
Sposób działania automatu ze stosem
Gramatyki akceptowane przez automat ze stosem
Definicja Maszyny Turinga (MT)
Akceptacja języka przez MT
Języki rekurencyjne i rekurencyjnie przeliczalne
Funkcje częściowo i całkowicie rekurencyjne
Teza Churcha-Turinga
Pojęcie Uniwersalnej MT
Problem stopu; pojęcie nierozstrzygalności
Umiejętność rysowania MT dla dodawania i odejmowania liczby 1 w systemie jedynkowym, mnożenia i dzielenia przez wielokrotności liczby 2 w systemie dwójkowym, określania parzystości liczby zapisanej w systemie jedynkowym bądź dwójkowym
Rozwinięcia MT
Maszyna RAM - budowa i zasady pracy
Instrukcje dostępne w RAM
Postaci operandum w maszynie RAM
Akceptowanie języków i obliczanie funkcji na RAM
Złożoność czasowa i pamięciowa programu RAM
Koszt zuniformizowany i koszt logarytmiczny